There is a stack of cards numbered in order from 1 to n.
The first card is placed at the bottom of the stack.
The second card is removed.
Cards are alternately placed at the bottom and removed until only one card remains.
Which card is it?
While this puzzle was in the queue, there was a discussion of the interpretation of "second card"--whether it was the second card before the placement of the first card at the bottom of the deck, or the card that newly became second because of the switch of the first card's positon. The below considers both interpretations.
for n=2:45
deck=1:n;
while length(deck)>1
deck=[deck(2:end) deck(1)];
deck=deck(2:end); % remove what was 2nd card, but is on top after first phase
end
disp([n deck])
end
disp(' ')
for n=2:45
deck=1:n;
while length(deck)>1
deck=[deck(2:end) deck(1)];
deck=[deck(1) deck(3:end)]; % remove what was 3rd card but is now 2nd card
end
disp([n deck])
end
finds the card that remains, under two interprtations of "the second card is removed":
If "the second card" means the card that had been second before the top card was placed on the bottom, it's this sequence:
n card remaining
at end
2 1
3 3
4 1
5 3
6 5
7 7
8 1
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1
17 3
18 5
19 7
20 9
21 11
22 13
23 15
24 17
25 19
26 21
27 23
28 25
29 27
30 29
31 31
32 1
33 3
34 5
35 7
36 9
37 11
38 13
39 15
40 17
41 19
42 21
43 23
44 25
45 27
But if "second card" means the card that became second by the switch of the top card to the bottom (i.e., was the third card before the change in the top card's position, or, near the end, when the what had been the first card becomes the second, that one is removed):
2 2
3 1
4 2
5 4
6 6
7 1
8 2
9 4
10 6
11 8
12 10
13 12
14 14
15 1
16 2
17 4
18 6
19 8
20 10
21 12
22 14
23 16
24 18
25 20
26 22
27 24
28 26
29 28
30 30
31 1
32 2
33 4
34 6
35 8
36 10
37 12
38 14
39 16
40 18
41 20
42 22
43 24
44 26
45 28
In the first interpretation, when n is a power of 2, card labeled 1 remains at the end. In between powers of two, the first such leaves 3 as the remaining card and the rest follow with each successive odd-numbered card.
In the second interpretation, when n is a power of 2, card labeled 2 remains at the end. In between powers of two, the first such leaves 2 as the remaining card and the rest follow with each successive even-numbered card, except the card remaining for n that is 1 less than a power of 2, is 1.
Examples:
First interpretation Second interpretation
2 number of cards 2
1 2 initial configuration 1 2
2 1 after move 2 1
1 after deletion 2
etc.
3 3
1 2 3 1 2 3
2 3 1 2 3 1
3 1 2 1
1 3 1 2
3 1
4 4
1 2 3 4 1 2 3 4
2 3 4 1 2 3 4 1
3 4 1 2 4 1
4 1 3 4 1 2
1 3 4 2
3 1 2 4
1 2
5 5
1 2 3 4 5 1 2 3 4 5
2 3 4 5 1 2 3 4 5 1
3 4 5 1 2 4 5 1
4 5 1 3 4 5 1 2
5 1 3 4 1 2
1 3 5 1 2 4
3 5 1 4
5 3 4 1
3 4
6 6
1 2 3 4 5 6 1 2 3 4 5 6
2 3 4 5 6 1 2 3 4 5 6 1
3 4 5 6 1 2 4 5 6 1
4 5 6 1 3 4 5 6 1 2
5 6 1 3 4 6 1 2
6 1 3 5 6 1 2 4
1 3 5 6 2 4
3 5 1 2 4 6
5 1 2 6
1 5 6 2
5 6
7 7
1 2 3 4 5 6 7 1 2 3 4 5 6 7
2 3 4 5 6 7 1 2 3 4 5 6 7 1
3 4 5 6 7 1 2 4 5 6 7 1
4 5 6 7 1 3 4 5 6 7 1 2
5 6 7 1 3 4 6 7 1 2
6 7 1 3 5 6 7 1 2 4
7 1 3 5 6 1 2 4
1 3 5 7 1 2 4 6
3 5 7 1 4 6
5 7 3 4 6 1
7 3 4 1
3 7 1 4
7 1
8 8
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1
3 4 5 6 7 8 1 2 4 5 6 7 8 1
4 5 6 7 8 1 3 4 5 6 7 8 1 2
5 6 7 8 1 3 4 6 7 8 1 2
6 7 8 1 3 5 6 7 8 1 2 4
7 8 1 3 5 6 8 1 2 4
8 1 3 5 7 8 1 2 4 6
1 3 5 7 8 2 4 6
3 5 7 1 2 4 6 8
5 7 1 2 6 8
7 1 5 6 8 2
1 5 6 2
5 1 2 6
1 2
|
|
Posted by Charlie
on 2023-08-09 09:20:31 |
solutions
