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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Your two examples are nonnegative, have $a_1=1$, and have distinct nonzero entries, but the mod condition fails for both. $\endgroup$
    – RobPratt
    Feb 8, 2020 at 22:24
  • $\begingroup$ @RobPratt thanks! edited. see now. $\endgroup$
    – vidyarthi
    Feb 8, 2020 at 22:29
  • $\begingroup$ Still not right. For $j=2$, $4\not\equiv 5+2-1 \pmod 5$. $\endgroup$
    – RobPratt
    Feb 8, 2020 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$
    – RobPratt
    Feb 8, 2020 at 23:43
  • 1
    $\begingroup$ Your second example fails for $j=6$ because $5\not\equiv 2+6-1 \pmod{5}$. $\endgroup$
    – RobPratt
    Feb 9, 2020 at 18:39

2 Answers 2

Reset to default
2
$\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.

ADDED. Here is a SageMath code implementing the above construction. There is a sample call construct_a(16,11), which constructs vector $(a_1,\dots,a_n)$ for parameters $n=16$ and $m=11$.

Improve this answer
$\endgroup$
35
  • 1
    $\begingroup$ @vidyarthi: a lot of drawing on a piece of paper ;) $\endgroup$
    – Max Alekseyev
    Feb 10, 2020 at 21:23
  • 1
    $\begingroup$ @vidyarthi: I drew matchings between residues modulo $m$ giving differences $1,2,\dots$ $\endgroup$
    – Max Alekseyev
    Feb 10, 2020 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, 2020 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, 2020 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, 2020 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}

Improve this answer
$\endgroup$
1
  • $\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, 2020 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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