The Lomonosov Tournament: Games Contest
A combinatorial games section? At a math competition? I have never heard of it before. But here it is, at the Lomonosov Tournament. The first problem is from the 2012 Tournament (the link is to a Russian version). The problem is by Alexander Shapovalov. I picked it for its elegance and simplicity.
A rectangular band. You have a paper rectangle of size m by n with grid lines, where both m and n are greater than 1. Two players play the following game. The first player cuts the rectangle along any grid line into two rectangles. The next player picks one of the rectangles and cuts it again along a grid line, and so on. The winner is the player who, after their move, can arrange all the rectangles into a band of width 1. Which player is guaranteed a win regardless of the moves of their partner? Consider two cases.
- One of the numbers, m or n, is even;
- Both m and n are odd.
The next problem, by I. Raskin, is from the 2015 Tournament (in Russian). The problem is about fruits, and I know a lot of great puzzles with bananas and oranges, so I immediately got attracted to this one.
The original version had three types of fruit starting with the letters a, b, and c in Russian. They were oranges, bananas, and plums. I reused bananas and replaced oranges with apples, but I got stuck on the letter c. The players in this game eat their fruits, so using cantaloupes seemed like overkill. Plus, I am on a diet, so I decided on cherries.
Fruits. There are a apples, b bananas, and c cherries on the table. Two players play a game where one move consists of eating two different fruits. The person who can’t move loses. Assuming the players use their best strategies, would the first or the second player win in the following cases?
- a = 1 (the answer might depend on the values of b and c);
- a = 6, b = 8, c = 10;
- a = 7, b = 9, c = 15;
- a = 19, b = 20, c = 21.
The last problem is from the 2012 Tournament (in Russian). It has great sentimental value for me, as it was created by John Conway. It also reminds me of the famous Frobenius (chicken McNugget) problem.
Coin mintage. Once upon a time, in a faraway kingdom, two treasurers were minting coins. They decided to make it into a game, taking turns minting coins. Each turn, the player chooses a particular integral denomination and mints an infinite supply of coins of this denomination. The rules of the game forbid choosing a new denomination that can be paid with the existing coins. The treasurer who is forced to mint a coin of denomination 1 loses.
- Prove that if the first treasurer starts with denomination 2 or 3, s/he loses.
- Is it profitable for the first treasurer to start with denomination 4?
- Is it profitable for the first treasurer to start with denomination 6?
- Suppose the first treasurer minted coins of denomination 5, and the second treasurer of denomination 6. What is the winning strategy for the first treasurer after that?
- Suppose the first treasurer minted coins of denomination 5, and the second treasurer of denomination k. Prove that the largest denomination available for minting is 4k − 5.
- Prove that the first treasurer can win by starting with denomination 5. (Hint: Suppose the second treasurer replied with denomination k, and the first treasurer minted 4k − 5 after that. If this strategy wins, the problem is solved. However, if after that, the second treasurer wins by minting denomination m, then minting denomination 4k − 5 was the wrong move. What was the right move?)
Share:
Sanandan Swaminathan:
Coin Mintage:
Let A be the first treasurer and B be the second treasurer.
Part 1: If A starts by minting 2, then B will mint 3. Denomination 2 covers all even numbers, while 3 + 2n, where n >= 0, covers all odd numbers greater than 1. Thus, A will be forced to pick 1 and lose. On the other hand, if A starts by minting 3, then B will mint 2. Again, all numbers greater than 1 will be covered at this point, and A will be forced to pick 1 and lose.
Part 2: A will lose if he starts the game by minting 4. B can counter by minting 7. A won’t next pick 2 or 3 since that’s a losing move as we’ve seen in part 1. If A next picked either 5 or 6, B would pick the other. The set {4,5,6,7) covers all integers >= 4. So A would be forced to pick 2 or 3, and lose. Hence, A would want to pick a denomination > 7. Note that, with {4,7} already minted, the first treasurer to mint from either {2,3} or from {5,6} loses.
Since 4 and 7 are relatively prime, by the Chicken McNuggets theorem, the largest number that cannot be formed as a linear combination of 4 and 7 is 4*7 – 4 – 7 = 17. With the first two picks being 4 and 7, we can see that the only denominations > 7 that are not covered are {9, 10, 13, 17}. Given that picking from {5,6} or (2,3} is a losing move, A has four options for the next move:
a) If A next picks 9, then 13 also gets covered. So, B would pick 10 (and 17 would also get covered). This would force A to next pick from either {5, 6} or {2, 3}, a losing move.
b) If A picks 10, then 17 also gets covered. So, B would pick 9 (and 13 would also get covered). This would force A to next pick from either {5, 6} or {2, 3}, a losing move.
c) If A picks 13, B will pick 17. Whether A next picks 9 or 10, B will pick the other. This would force A to next pick from either {5, 6} or {2, 3}, a losing move.
d) If A picks 17, B will pick 13. Whether A next picks 9 or 10, B will pick the other. This would force A to next pick from either {5, 6} or {2, 3}, a losing move.
Thus, we can see that A starting the game by minting 4 is a losing move.
Part 4: If A starts with 5, and B then mints 6, then A can guarantee a win by next minting the Chicken Mcnuggets number 5*6 – 5 – 6 = 19. As we’ve seen in previous parts, at this point, both treasurers would want to avoid being the first to mint from {2,3} or {4,7}. Given that the denominations minted so far are {5,6,19}, the only numbers greater than 7 that B could target minting now are {8,9,13,14}.
a) If B mints 8, then 13 and 14 also get covered. So, A will next mint 9, forcing B to next pick from either {4,7} or {2, 3}, a losing move.
b) If B mints 9, then 14 also gets covered. So, A will next mint 8 (which also covers 13), forcing B to next pick from either {4,7} or {2, 3}, a losing move.
c) If B mints 13, then A will mint 14. Whether B next picks 8 or 9, A will pick the other. This would force B to next pick from either {4,7} or {2, 3}, a losing move.
d) If B mints 14, then A will mint 13. Whether B next picks 8 or 9, A will pick the other. This would force B to next pick from either {4,7} or {2, 3}, a losing move.
Thus, we can see that A will always win if the game starts with 5 followed by 6. A will win if he mints 19 next. In fact, this is true even if the game starts with 6 followed by 5. By minting 19 next, A would guarantee a win.
Part 5: If A starts by minting 5, B is not allowed to mint any multiple of 5. Also, B would not mint 1. Hence, any denomination k that B chooses would be relatively prime to 5. So, by the Chicken Mcnuggets theorem, the largest denomination available for minting at this point is 5*k – 5 – k = 4k-5.
13 September 2022, 12:40 amSanandan Swaminathan:
Fruits:
Let the first player be A and the second player be B.
Part 2 (a = 6, b = 8, c = 10): The second player (player B) is guaranteed to win. All three heaps have an even number of the respective fruits. In the first move, A will necessarily make them into two odd heaps and one even heap (in some order). Player B can simply turn the heaps back into three even heaps (by eating a fruit from each of the two odd heaps). B would do this in every turn. In every turn, A would be faced with three even heaps, and A will necessarily turn them into two odds and one even. Odd heaps have at least 1 fruit. Since A would always leave two odd heaps on the table, B will always be able to consume a fruit from each of those two odd heaps. So, B can never lose. Since the game will terminate at some point, player A is guaranteed to lose.
Part 4 (a = 19, b = 20, c = 21: The first player (player A) is guaranteed to win. There are two odd heaps and one even heap. In the very first move, A will take a fruit from each of the two odd heaps. So, player B will face three even heaps. From part 2, we already know that the second player wins a game with three even heaps. Here, player A would be the second player in the new game of three even heaps after A’s very first turn. Hence, player A is guaranteed to win.
13 September 2022, 1:06 amSanandan Swaminathan:
Rectangular band (m x n grid):
Part 1 (one of the numbers, m or n, is even, and the other could be odd or even): Player1 is guaranteed to win. Player1 can cut the grid into two congruent grids (of half the area) since one of the dimensions is even (even number of squares along that dimension). Let the two halves be H1 and H2, and treat them as distinct sets for the rest of the game. Now, whatever cut player2 makes in H1 or H2, player1 can make the exact same cut in the other half. If player2 can make a cut, then player1 can always make the same cut in the other half. Basically, player1 is mirroring player2’s moves. If player2 makes the last cut needed or possible in H1 or H2, then player1 would make the same cut in the other half to complete the game’s objective. Thus, player1 is guaranteed to win.
Part 2 (both m and n are odd): Player2 is guaranteed to win. As we’ve seen in part 1, when at least one of the grid dimensions is even at the start of a game, then the first player is guaranteed to win. In the first turn in the odd x odd game, player1 will necessarily need to split the grid into two sub-grids such that one of them is an even x odd sub-grid, and the other is an odd x odd sub-grid. Player2 should then split the even x odd sub-grid into two congruent halves (just like player1 did in part 1). If player1 then makes a cut in one of those halves, then player2 should make the exact same cut in the other half. On the other hand, if player1 cuts the other odd x odd sub-grid at any stage, it would necessarily get split into yet another even x odd sub-grid and an odd x odd sub-grid. In this case, player2 should immediately cut the new even sub-grid into two equal halves. In any given turn of player1, s/he would either be making a cut in some half of an old even sub-grid, or producing a new even sub-grid (with a leftover odd x odd sub-grid). In any turn, if player1 makes a cut in some half of some old even sub-grid, then player2 should counter by making the exact same cut in the other half of that SPECIFIC even sub-grid. If player1 produces a new even sub-grid at any stage, then player2 should simply cut the new even sub-grid into two congruent halves. By this strategy, player2 will win every even sub-grid ever produced during the game by player1. Eventually, there will be no more new even sub-grids for player1 to produce. Thus, player2 is guaranteed to win the odd by odd game.
13 September 2022, 3:02 amTanya Khovanova's Math Blog » Blog Archive » The Lomonosov Tournament: Games Contest - New Marathi Live:
[…] Source link […]
16 September 2022, 3:19 am