tceic.com

# 第13届哈佛-MIT校际数学竞赛组合数学试题

13th Annual Harvard-MIT Mathematics Tournament
Saturday 20 February 2010

Combinatorics Subject Test
1. [2] Let S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. How many (potentially empty) subsets T of S are there such that, for all x, if x is in T and 2x is in S then 2x is also in T ? 2. [3] How many positive integers less than or equal to 240 can be expressed as a sum of distinct factorials? Consider 0! and 1! to be distinct. 3. [4] How many ways are there to choose 2010 functions f1 , . . . , f2010 from {0, 1} to {0, 1} such that f2010 ? f2009 ? · · · ? f1 is constant? Note: a function g is constant if g(a) = g(b) for all a, b in the domain of g. 4. [4] Manya has a stack of 85 = 1 + 4 + 16 + 64 blocks comprised of 4 layers (the kth layer from the top has 4k?1 blocks; see the diagram below). Each block rests on 4 smaller blocks, each with dimensions half those of the larger block. Laura removes blocks one at a time from this stack, removing only blocks that currently have no blocks on top of them. Find the number of ways Laura can remove precisely 5 blocks from Manya’s stack (the order in which they are removed matters).

5. [5] John needs to pay 2010 dollars for his dinner. He has an unlimited supply of 2, 5, and 10 dollar notes. In how many ways can he pay? 6. [5] An ant starts out at (0, 0). Each second, if it is currently at the square (x, y), it can move to (x ? 1, y ? 1), (x ? 1, y + 1), (x + 1, y ? 1), or (x + 1, y + 1). In how many ways can it end up at (2010, 2010) after 4020 seconds? 7. [6] For each integer x with 1 ≤ x ≤ 10, a point is randomly placed at either (x, 1) or (x, ?1) with equal probability. What is the expected area of the convex hull of these points? Note: the convex hull of a ?nite set is the smallest convex polygon containing it. 8. [6] How many functions f from {?1005, . . . , 1005} to {?2010, . . . , 2010} are there such that the following two conditions are satis?ed? ? If a < b then f (a) < f (b). ? There is no n in {?1005, . . . , 1005} such that |f (n)| = |n|. 9. [7] Rosencrantz and Guildenstern are playing a game where they repeatedly ?ip coins. Rosencrantz wins if 1 heads followed by 2009 tails appears. Guildenstern wins if 2010 heads come in a row. They will ?ip coins until someone wins. What is the probability that Rosencrantz wins? 10. [8] In a 16 × 16 table of integers, each row and column contains at most 4 distinct integers. What is the maximum number of distinct integers that there can be in the whole table?