The 41-st Tournament of the Towns
Today I present three problems from the 41-st Tournament of the Towns that I liked: an easy one, one that reminds me of the Collatz conjecture, and a hard one.
Problem 1 (by Aleksey Voropayev). A magician places all the cards from the standard 52-card deck face up in a row. He promises that the card left at the end will be the ace of clubs. At any moment, an audience member tells a number n that doesn’t exceed the number of cards left in the row. The magician counts the nth card from the left or right and removes it. Where does the magician need to put the ace of clubs to guarantee the success of his trick?
Problem 2 (by Vladislav Novikov). Number x on the blackboard can be replaced by either 3x + 1 or ⌊x/2⌋. Prove that you can use these operations to get to any natural number when starting with 1.
Share:Problem 3 (by A. Gribalko). There are 2n consecutive integers written on a blackboard. In one move, you can split all the numbers into pairs and replace every pair a, b with two numbers: a + b and a − b. (The numbers can be subtracted in any order, and all pairs have to be replaced simultaneously.) Prove that no 2n consecutive integers will ever appear on the board after the first move.
Sanjay:
Either end of the row of 52 cards.
30 December 2021, 1:59 amGennardo:
Problem 1: Put the card at one of the ends. Count the cards from this end if the audience tells a number bigger than 1
and from the other end when the audience say 1
In all other cases the magician loses against the best strategy of the audience. Assume he has put his card at position 14.
2 February 2022, 5:12 pmThen the audience always tells 15 so his card always remains at position 14. When 27 cards are left the audience tells 14 and the
magician loses.
Gennardo:
Problem 2: Call a number reachable, if it can be reached by the algorithm starting with 1. All numbers reached by the algorithm starting with another reachable number as a seed are of course reachable, too.
Th: The numbers 1, 2, 3, 4, …, 3n-1, 3n are reachable for every n
2 February 2022, 6:55 pmProof by induction:
base case n=2: 1, 2, 3, 4, 5 and 6 are all reachable (1–>1, 1–>4–>2, 1–>4–>13–>6–>3, 1–>4, 1–>4–>13–>40–>20–>10–>5, 1–>4–>13–>6) This enfolds the base case n=1. We need n=2 in the base case too because the step case won’t work with n=1
step case: Let 1, 2, 3, 4, …, 3n-1, 3n be reachable (n>1)
1. n ist reachable and the algorithm reaches 3n+1 with one (3x+1)-step so 3n+1 is reachable
2. 2n+1 ist less than or equal to 3n thus reachable and one (3x+1)-step with this seed gives 6n+4 and one (ceil(x/2))-step on 6n+4 gives 3n+2 therefore 3n+2 is reachable
3. 2n+2 ist less than or equal to 3n (here we need n>1) thus reachable and one (3x+1)-step with this seed gives 6n+7 and one (ceil(x/2))-step on 6n+7 gives ceil(3n+3.5) = 3n+3 thus 3n+3 is reachable
Gennardo:
Replace ceil() by floor() in my proof. Also n=2 in the base case of the induction is superfluous, Although we would have 2n+2 = 4 in the 3rd part of the step case which is not covered by the induction hypothesis and thus needs not to be reachable, we would have proven that 4 is reachable in the 1st part of the step case
3 February 2022, 2:30 am