# You are a cat. How do you swap?

Number twenty-one cages containing mice, 1, 2, 3, etc., up to 21, and place them in the following order:

1 14 15 17 3 7 13 6 20 2 19 21 5 18 8 11 16 9 12 4 10

• You start from a cage of your choice, calling that cage one, and count, one, two, three, etc., from left to right. Once you reach the end, you continue counting from the leftmost cage.

• When your count matches with the number on the cage, you have made a catch, and you can eat that mouse (you're a cat), and throw away the cage.

• Then start at the cage next to it (or the leftmost cage, if you just caught the rightmost cage), call that one, and try to make another catch, and so on.

Let's say you start at 18, calling that cage one, your first catch will be 19.

1 14 15 17 3 7 13 6 20 2 19 21 5 18 8 11 16 9 12 4 10
^


Remove 19 and your next catch will be 10.

1 14 15 17 3 7 13 6 20 2    21 5 18 8 11 16 9 12 4 10
^


Remove 10 and your next catch is 1.

1 14 15 17 3 7 13 6 20 2    21 5 18 8 11 16 9 12 4
^


Remove the 1, and you cannot make another catch, even if you count up to 21.

  14 15 17 3 7 13 6 20 2    21 5 18 8 11 16 9 12 4
^


Since you're very hungry, you want to catch all the twenty-one mice. But you'll soon figure out that this is not here possible - no matter which cage you start from.

But here's what you can do:

You can choose two cages and swap them before you begin. Then, if you start at the right place, you might be able to catch all twenty-one mice.

• You may never pass over a catch, i.e., you must always eat the mouse you caught, remove that cage and continue.

• You can always count up to 21, even if fewer cages are left.

### What two cages would you swap, and which cage would you start counting from?

It would be great if you could include the strategy you used to get to the answer, unless you used brute force.

• I didn't realize you can count higher than the amount of cages. You may want to mention that in the question. May 23, 2014 at 21:33
• Updated. I hope its clearer now. May 23, 2014 at 21:36

I employed a brute force strategy, testing every possible swap with every possible starting position. I used the following Python code (Python 2.7):

cages = map(int, '1 14 15 17 3 7 13 6 20 2 19 21 5 18 8 11 16 9 12 4 10'.split())

swaps = ((i,j) for i in xrange(len(cages)) for j in xrange(len(cages)) if i > j)

for (i,j) in swaps:
for start in xrange(len(cages)):
l = list(cages)
l[i], l[j] = l[j], l[i]  # perform the swap
pos = start
count = 1

while (count <= 21) and l:
if l[pos] == count:
del l[pos]
count = 0
else:
pos += 1

if pos >= len(l):
pos = 0

count += 1

if not l:  # if the list is empty, we've found one that works
print 'swap', cages[i], 'with', cages[j], 'and start at', cages[start]


which produces the following output:

swap 6 with 13 and start at 14
swap 8 with 6 and start at 19
swap 10 with 14 and start at 16

• Yes, those are the three solutions to the problem. However, I would prefer an answer that does not use brute force over this one. If I don't find any, I shall accept this. May 23, 2014 at 22:24
• @JohnBupit I would also prefer such an answer. :) May 23, 2014 at 23:07