Harvard-MIT Mathematics Tournament March 15. 2003 Individual Round: Combinatorics Subject Test You have 2003 switches, numbered from 1 to 2003, arranged in a circle. Initially, each switch is either on or OFF, and all configurations of switches are equally likely. You perform the following operation: for each switch S, if the two switches next to S were tially in the same position, then you set s to oN; otherwise, you set s to OFF What is the probability that all switches will now be ON? 2. You are given a 10 x 2 grid of unit squares. Two different squares are adjacent if they share a side. How many ways can one mark exactly nine of the squares so that no two marked squares are adjacent? 3. Daniel and Scott are playing a game where a player wins as soon as he has two points more than his opponent. Both players start at par, and points are earned one at a time. If Daniel has a 60% chance of winning each point, what is the probability that he will win the game? 4. In a certain country, there are 100 senators, each of whom has 4 aides. These senators and aides serve on various committees. A committee may consist either of 5 senators of 4 senators and 4 aides, or of 2 senators and 12 aides. Every senator serves on 5 committees, and every aide serves on 3 committees. How many committees are there altogether? 5. We wish to color the integers 1, 2, 3, .., 10 in red, green, and blue, so that no two numbers a and b, with a-b odd, have the same color. We do not require that all three colors be used. )In how many ways can this be done? 6. In a classroom, 34 students are seated in 5 rows of 7 chairs. The place at the center of the room is unoccupied. A teacher decides to reassign the seats such that each student will occupy a chair adjacent to his/her present one(i.e. move one desk forward, back left or right). In how many ways can this reassignment be made? 7. You have infinitely many boxes, and you randomly put 3 balls into them. The boxes are labeled 1, 2, ... Each ball has probability 1/2n of being put into box n. The balls are placed independently of each other. What is the probability that some box will contain at least 2 balls? 8. For any subset SC1, 2,., 151, a number n is called an "anchor"for S if n and n+S are both members of S, where S denotes the number of members of S. Find the average number of anchors over all possible subsets SC(1, 2,., 15) At a certain college, there are 10 clubs and some number of students. For any two different students, there is some club such that exactly one of the two belongs to that club. For any three different students, there is some club such that either exactly one or all three belong to that club. What is the largest possible number of students?Harvard-MIT Mathematics Tournament March 15, 2003 Individual Round: Combinatorics Subject Test 1. You have 2003 switches, numbered from 1 to 2003, arranged in a circle. Initially, each switch is either ON or OFF, and all configurations of switches are equally likely. You perform the following operation: for each switch S, if the two switches next to S were initially in the same position, then you set S to ON; otherwise, you set S to OFF. What is the probability that all switches will now be ON? 2. You are given a 10 × 2 grid of unit squares. Two different squares are adjacent if they share a side. How many ways can one mark exactly nine of the squares so that no two marked squares are adjacent? 3. Daniel and Scott are playing a game where a player wins as soon as he has two points more than his opponent. Both players start at par, and points are earned one at a time. If Daniel has a 60% chance of winning each point, what is the probability that he will win the game? 4. In a certain country, there are 100 senators, each of whom has 4 aides. These senators and aides serve on various committees. A committee may consist either of 5 senators, of 4 senators and 4 aides, or of 2 senators and 12 aides. Every senator serves on 5 committees, and every aide serves on 3 committees. How many committees are there altogether? 5. We wish to color the integers 1, 2, 3, . . . , 10 in red, green, and blue, so that no two numbers a and b, with a − b odd, have the same color. (We do not require that all three colors be used.) In how many ways can this be done? 6. In a classroom, 34 students are seated in 5 rows of 7 chairs. The place at the center of the room is unoccupied. A teacher decides to reassign the seats such that each student will occupy a chair adjacent to his/her present one (i.e. move one desk forward, back, left or right). In how many ways can this reassignment be made? 7. You have infinitely many boxes, and you randomly put 3 balls into them. The boxes are labeled 1, 2, . . .. Each ball has probability 1/2 n of being put into box n. The balls are placed independently of each other. What is the probability that some box will contain at least 2 balls? 8. For any subset S ⊆ {1, 2, . . . , 15}, a number n is called an “anchor” for S if n and n + |S| are both members of S, where |S| denotes the number of members of S. Find the average number of anchors over all possible subsets S ⊆ {1, 2, . . . , 15}. 9. At a certain college, there are 10 clubs and some number of students. For any two different students, there is some club such that exactly one of the two belongs to that club. For any three different students, there is some club such that either exactly one or all three belong to that club. What is the largest possible number of students? 1