1997 PMWC Problems/Problem T10

Revision as of 15:48, 7 January 2020 by Skyguy88 (talk | contribs) (Solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

The twelve integers $1, 2, 3,\dots, 12$ are arranged in a circle such that the difference of any two adjacent numbers is either $2, 3,$ or $4$. What is the maximum number of the difference $4$ can occur in any such arrangement?

Solution

We can use reasoning to determine the best answer. Seating $1$ in an arbitrarily chosen seat, we will try to draw a path from $1$ back to $1$ that includes every positive integer less than or equal to $12$ exactly once while maximizing the number of jumps of $4$.

Notice that, if we want to maximize the number of jumps of 4, the values in the sequence will fluctuate widely. Since we must eventually return to the number we started with, we can either go up to the double digits and back once, or we can try to double dip and reach the double digits on two different occasions. If we try to do this, we can develop a sort of see-saw pattern that moves up and down along different residue classes mod 4 (which is a fancy way of saying that the numbers have the same remainder when divided by 4).

If we try $1, 5, 9, 12, 8, 4, 2, 6, 10, 11, 7, 3, 1$, we see that there is a way to have 8 jumps of 4. One way to convince ourselves that this is the best answer is that we can only move up or down by fours at most two times before we hit the minimum or maximum of the integers. At this point, we have to jump by a number other than 4. Since the best case scenario is having two jumps of 4 for every one jump of 2 or 3, we can have at most $\frac{2}{3} * 12 = \boxed{8}$ jumps of 4.

Note that while the answer key says the answer is $7$, we can see from the arrangement provided above that that cannot be the correct answer.

See Also

1997 PMWC (Problems)
Preceded by
Problem T9
Followed by
Last
Problem
I: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T: 1 2 3 4 5 6 7 8 9 10
Invalid username
Login to AoPS