practice problems
Q1. Ten 1's and ten 2's are written on a blackboard. In one turn, a player may erase any two figures. If the two figures erased are identical, they are replaced with a 2. If they are different, they are replaced with a 1. The first player wins if a 1 is left at the end, and the second player wins if a 2 is left.
S1.
Only P2 can win.
Why?
1. There are total 19 moves since in every move the count of total numbers goes down by 1. At the end we will have a single number.
2. Let's say P1 plays the first move, then he will also play the 19th move. Let C1, C2 denote count of 1s and 2s at any given time.
3. For P1 to win, after the 18th move we need C1 = 1, C2 = 1. For P2 to win C1 = 0, C2 = 2 or C1 = 2, C2 = 0.
4. Let's focus on P1's win. That means that in the initial 18 moves both C1 and C2 should decrease by 9 each.
5. What happens in every move?
Case 1: Two 1s replaced by 2 => C1 -= 2, C2 += 1
Case 2: Two 2s replaced by 2 => C1 += 0, C2 -= 1
Case 3: One 1 and One 2 replaced by 1 => C1 += 0, C2 -= 1
So C1 changes by 0 or 2 and C2 changes by +1 or -1.
For P1 to win C1 has to change by 9 which is not possible with changes of 0,2
Hence P1 cannot win.
For P2 to win there are two cases:
C1 -10, C2 -8 or C1 -8, C2 -10. Both are possible.
So only P2 can win.
Q2. There are three piles of stones. The first contains 50 stones, the second 60 stones, and the third 70. A turn consists in dividing each of the piles containing more than one stone into two smaller piles. The player who leaves piles of individual stones is the winner.
S2.
If the opponent gets 3 as the largest pile, I would win.
Because he will have to split it as 2,1 and then I would make it 1,1.
Similarly for 7.
Looks like this pattern will repeat for all 2^k - 1.
So, a player has to always focus on the largest pile and ensure that the opponent gets the largest pile which has 2^k - 1 stones. And split the other piles as evenly as possible.
Here the player 1 can simply divide the first pile in 63,7 since 63 = 2^6 - 1.
This will ensure player 2's loss.
Q3. Two players take turns putting pennies on a round table, without piling one penny on top of another. The player who cannot place a penny loses.
S3.
Player 1 should place the penny in the center of the table.
Now whatever player 2 picks to place the penny, player 1 will place his penny diametrically opposite to it. So player 1 can never run out of space, but player 2 can. So player 1 will always win.
Q4. Given a 10×10 chessboard, two players take turns covering pairs of squares with dominoes. Each domino consists of a rectangle 1 square in width and 2 squares in length (which can be held either way). The dominoes cannot overlap. The player who cannot place a domino loses.
S4.
Let's see it on a smaller 4x4 1-indexed grid.
Since the dimension is even, the grid doesn't have a square as its center(unlike and odd-sized grid).
It has a point center which is the center of the center 4 squares (2,2) (2,3) (3,2) (3,3).
If player 2 mimics player 1's moves reflected 180 degree against this point center then player 2 will always have a move and eventually player 1 will run out of moves.
For e.g. see this game play:
Initial empty:
_ _ _ _
_ _ _ _
_ _ _ _
_ _ _ _
First move:
1 1 _ _
_ _ _ _
_ _ _ _
_ _ _ _
1 1 _ _
_ _ _ _
_ _ _ _
_ _ 2 2
How is the 180 degree reflection calculated:
(r,c) goes to (N+1-r, N+1-c) so here it becomes (5-r),(5-c)
1 1 _ _
1 _ _ _
1 _ _ _
_ _ 2 2
then:
1 1 _ _
1 _ _ 2
1 _ _ 2
_ _ 2 2
then:
1 1 1 1
1 _ _ 2
1 _ _ 2
_ _ 2 2
then:
1 1 1 1
1 _ _ 2
1 _ _ 2
2 2 2 2
then:
1 1 1 1
1 1 1 2
1 _ _ 2
2 2 2 2
then:
1 1 1 1
1 1 1 2
1 2 2 2
2 2 2 2
And see how to find reflection geometrically for 4,3
Take the center of square at 4,3 and join with the center of the grid.
That means you moved 0.5 west and 1.5 north.
Now repeat these operations in reverse order on the other side of the grid center.
1.5 north and 0.5 west.
You land in 2,1.
If you join these triangles you will see that AA' is a straight line and OAB and OA'B' are congruent.
Q5. Start with a pile of n chips. A and B move alternately. At his first move, A takes any number s so that 0<s<n. From then on, a player may take any number which is a divisor of the number of chips taken at the preceding move. The winner is the one who makes the last move. Which initial positions are winning for A or B?
S5.
Assuming n >= 2.
First thought: if 'n' is odd and A takes 1 chip then all the subsequent moves will have to be 1 chip. And A will be the last to take the remaining 1 chip.
So for odd 'n' A should take 1 chip.
So you should never hand over odd number of chips to your opponent since he will simply take 1 chip and guaranteed to win.
n=2 B wins.
n=4
A will take 2, B takes 2 and wins.
n=6 A takes 2 and wins.
For n = 10,
A can't take odd number of chips so A can take 2,4,6,8.
If A takes 2, B is forced to take 2 and every move will be of 2 chips.
So A will take the last 2.
The final solution is this:
Case 1:
n is not a power of 2.
Every integer can be written as: 2^k.m where m is some odd number.
Let n = 2^k.m
A takes 2^k chips from this.
n = 2^k(m-1)
Now n has even higher power of 2 then earlier since (m-1) is even.
B has to take 2^q where q <= k
=>
n = 2^k(m-1) - 2^q = 2^q[2^(k-q).(m-1) - 1]
If B picks q = 0 => 1 chip, then he is handing over odd number to A and A wins.
If q >0,
then there are 2 sub cases:
sub case 1:
[2^(k-q).(m-1) - 1] is clearly odd but it's not 1.
Then A will repeat its strategy since the new number is 2^q.<odd != 1> and hand over new even number to B which has higher power of 2 than q.
sub case 2:
it is 1. then 2^q chips are remaining and A will take all 2^q since B took 2^q in the last move.
And A wins.
Case 2:
n is a power of 2.
So n = 2^k
Now A doesn't want to hand over an odd number to B.
So A will take 2^q.m where m is odd and 0 < q < k.
=> n = 2^q[2^(k-q) - m]
Now B has got n in the form where it is not a power of 2. So B will use the same rules as earlier and win.
Q6.
Arjun and Beth play a game in which they take turns removing one brick or two adjacent bricks from one "wall" among a set of several walls of bricks, with gaps possibly creating new walls. The walls are one brick tall. For example, a set of walls of sizes 4 and 2 can be changed into any of the following by one move:
(3,2),(2,1,2),(4),(4,1),(2,2), or (1,1,2).
Arjun plays first, and the player who removes the last brick wins. For which starting configuration is there a strategy that guarantees a win for Beth?
S6.
Winning strategy for Beth:
If game starts in a symmetrical state, i.e. there are even number of walls for each size.
For e.g. 4,4 or 2,4,2,4.
In that case Beth will simply mirror Arjun's moves and eventually Arjun will run out of moves.
Winning strategy for Arjun:
If the game starts with a single wall.
For e.g. a wall of size 1 or 2, Arjun will simply take the entire wall.
If it's more than 2 and odd sized, then Arjun will take 1 brick from the middle to force symmetry and then mirror.
For even sized wall, he will take 2 bricks from middle and force symmetry.
Q7.
S7.
If we add all permutations of abc, then we get:
(100 + 10 + 1)(2a + 2b + 2c) = 222(a+b+c)
Let a+b+c = k.
And let the original number abc = x.
=> 222.k = 3194 + x_____[1]
Now there are 2 ways to solve from here:
Method 1:
100 <= x <= 999
=> 3294 <= 222.k <= 4193
14.sth <= k <= 18.sth
=> k can be 15,16,17,18
Let's plug the values ok k in [1]:
k = 15 => x = 136, sum of digits != 15
Similarly, try all values of k, only k = 16 will work.
You will get x = 358 which has sum of digits = 16.
Method 2:
To avoid the calculations, let's take mod 9.
Why mod 9? Since x mod 9 = sum of digits of x mod 9.
=> 222.k = 3194 + x mod 9
=> 6.k = 8 + k mod 9
=> 5k = 8 mod 9
=> 10k = 16 mod 9
=> 1.k = 7 mod 9
=> k = 7 mod 9
So k can be 7,16,25...
Now look at this again:
3294 <= 222.k <= 4193
222*10 = 2220
222*20 = 4440
=> k is between 10 and 20 => k = 16
=> 222.16 = 3194 + x => x = 358.
Comments
Post a Comment