1

enter image description here

The question is from Pui Ching Invitational Mathematics Competition (2019)

My attempt:

obvious solution (symmetric form is omitted)

$(0,1,2,3,...,n,0)$ [difference: $1 \& n$]

$(0,1,3,5,...,2m-1,2m,2m-2,...,0)$ [difference: $1 \& 2$]

$(0,2m-1,2m-3,...,1,2m,2m-2,...,0)$ [difference: $2 \& 2m-1$]

$(0,1,3,...,2m+1,2m,...,2,0)$[difference: $1 \& 2$]

$(0,m+1,1,m+2,2,...,2m,m,0)$ [difference: $m \& m+1$]

ex: if $n = 6$

$(0,1,2,3,4,5,6,0)$ [difference: $1 \& 6$]

$(0,1,3,5,6,4,2,0)$ [difference: $1 \& 2$]

$(0,5,3,1,6,4,2,0)$ [difference: $2 \& 5$]

$(0,4,1,5,2,6,3,0)$ [difference: $3 \& 4$]

In addition to general solutions, I found that if $n = 12$, other permutations exist:

$(0,3,1,4,6,8,11,9,12,10,7,5,2,0)$ [difference: $2 \& 3$]

$(0,9,5,1,10,6,2,11,7,3,12,8,4,0)$ [difference: $4 \& 9$]

Is there an algorithm to construct all possible permutations, or a formula to calculate the ways for any $n$? Thank you very much.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
Ichungchen
  • 190
  • 1
    The outcome $(0,1,2,3,4,5,6,0)$ actually has differences of $1$ and $-6$, not $1$ and $6$. If we're prescribing $a_0$ and $a_{53}$ to both be zero then $a_1-a_0$ is positive whereas $a_{53}-a_{52}$ is negative. – Matthew H. Sep 17 '21 at 14:48
  • Yes, I might misunderstand the original problem. If the difference is not defined as absolute value, the answer are only (1,2,....,51,52) and (52,51,...,2,1), am I right? However, I am very interested in the condition that difference is the absolute value (as I described above). Thank you very much. – Ichungchen Sep 17 '21 at 15:35
  • No, I think there can be more. There may be an alternative problem that is a bit less confusing to think about but gives an equivalent solution, something close is: find all permutations of 53 numbers (representing change in value) such that no more than 2 are unique, the sum of the first $n_1$ numbers does not equal the sum of the first $n_2$ numbers for any $n_1\ne n_2$, the sum of all 53 numbers is 0, and the sum of the absolute value of all 53 numbers is 104. But a problem with that is -1 52 times then +52 is permitted. – Swan Klein Sep 17 '21 at 17:15
  • I guess one could also require that the sum of the first $n$ integers must be non-negative to fix that issue. I'm trying to describe how I visualize the problem. – Swan Klein Sep 17 '21 at 17:15

1 Answers1

2

The answer is 52. Of the two unique values, you know that one value must be positive and one value must be negative. Let $a$ be the positive value and let $-b$ be the negative value, so $b$ is the absolute value of the negative value. By summing the differences, we have $$a_1-a_0 + a_2-a_1 + ... + a_{53}-a_{52} = a_{53}-a_0 = 0.$$ Thus, $$ak - bm = 0$$ where $k$ is the number of times the positive value occurs and $m$ is the number of times the negative value occurs. We also know that $k+m = 53$ so we can rewrite the above as $$(a+b)k - 53b = 0.$$ This says that $a+b$ is a multiple of 53 ($k$ cannot be a multiple of 53, because we can't increase more than 52 times; going from $a_{52}$ to $a_{53}$ must be a decrease.) Moreover, $a+b = 53$, because if it were greater than $106$, then either $a$ or $b$ would be greater than 53, which is impossible. This tells us the following: \begin{align*} a +b &= 53 \\ b &= k. \end{align*} Every positive pair $(a,b)$ which sum to 53 works; the algorithm is, you increase by $a$ until you can't, then you decrease by $b$ until you can't, and repeat this. In fact, if you can increase by $a$, you cannot decrease by $b$, so this is the only thing you can do.

Ex. $a=10$ and $b=43$ would generate, $10, 20, 30, 40, 50, 7, ..., 47, 4, ..., 44, 1, ..., 51, 8,...,48,...,5,...,45,...,2,...,52,...,9,...,49,6,...,46,3,...,43,0.$

This always works because subtracting $b$ is equal to adding $a$ and taking the mod $53$, and since $53$ is prime, we can always go around in a circle by keep adding $a$ mod 53.

ffffffyyyy
  • 161