1
$\begingroup$

Consider constructing a vector $v=(a_1,a_2,\ldots,a_n)$ consisting of nonnegative integers such that $a_1=1$ and, if $a_j$'s are nonzero, then $a_j\equiv a_{n-j+2}+j-1 \pmod m\ \forall 1<j\le\frac{n}{2}$, where $m$ is the number of nonzero entries; with the additional constraint that all nonzero $a_i$'s are distinct modulo $m$. Note that the number $m$ itself appears once as a nonzero number satisfying the above congruence.

Is it always possible to construct such a vector? I think this should be possible if $m$ is odd. For example, $(1,4,2,5,3)$ and $(1,4,2,0,0,5,3)$ are such vectors. It is easy to construct if the first entries (within $\lfloor\frac{n}{2}\rfloor$) of the vector are consecutive. But, in other cases, it is not clear as to how to proceed with the construction. Any hints? Thanks beforehand.

$\endgroup$
  • 1
    $\begingroup$ Your two examples are nonnegative, have $a_1=1$, and have distinct nonzero entries, but the mod condition fails for both. $\endgroup$ – Rob Pratt Feb 8 at 22:24
  • $\begingroup$ @RobPratt thanks! edited. see now. $\endgroup$ – vidyarthi Feb 8 at 22:29
  • $\begingroup$ Still not right. For $j=2$, $4\not\equiv 5+2-1 \pmod 5$. $\endgroup$ – Rob Pratt Feb 8 at 22:37
  • 1
    $\begingroup$ For the first example, $n=5$, and $j=2$ yields $a_{n-j+1}=a_{5-2+1}=a_4=5\not= 3$. $\endgroup$ – Rob Pratt Feb 8 at 23:43
  • 1
    $\begingroup$ Your second example fails for $j=6$ because $5\not\equiv 2+6-1 \pmod{5}$. $\endgroup$ – Rob Pratt Feb 9 at 18:39
1
$\begingroup$

Yes, such construction is always possible.

Consider two sets of pairs of values: $$\big\{ (2+t,m-t)\quad :\quad t=0\,..\,\lfloor\frac{m-1}{4}\rfloor-1\big\},$$ where differences of elements modulo $m$ are: $2,4,\dots,2\cdot\lfloor\frac{m-1}{4}\rfloor$, and $$\big\{ (\lfloor\frac{m+1}{2}\rfloor+t+1,\lfloor\frac{m+1}{2}\rfloor-t)\quad :\quad t=0\,..\,\lfloor\frac{m+1}{4}\rfloor-1\big\},$$ where differences of elements modulo $m$ are: $1, 3, \dots, 2\cdot\lfloor\frac{m+1}{4}\rfloor-1.$ Together they give all differences from $1$ to $\lfloor\frac{m-1}{2}\rfloor$.

Notice that all elements forming pairs in these sets are $\ne0,1$ and are distinct modulo $m$.

Therefore, it's enough to assign the values from these sets to the corresponding pairs $(a_j,a_{n+2-j})$, giving $2\cdot\lfloor\frac{m-1}{2}\rfloor$ nonzero $a_j$'s. If $m$ is even we need to assign one more yet unassigned nonzero value (which is $\lfloor\frac{3m}{4}\rfloor+1$) to any of yet unassigned $a_j$ with $j>\frac{n}2$. The other unassigned $a_j$ are set to zero.

$\endgroup$
  • 1
    $\begingroup$ @vidyarthi: a lot of drawing on a piece of paper ;) $\endgroup$ – Max Alekseyev Feb 10 at 21:23
  • 1
    $\begingroup$ @vidyarthi: I drew matchings between residues modulo $m$ giving differences $1,2,\dots$ $\endgroup$ – Max Alekseyev Feb 10 at 21:26
  • 1
    $\begingroup$ Assume $m|n$. There are no $j\equiv 1\pmod m$ in the interval $[2,n/2]$ if $m\geq n/2$. So, the additional restriction playa role only when $m\leq n/3$. However, in this case we can simply assign all nonzero values to $a_j$'s with $j>n/2$. $\endgroup$ – Max Alekseyev Feb 22 at 6:04
  • 1
    $\begingroup$ For $m\leq n/3$, simply set $a_{n/2+k}=k$ for $k=1..m$, and all other $a_j$ to 0. If $n/3<m<n/2$, then $m$ cannot divide $n$. $\endgroup$ – Max Alekseyev Feb 22 at 22:11
  • 1
    $\begingroup$ I do not quite follow again. According to your original question, the congruence $a_j\equiv a_{n+2-j}+j-1\pmod m$ is required only for nonzero $a_j$. In the above example, for $j=n/2-1$ we have $a_j=0$, and so the congruence may not hold. $\endgroup$ – Max Alekseyev Feb 24 at 13:49
0
$\begingroup$

Computational experiments for $1 \le m \le n \le 20$ yield feasible solutions even if you impose the upper bound $a_j \le n$. Here is an infinite family for $m \le \lceil n/2\rceil +1$: $$(1,\underbrace{0,\dots,0}_{n-m},2,3,4,\dots,m)$$

Here are the lexicographically smallest solutions for $n=m$: \begin{matrix} n & a\\ \hline 1& (1)\\ 2& (1, 2)\\ 3& (1, 2, 3)\\ 4& (1, 3, 4, 2)\\ 5& (1, 3, 4, 5, 2)\\ 6& (1, 3, 6, 5, 4, 2)\\ 7& (1, 3, 6, 5, 7, 4, 2)\\ 8& (1, 3, 6, 8, 7, 5, 4, 2)\\ 9& (1, 3, 6, 8, 7, 9, 5, 4, 2)\\ 10& (1, 3, 6, 10, 9, 8, 5, 7, 4, 2)\\ 11& (1, 3, 6, 8, 11, 9, 10, 7, 5, 4, 2)\\ 12& (1, 3, 6, 11, 9, 12, 10, 7, 5, 8, 4, 2)\\ 13& (1, 3, 6, 8, 13, 12, 10, 11, 7, 9, 5, 4, 2)\\ 14& (1, 3, 6, 10, 12, 14, 5, 11, 13, 9, 8, 7, 4, 2)\\ 15& (1, 3, 6, 8, 14, 12, 15, 11, 13, 9, 7, 10, 5, 4, 2)\\ 16& (1, 3, 6, 10, 12, 16, 15, 5, 13, 14, 9, 11, 8, 7, 4, 2)\\ 17& (1, 3, 6, 8, 13, 15, 17, 14, 12, 16, 7, 11, 10, 9, 5, 4, 2)\\ 18& (1, 3, 6, 8, 13, 16, 18, 17, 15, 14, 7, 10, 12, 11, 9, 5, 4, 2)\\ 19& (1, 3, 6, 8, 11, 17, 19, 16, 18, 14, 15, 10, 9, 13, 12, 7, 5, 4, 2)\\ 20& (1, 3, 6, 8, 13, 17, 20, 18, 15, 19, 16, 10, 7, 11, 14, 12, 9, 5, 4, 2)\\ \end{matrix}

$\endgroup$
  • $\begingroup$ thanks, but what about the general case? And even in the cases you have provided, what happens when I introduce zeroes in between the numbers ( thereby increasing $n$ keeping $m$ fixed) ? $\endgroup$ – vidyarthi Feb 9 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.