Technical Problems
Technical Problems
Technical Problems is a new weekly column consisting of puzzles and math problems intended to be accessible to undergraduates of all majors. The column will feature new problems each week as well as solutions to problems posed in previous weeks. If you are interested in having one or more of your solutions published in the column, please send them to general@tech.mit.edu.
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?
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.
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?
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.
Compiled and edited by Matthew Brennan.