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
    Commented Feb 8, 2020 at 22:24
  • $\begingroup$ @RobPratt thanks! edited. see now. $\endgroup$
    – vidyarthi
    Commented Feb 8, 2020 at 22:29
  • $\begingroup$ Still not right. For $j=2$, $4\not\equiv 5+2-1 \pmod 5$. $\endgroup$
    – RobPratt
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 10, 2020 at 21:23
  • 1
    $\begingroup$ @vidyarthi: I drew matchings between residues modulo $m$ giving differences $1,2,\dots$ $\endgroup$
    – Max Alekseyev
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 9, 2020 at 21:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .