Difference between revisions of "1997 PMWC Problems/Problem T10"
(Created page with '#REDIRECT[http://home.comcast.net/~wolfand/]') |
(→Solution) |
||
| (6 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | ==Problem== | |
| + | The twelve integers <math>1, 2, 3,\dots, 12</math> are arranged in a circle such that the difference of any two adjacent numbers is either <math>2, 3,</math> or <math>4</math>. What is the maximum number of the difference <math>4</math> can occur in any such arrangement? | ||
| + | |||
| + | ==Solution== | ||
| + | |||
| + | We can use reasoning to determine the best answer. Seating <math>1</math> in an arbitrarily chosen seat, we will try to draw a path from <math>1</math> back to <math>1</math> that includes every positive integer less than or equal to <math>12</math> exactly once while maximizing the number of jumps of <math>4</math>. | ||
| + | |||
| + | 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 <math>1, 5, 9, 12, 8, 4, 2, 6, 10, 11, 7, 3, 1</math>, 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 <math>\frac{2}{3} * 12 = \boxed{8}</math> jumps of 4. | ||
| + | |||
| + | Note that while the answer key says the answer is <math>7</math>, we can see from the arrangement provided above that that cannot be the correct answer. | ||
| + | |||
| + | ==See Also== | ||
| + | |||
| + | {{PMWC box|year=1997|num-b=T9|after=Last<br />Problem}} | ||
Latest revision as of 14:48, 7 January 2020
Problem
The twelve integers 
are arranged in a circle such that the difference of any two adjacent numbers is either 
or 
. What is the maximum number of the difference can occur in any such arrangement?
Solution
We can use reasoning to determine the best answer. Seating 
in an arbitrarily chosen seat, we will try to draw a path from back to that includes every positive integer less than or equal to 
exactly once while maximizing the number of jumps of .
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 
, 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 
jumps of 4.
Note that while the answer key says the answer is 
, 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 | ||
