Technical Problems 5

Technical Problems is a weekly column consisting of puzzles and math problems intended to be accessible to undergraduates of all majors. Solutions are posted two weeks later online. 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

You have six charged batteries, six uncharged batteries and a radio that requires two charged batteries to work. You are allowed to try out nine pairs of batteries and each time check if the radio works. Is there a way to guarantee that you will be able to find a pair of charged batteries?

Problem 2

You have four balls, each with a positive integer mass (in grams), and a balance which reports the signed difference between the weight of the contents in its left pan and in its right pan. You are allowed to use the balance four times. The balance might malfunction and give you an answer that is off by 1 gram; however, this can occur at most once. Can you always figure out the masses of all four balls?

Problem 3

David has colored the squares of a 2015-by-2015 square grid red and blue. A path is a sequence of squares such that consecutive squares in the path share an edge and no other pairs of squares in the path share an edge. Prove that if the red squares form a single path and the blue squares form a single path, then one of these two paths must begin or end in the center of the 2015-by-2015 grid.

*Compiled and edited by Matthew Brennan.*