Technical Problems 2
Technical Problems 2
Update: the solutions to these problems have been posted.
Technical Problems is a weekly column consisting of puzzles and math problems intended to be accessible to undergraduates of all majors. The column features new problems each week as well as solutions to the problems posed two weeks earlier. The solutions to last week’s problems will be included in the column next week. 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
There are 100 passengers about to board a plane with 100 seats. Each passenger is assigned a distinct seat on the plane. The first passenger who boards has forgotten his seat number and sits in a randomly selected seat on the plane. Each passenger who boards after him either sits in his or her assigned seat, if it is empty, or sits in a randomly selected seat from the unoccupied seats otherwise. What is the probability that the last passenger to board the plane sits in her assigned seat?
Problem 2
Four congruent right triangles are given. Adriana picks one of them and cuts it along its altitude, obtaining two new right triangles. She repeats this operation several times. Prove that no matter how Adriana performs the cuts, she can always find among the triangles two that are congruent.
Problem 3
Fix positive integers n and k where k is at least 2. A list of n integers is written in a row on a blackboard. Alice can choose a contiguous block of integers, and Bob will either add 1 to all of them or subtract 1 from all of them. Alice has no control over what Bob does, but she can repeat this step as often as she likes, possibly adapting her selections based on what Bob does. Prove that Alice can ensure that after a finite number of steps, at least n – k + 2 numbers on the blackboard are simultaneously divisible by k.
Compiled and edited by Matthew Brennan.