Solutions to Technical Problems from April 2

Apr. 17, 2015

• Facebook
• Twitter
• Reddit
• Email
• Print

Solutions to Technical Problems from April 2

Problem 1

Alice and Bob alternately mark the squares of a 4×4 square grid, with Alice going first. If a 2×2 sub-grid is completely marked after a player’s turn, then he or she loses. Who can force a win, and what is the winning player’s strategy?

Solution. Bob can guarantee a win with the following strategy. If Alice marks the ith square of a row, Bob marks the ith square of the row two rows away (e.g. Bob plays in the third row if Alice plays in the first and Bob plays in the second row if Alice plays in the fourth). If Bob were ever to complete a 2×2 sub-grid, some casework shows that a 2×2 sub-grid must already have been completed. Therefore Bob can never be the first player to complete a 2×2 sub-grid and will always win with this strategy.

Problem Source: Problem Solving Strategies by Arthur Engel

Problem 2

A lattice point is a point with integer coordinates. Find the smallest positive integer n such that given any n lattice points in three-dimensional space, there are some two of these n points such that the segment joining them passes through another lattice point.

Solution. The answer is n = 9. First we show that any 9 lattice points (x₁, y₁, z₁), (x₂, y₂, z₂), …, (x₉, y₉, z₉) in three dimensional space have the desired property. If e denotes even and o denotes odd, then each point is of one of the eight forms (e, e, e), (e, e, o), (e, o, e), (e, o, o), (o, e, e), (o, e, o), (o, o, e) or (o, o, o). Since there are 9 > 8 points, some two points (x_i, y_i, z_i) and (x_j, y_j, z_j) must be of the same form i.e. all of their coordinates must have the same parity. The midpoint of these two points must also be lattice point and therefore the segment joining them passes through another lattice point. To see that n must be at least 9, consider the unit cube of points with all of their coordinates equal to either 0 or 1. No segment joining any two of these points passes through another lattice point.

Problem Source: Brilliant.org

Problem 3

There are 30 students, each of whom is either honest or a liar, sitting at a round table. John, a teacher at their school, does not know who is honest and who is a liar, but he is looking to find an honest student. John asks each of them whether their right neighbor is honest or a liar. An honest student always answers correctly, while a liar can answer either correctly or incorrectly. John knows that the number of liars does not exceed L. What is the largest possible value of L for which John will always be able to find a student who he can deduce is honest?

Solution. The answer is L = 8. If there are at most L = 8 liars, then John can deduce that the rightmost student in the longest contiguous string C of students who call their neighbors honest must be honest.

Suppose there is a situation where this strategy does not work. Let k denote the number of liars among the set S of students called liars and the students to the left of students called liars. Note that if a student calls the student to his or her right a liar, either that student or the student to his or her right must be a liar. Therefore k is at least half the number of students in S and therefore there are at most 2k students who call their neighbors liars. Thus there are at least 30 – 2k students who call their neighbors honest. Now consider a contiguous string of students who call their neighbors honest. The first student in this string must have been called a liar and thus either that student or the student to his or her left must be one of the liars counted in k. This implies that the number of contiguous strings of students who call their neighbors honest is at most k. Therefore the longest continuous string C must have length at least (30 – 2k)/k. If the rightmost student in this string were a liar, then the second rightmost student must also be a liar, as must be the third rightmost student. Continuing this logic yields that all students in C must be liars if the rightmost student were a liar. Therefore there must be at least (30 – 2k)/k + k liars which is at least 9 for integers k (minimized when k = 5, 6). This situation is therefore not possible since there are at most L = 8 liars. This proves that John’s strategy must work.

To see that there is no strategy for L at least 9, consider the case in which every fifth student around the table is called a liar and the rest are called honest. It is possible that everyone tells the truth (that all six students called liars are liars) and therefore John cannot deduce that anyone called a liar is honest. It is also possible that any four consecutive students called honest are liars, the student after them called a liar is actually honest and that everyone else is called what they are. This would require a total of nine liars and is possible as long as L is at least 9. Therefore any student called honest could actually be a liar and there is no strategy where John can deduce that someone called honest is actually honest.

Problem Source: Russian Math Olympiad 1993

Problem 4

Sarah is playing a game similar to the board game Rush Hour on a board consisting of an m×n square grid, where m and n are odd positive integers. The m×n square board is initially tiled with non-overlapping dominos such that only the upper-right square of the board is uncovered. Sarah is allowed to slide dominos into the single uncovered square and, in this way, move the uncovered square around the board. Prove that where Sarah can move the uncovered square does not depend on the initial tiling of the board.

Solution. Label the rows down the square grid from 1 to m and the columns from 1 to n from left to right. Call a square odd if it has coordinates (x, y) where x and y are both odd integers. It will be proven that regardless of how the square grid is tiled, Sarah can move the uncovered square exactly to the odd squares in the grid.

Note that in any given move, Sarah moves the uncovered square exactly two units in one direction. Therefore since the uncovered square begins on the odd square (1, n), it only ever occupies odd squares. Now it will be shown that every odd square is reachable. Consider an odd square A and the domino covering A. The short end of this domino not bordering A borders another odd square B. Note that if B is ever empty, then Sarah can slide the domino into B, leaving A uncovered. For all such pairs A and B in the square grid, draw an arrow from the center of A to the center of B. Now every odd square other than the starting position (1, n) of the grid has exactly one arrow leaving it. Beginning at an arbitrary odd square C of the grid, follow the arrows beginning at this square until either there is no arrow to follow or we arrive at a square we have visited before. If there is no arrow to follow, we must be at the starting position (1, n) and the sequence of odd squares along the arrows we followed in reverse order gives a path along which Sarah can move the uncovered square from (1, n) to C. Otherwise there must exist a cycle of arrows, which will be shown to be impossible. Note that it suffices to prove that a cycle of arrows is impossible since then there must be a sequence of moves leaving the uncovered square in C for all odd squares C.

Suppose that there is a cycle of arrows. Let the value of the cycle be the number of unit squares of the grid completely contained inside the cycle. We note that the value of a cycle must always be odd. To see this, note that any cycle can be obtained as the perimeter of a region R obtained iteratively as follows: start with a 2×2 square with vertices at the centers of four odd squares and iteratively add more of these 2×2 squares along the perimeter of the region. The initial 2×2 cycle has value 1, and some casework shows that each 2×2 square added to the region increases the value of the cycle either by 2 or 4. Therefore the value of any cycle is odd. However, since the m×n square grid has been tiled by dominos, the squares inside any cycle must also be tiled by dominos and therefore even in number. This is a contradiction and therefore no cycle of arrows could have existed to begin with.

Problem Source: Russian Math Olympiad 1997

Compiled and edited by Matthew Brennan.