Competition problem — Combinatorics

Library / /157 of 168

Combinatorics Difficulty 2.7 Junior Find the answer

Suppose that $k \geq 2$ is a positive integer. An in-shuffle is performed on a list with $2 k$ items to produce a new list of $2 k$ items in the following way: - The first $k$ items from the original are placed in the odd positions of the new list in the same order as they appeared in the original list. - The remaining $k$ items from the original are placed in the even positions of the new list, in the same order as they appeared in the original list. For example, an in-shuffle performed on the list $P Q R S T U$ gives the new list $P S Q T R U$ . A second in-shuffle now gives the list $P T S R Q U$ . Ping has a list of the 66 integers from 1 to 66, arranged in increasing order. He performs 1000 in-shuffles on this list, recording the new list each time. In how many of these 1001 lists is the number 47 in the 24th position?

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

Starting with a list of $66=2 \times 33$ items, the items in the first 33 positions $1,2,3, \ldots, 31,32,33$ are moved by an in-shuffle to the odd positions of the resulting list, namely to the positions $1,3,5, \ldots, 61,63,65$ respectively. This means that an item in position $x$ with $1 \leq x \leq 33$ is moved by an in-shuffle to position $2 x-1$ . We can see why this formula works by first moving the items in positions $1,2,3, \ldots, 31,32,33$ to the even positions $2,4,6, \ldots, 62,64,66$ (doubling the original position numbers) and then shifting each backwards one position to $1,3,5, \ldots, 61,63,65$ . Also, the items in the second 33 positions $34,35,36, \ldots, 64,65,66$ are moved by an in-shuffle to the even positions of the resulting list, namely to the positions $2,4,6, \ldots, 62,64,66$ respectively. This means that an item in position $x$ with $34 \leq x \leq 66$ is moved by an in-shuffle to position $2(x-33)$ . We can see why this formula works by first moving the items in positions $34,35,36, \ldots, 64,65,66$ backwards 33 positions to $1,2,3, \ldots, 31,32,33$ and then doubling their position numbers to obtain $2,4,6, \ldots, 62,64,66$ . In summary, the item in position $x$ is moved by an in-shuffle to position - $2 x-1$ if $1 \leq x \leq 33$ - $2(x-33)$ if $34 \leq x \leq 66$ Therefore, the integer 47 is moved successively as follows: List | Position 1 | 47 2 | $2(47-33)=28$ 3 | $2(28)-1=55$ 4 | $2(55-33)=44$ 5 | $2(44-33)=22$ 6 | $2(22)-1=43$ 7 | $2(43-33)=20$ 8 | $2(20)-1=39$ 9 | $2(39-33)=12$ 10 | $2(12)-1=23$ 11 | $2(23)-1=45$ 12 | $2(45-33)=24$ 13 | $2(24)-1=47$ Because the integer 47 moves back to position 47 in list 13, this means that its positions continue in a cycle of length 12: $47,28,55,44,22,43,20,39,12,23,45,24$ This is because the position to which an integer moves is completely determined by its previous position and so the list will cycle once one position repeats. We note that the integer 47 is thus in position 24 in every 12th list starting at the 12th list. Since $12 \times 83=996$ and $12 \times 84=1008$ , the cycle occurs a total of 83 complete times and so the integer 47 is in the 24th position in 83 lists. Even though an 84th cycle begins, it does not conclude and so 47 does not occur in the 24th position for an 84th time among the 1001 lists.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.