A Puzzle from the Möbius Tournament
Here is a puzzle for middle school students from the Möbius tournament.
Share:Puzzle. For which natural numbers n greater than 1 it is possible to arrange n numbers 1 through n in a circle so that the difference between two neighbors always divides n?
Ivan:
Dyslexic iVAN bets on eVAN numbers.
25 December 2024, 4:03 amAndreas:
Yes, it is possible to arrange the numbers as stated in the problem if and only if n is even.
When n is even we know that it’s allowed to have neighbors that differ by one or two. Place the number 1 on the circle, and place numbers that are higher by two in each step as you move around the circle until you reach n-1. Then place n, and continue with numbers that are lower by two until you reach 2:
1 – 3 – 5 – … – (n-3) – (n-1) – (n) – (n-2) – (n-4) – … – 2 – (wrap around to 1)
To prove that it’s never possible to arrange the numbers on the circle if n is odd, we first note that the sum of each step size around the circle must be even. When calculating the sum of all the differences, we take the difference for each pair of neighbors and add them all together. Since each number has two neighbors, it must occur in the sum twice (positive and negative) which results in an even sum.
However, when n is odd, we have an odd number of steps. Also, each step size is odd according to the rules, so the sum of the steps must be an odd number.
28 December 2024, 6:12 pmRobin:
Nice proof Andreas. I would like to add for clarity that all steps=absolute differences should be odd. Otherwise, n (odd) cannot be divided by all steps. However, we have an odd number of steps which sums to an even number. Hence at least one step is odd. To see why the steps sum to an even number one can also consider an apartment building with n (odd) floors. You will climb from 1 to n and descent to 1 again.
11 January 2025, 10:19 am