tceic.com

学霸学习网 这下你爽了

学霸学习网 这下你爽了

COMBINATORICS TEST

This test consists of 10 short-answer problems to be solved individually in 50 minutes. Problems will be weighted with point values after the contest based on how many competitors solve each problem. There is no penalty for guessing. No translators, books, notes, slide rules, calculators, abaci, or other computational aids are permitted other than the of?cial translation sheets. Similarly, graph paper, rulers, protractors, compasses, and other drawing aids are not permitted. Our goal is that a closed form answer equivalent to the correct answer will be accepted. However, we do not always have the resourses to determine whether a complicated or strange answer is equivalent to ours. To assist us in awarding you all the points that you deserve, you answers should be simpli?ed as much as possible. Answers must be exact unless otherwise speci?ed. Correct mathematical notation must be used. No partial credit will be given unless otherwise speci?ed. If you believe the test contains an error, please submit your protest in writing to Science Center 109 during lunchtime. Enjoy!

15th Annual Harvard-MIT Mathematics Tournament

Saturday 11 February 2012

Combinatorics Test

1. In the game of Minesweeper, a number on a square denotes the number of mines that share at least one vertex with that square. A square with a number may not have a mine, and the blank squares are undetermined. How many ways can the mines be placed in this con?guration? 2 1 2

2. Brian has a 20-sided die with faces numbered from 1 to 20, and George has three 6-sided dice with faces numbered from 1 to 6. Brian and George simultaneously roll all their dice. What is the probability that the number on Brian’s die is larger than the sum of the numbers on George’s dice? 3. In the ?gure below, how many ways are there to select 5 bricks, one in each row, such that any two bricks in adjacent rows are adjacent?

4. A frog is at the point (0, 0). Every second, he can jump one unit either up or right. He can only move to points (x, y) where x and y are not both odd. How many ways can he get to the point (8, 14)? 5. Dizzy Daisy is standing on the point (0, 0) on the xy-plane and is trying to get to the point (6, 6). She starts facing rightward and takes a step 1 unit forward. On each subsequent second, she either takes a step 1 unit forward or turns 90 degrees counterclockwise then takes a step 1 unit forward. She may never go on a point outside the square de?ned by |x| ≤ 6, |y| ≤ 6, nor may she ever go on the same point twice. How many di?erent paths may Daisy take? 6. For a permutation σ of 1, 2, . . . , 7, a transposition is a swapping of two elements. (For instance, we could apply a transposition to the permutation 3, 7, 1, 4, 5, 6, 2 and get 3, 7, 6, 4, 5, 1, 2 by swapping the 1 and the 6.) Let f (σ) be the minimum number of transpositions necessary to turn σ into the permutation 1, 2, 3, 4, 5, 6, 7. Find the sum of f (σ) over all permutations σ of 1, 2, . . . , 7. 7. You are repeatedly ?ipping a fair coin. What is the expected number of ?ips until the ?rst time that your previous 2012 ?ips are ‘HTHT...HT’ ? 8. How many ways can one color the squares of a 6x6 grid red and blue such that the number of red squares in each row and column is exactly 2? 9. A parking lot consists of 2012 parking spots equally spaced in a line, numbered 1 through 2012. One by one, 2012 cars park in these spots under the following procedure: the ?rst car picks from the 2012 spots uniformly randomly, and each following car picks uniformly randomly among all possible choices which maximize the minimal distance from an already parked car. What is the probability that the last car to park must choose spot 1? 10. Jacob starts with some complex number x0 other than 0 or 1. He repeatedly ?ips a fair coin. If the 1 nth ?ip lands heads, he lets xn = 1 ? xn?1 , and if it lands tails he lets xn = xn?1 . Over all possible choices of x0 , what are all possible values of the probability that x2012 = x0 ?

15th Annual Harvard-MIT Mathematics Tournament

Saturday 11 February 2012

Combinatorics Test

Name School Team

Team ID#

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Score: