HARVARD-MIT MATHEMATICS TOURNAMENT. MARCH 15. 2003- GUTS ROUND 2 of at least one of the vertices a regular hexagon of side length 1 is within distance 16.8 What fraction of the area of [8] There are 10 cities in a state, and some pairs of cities are connected by roads. There are 40 roads altogether. A city is called a "hub" if it is directly connected to every other city. What is the largest possible number of hubs? 18. [8 Find the sum of the reciprocals of all the(positive)divisors of 144 HARVARD-MIT MATHEMATICS TOURNAMENT. MARCH 15. 2003- GUTS ROUND 19.[ 8] Let r, s, t be the solutions to the equation r+az2+b+c=0. What is the value of(rs)2+(st)2+(rt)2 in terms of a, b, and c? 20.[8 What is the smallest number of regular hexagons of side length 1 needed to com- pletely cover a disc of radius 1? [8]r and s are integers such that 3r>25-3 and 4s>r+12 What is the smallest possible value of r/s? HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 200 GUTS ROUND 22. 9 There are 100 houses in a row on a street. A painter comes and paints every house red. Then, another painter comes and paints every third house(starting with house number 3)blue. Another painter comes and paints every fifth house red(even if it already red), then another painter paints every seventh house blue, and so forth, alternating between red and blue, until 50 painters have been by. After this is finished ow many houses will be red? 23. 9 How many lattice points are enclosed by the triangle with vertices(0, 99),(5, 100) and(2003, 500)? Don't count boundary point [9 Compute the radius of the inscribed circle of a triangle with sides 15, 16, and 1 3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 16. [8] What fraction of the area of a regular hexagon of side length 1 is within distance 1 2 of at least one of the vertices? 17. [8] There are 10 cities in a state, and some pairs of cities are connected by roads. There are 40 roads altogether. A city is called a “hub” if it is directly connected to every other city. What is the largest possible number of hubs? 18. [8] Find the sum of the reciprocals of all the (positive) divisors of 144. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 19. [8] Let r, s, t be the solutions to the equation x 3 + ax2 + bx + c = 0. What is the value of (rs) 2 + (st) 2 + (rt) 2 in terms of a, b, and c? 20. [8] What is the smallest number of regular hexagons of side length 1 needed to completely cover a disc of radius 1? 21. [8] r and s are integers such that 3r ≥ 2s − 3 and 4s ≥ r + 12. What is the smallest possible value of r/s? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 22. [9] There are 100 houses in a row on a street. A painter comes and paints every house red. Then, another painter comes and paints every third house (starting with house number 3) blue. Another painter comes and paints every fifth house red (even if it is already red), then another painter paints every seventh house blue, and so forth, alternating between red and blue, until 50 painters have been by. After this is finished, how many houses will be red? 23. [9] How many lattice points are enclosed by the triangle with vertices (0, 99), (5, 100), and (2003, 500)? Don’t count boundary points. 24. [9] Compute the radius of the inscribed circle of a triangle with sides 15, 16, and 17. 3
HARVARD-MIT MATHEMATICS TOURNAMENT. MARCH 15. 2003- GUTS ROUND 25.9 Let ABC be an isosceles triangle with apex A. Let I be the incenter. If AI =3 and the distance fromI to bc is 2. then what is the length of bc? 26.9 Find all integers a such that a+6. r +28 is a perfect square 60 and 70, respectively. What is the smallest possible denominator of z +y? inators 27. 9 The rational numbers z and y, when written in lowest terms, have denom HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003--GUTS ROUND 28. [10 A point in three-space has distances 2, 6, 7, 8, 9 from five of the vertices of a regular octahedron. What is its distance from the sixth vertex? 29. 10 A palindrome is a positive integer that reads the same backwards as forwards such as 82328. What is the smallest 5-digit palindrome that is a multiple of 99? [10 The sequence a1, a2, a,, . . of real numbers satisfies the recurrence an-1+ 2an +1 Given that a1= l and ag=7, find as HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003- GUTS ROUND 31. [10 A cylinder of base radius 1 is cut into two equal parts along a plane passing through the center of the cylinder and tangent to the two base circles. Suppose that each piece's surface area is m times its volume. Find the greatest lower bound for possible values of m as the height of the cylinder varies 32.[10] If a, y, and z are real numbers such that 2x2+y2+22=2x-4y+2xz-5,find the maximum possible value of x-y+2 33. 10 We are given triangle ABC, with AB=9, AC= 10, and BC= 12, and a point D on BC. B and C are reflected in AD to B and C, respectively. Suppose that lines BC' and B'C never meet (i. e, are parallel and distinct ) Find BD 4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 25. [9] Let ABC be an isosceles triangle with apex A. Let I be the incenter. If AI = 3 and the distance from I to BC is 2, then what is the length of BC? 26. [9] Find all integers x such that x 2 + 6x + 28 is a perfect square. 27. [9] The rational numbers x and y, when written in lowest terms, have denominators 60 and 70, respectively. What is the smallest possible denominator of x + y? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 28. [10] A point in three-space has distances 2, 6, 7, 8, 9 from five of the vertices of a regular octahedron. What is its distance from the sixth vertex? 29. [10] A palindrome is a positive integer that reads the same backwards as forwards, such as 82328. What is the smallest 5-digit palindrome that is a multiple of 99? 30. [10] The sequence a1, a2, a3, . . . of real numbers satisfies the recurrence an+1 = a 2 n − an−1 + 2an an−1 + 1 . Given that a1 = 1 and a9 = 7, find a5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 31. [10] A cylinder of base radius 1 is cut into two equal parts along a plane passing through the center of the cylinder and tangent to the two base circles. Suppose that each piece’s surface area is m times its volume. Find the greatest lower bound for all possible values of m as the height of the cylinder varies. 32. [10] If x, y, and z are real numbers such that 2x 2 + y 2 + z 2 = 2x − 4y + 2xz − 5, find the maximum possible value of x − y + z. 33. [10] We are given triangle ABC, with AB = 9, AC = 10, and BC = 12, and a point D on BC. B and C are reflected in AD to B0 and C 0 , respectively. Suppose that lines BC0 and B0C never meet (i.e., are parallel and distinct). Find BD. 4
HARVARD-MIT MATHEMATICS TOURNAMENT. MARCH 15. 2003- GUTS ROUND 34.[12OK RA is a trapezoid with OK parallel to RA. If OK=12 and RA is a positive integer, how many integer values can be taken on by the length of the segment in the trapezoid, parallel to OK, through the intersection of the diagonals 35. [12] A certain lottery has tickets labeled with the numbers 1, 2, 3, .., 1000. The lottery is run as follows: first, a ticket is drawn at random. If the number on the ticket is odd the drawing ends; if it is even, another ticket is randomly drawn(without replacement) If this new ticket has an odd number, the drawing ends; if it is even, another ticket is randomly drawn(again without replacement ), and so forth, until an odd number is drawn. Then, every person whose ticket number was drawn (at any point in the process) wins a prize You have ticket number 1000. What is the probability that you get a prize? 36.[12 A teacher must divide 221 apples evenly among 403 students. What is the number of pieces into which she must cut the apples?(A whole uncut apple counts as one plece HARVARD-MIT MATHEMATICS TOURNAMENT. MARCH 15. 2003- GUTS ROUND 37. 15 A quagga is an extinct chess piece whose move is like a knight's, but much longer it can move 6 squares in any direction(up, down, left, or right)and then 5 squares in a perpendicular direction. Find the number of ways to place 51 quaggas on an 8 8 chessboard in such a way that no quagga attacks another.( Since quaggas are naturally belligerent creatures, a quagga is considered to attack quaggas on any squares it can move to, as well as any other quaggas on the same square. 38. [15] Given are real numbers a, y. For any pair of real numbers ao, a1, define a sequence by an+2=ran+1 +yan for n >0. Suppose that there exists a fixed nonnegative integer m such that, for every choice of ao and al, the numbers am, am+1, am+3, in this order, form an arithmetic progression. Find all possible values of y 39. [15] In the figure, if AE=3, CE=l, BD=CD=2, and AB=5, find AG
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 34. [12] OKRA is a trapezoid with OK parallel to RA. If OK = 12 and RA is a positive integer, how many integer values can be taken on by the length of the segment in the trapezoid, parallel to OK, through the intersection of the diagonals? 35. [12] A certain lottery has tickets labeled with the numbers 1, 2, 3, . . . , 1000. The lottery is run as follows: First, a ticket is drawn at random. If the number on the ticket is odd, the drawing ends; if it is even, another ticket is randomly drawn (without replacement). If this new ticket has an odd number, the drawing ends; if it is even, another ticket is randomly drawn (again without replacement), and so forth, until an odd number is drawn. Then, every person whose ticket number was drawn (at any point in the process) wins a prize. You have ticket number 1000. What is the probability that you get a prize? 36. [12] A teacher must divide 221 apples evenly among 403 students. What is the minimal number of pieces into which she must cut the apples? (A whole uncut apple counts as one piece.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 37. [15] A quagga is an extinct chess piece whose move is like a knight’s, but much longer: it can move 6 squares in any direction (up, down, left, or right) and then 5 squares in a perpendicular direction. Find the number of ways to place 51 quaggas on an 8 × 8 chessboard in such a way that no quagga attacks another. (Since quaggas are naturally belligerent creatures, a quagga is considered to attack quaggas on any squares it can move to, as well as any other quaggas on the same square.) 38. [15] Given are real numbers x, y. For any pair of real numbers a0, a1, define a sequence by an+2 = xan+1 +yan for n ≥ 0. Suppose that there exists a fixed nonnegative integer m such that, for every choice of a0 and a1, the numbers am, am+1, am+3, in this order, form an arithmetic progression. Find all possible values of y. 39. [15] In the figure, if AE = 3, CE = 1, BD = CD = 2, and AB = 5, find AG. F G A B D C E 5
HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003--GUTS ROUND 40. [18 All the sequences consisting of five letters from the set iT,U, R, N, I, P)(with repetitions allowed)are arranged in alphabetical order in a dictionary. Two sequences are called"anagrams "of each other if one can be obtained by rearranging the letters of the other. How many pairs of anagrams are there that have exactly 100 other sequences between them in the dictionary? 41.[18 A hotel consists of a 2 x 8 square grid of rooms, each occupied by one guest. All the guests are uncomfortable, so each guest would like to move to one of the adjoining rooms(horizontally or vertically). Of course, they should do this simultaneously, in such a way that each room will again have one guest. In how many different ways can they collectively move? 42.18 A tightrope walker stands in the center of a rope of length 32 minute she walks forward one meter with probability 3/4 and backy Le meter with probability 1/4. What is the probability that she reaches the end in front of her before the end behind her? HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 200 GUTS ROUND 43. Write down an integer N between 0 and 10, inclusive. You will receive N points unless some other team writes down the same N, in which case you receive nothing. 4. A partition of a number n is a sequence of positive integers, arranged in nonincreasing order, whose sum is n. For example, n= 4 has 5 partitions: 1+1+1+1=2+ 1+1=2+2=3+1=4. Given two different partitions of the same number n=a1+a2+…+ak=b1+b2+…+b, where k≤l, the first partition is said to dominate the second if all of the following inequalities hold b1 a1+a2≥b1+ a1+a2+a3≥b1+b2+b3 a1+a2+…+ak≥b1+b2+…+bk Find ly partitions of the number n= 20 as possible such that none of the partitions dominates any other. Your score will be the number of partitions you find If you make a mistake and one of your partitions does dominate another, your score is the largest m such that the first m partitions you list constitute a valid answer 45. Find a set S of positive integers such that no two distinct subsets of S have the same sum. Your score will be 20(2n/r-2)I, where n is the number of elements in the set S and r is the largest element of S(assuming, of course, that this number is nonnegative) Hej da
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 40. [18] All the sequences consisting of five letters from the set {T, U, R, N, I, P} (with repetitions allowed) are arranged in alphabetical order in a dictionary. Two sequences are called “anagrams” of each other if one can be obtained by rearranging the letters of the other. How many pairs of anagrams are there that have exactly 100 other sequences between them in the dictionary? 41. [18] A hotel consists of a 2 × 8 square grid of rooms, each occupied by one guest. All the guests are uncomfortable, so each guest would like to move to one of the adjoining rooms (horizontally or vertically). Of course, they should do this simultaneously, in such a way that each room will again have one guest. In how many different ways can they collectively move? 42. [18] A tightrope walker stands in the center of a rope of length 32 meters. Every minute she walks forward one meter with probability 3/4 and backward one meter with probability 1/4. What is the probability that she reaches the end in front of her before the end behind her? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HARVARD-MIT MATHEMATICS TOURNAMENT, MARCH 15, 2003 — GUTS ROUND 43. Write down an integer N between 0 and 10, inclusive. You will receive N points — unless some other team writes down the same N, in which case you receive nothing. 44. A partition of a number n is a sequence of positive integers, arranged in nonincreasing order, whose sum is n. For example, n = 4 has 5 partitions: 1 + 1 + 1 + 1 = 2 + 1 + 1 = 2 + 2 = 3 + 1 = 4. Given two different partitions of the same number, n = a1 + a2 + · · · + ak = b1 + b2 + · · · + bl , where k ≤ l, the first partition is said to dominate the second if all of the following inequalities hold: a1 ≥ b1; a1 + a2 ≥ b1 + b2; a1 + a2 + a3 ≥ b1 + b2 + b3; . . . a1 + a2 + · · · + ak ≥ b1 + b2 + · · · + bk. Find as many partitions of the number n = 20 as possible such that none of the partitions dominates any other. Your score will be the number of partitions you find. If you make a mistake and one of your partitions does dominate another, your score is the largest m such that the first m partitions you list constitute a valid answer. 45. Find a set S of positive integers such that no two distinct subsets of S have the same sum. Your score will be b20(2n/r−2)c, where n is the number of elements in the set S, and r is the largest element of S (assuming, of course, that this number is nonnegative). Hej d˚a! 6
Harvard-MIT Mathematics Tournament March 15. 2003 Team round Completions and Configurations Given a set A and a nonnegative integer k the k-completion of A is the collection of all k-element subsets of A, and a k-configuration of A is any subset of the k-completion of A (including the empty set and the entire k-completion). For instance, the 2-completion of A=1, 2, 3 is 1, 21,( 1, 31, 2, 31, and the 2-configurations of A are { {{1,2} {{1,3} {{2,3} {{1,2},{1,3} {{1,2},{2,3} {{1,3},{2,3} {{1,2},{1,3},{2,3} The order of an element a of A with respect to a given k-configuration of A is the number of subsets in the k-configuration that contain a. a k-configuration of a set A is consistent if the order of every element of A is the same, and the order of a consistent k-configuration is this common value 1.(a)[10 How many k-configurations are there of a set that has n elements? (b)[10 How many k-configurations that have m elements are there of a set that has n elements? 2. [15 Suppose A is a set with n elements, and k is a divisor of n. Find the number of onsistent k-configurations of a of order 1 3.(a)[15 Let An=a1, a2, a3, .. an, b], for n 2 3, and let Cn be the 2-configuration sting of{a,a2+} for all 1≤i≤n-1,{a1,an},and{a,b}for1≤ Let Se(n) be the number of subsets of Cn that ar Se(101)for e= 1, 2, and 3 (b)[20 Let A=V,w,X,Y, Z, 0, w, I, 9, 2. Find the number of subsets of the {{v,W},{W,},{X,Y},{Y,Z},{Z,V},{t,r},{,y},{,y},{u,x},{x,2} {v,v},{W,t},{X,x},{Y,y},{Z,x}} that are consistent of order 1 (c)[30 Let A=a1, b1, a2, b2, .. a10, b10, and consider the 2-configuration C con- sisting of{a,b-} for all 1≤i≤10,{a,a2+} for all 1≤i≤9,and{b2,b+}for all 1<i<9. Find the number of subsets of C that are consistent of order 1 Define a k-configuration of A to be m-separable if we can label each element of A with an integer from 1 to m(inclusive) so that there is no element e of the k-configuration all of whose elements are assigned the same integer. If C is any subset of A, then C is m-separable if we can assign an integer from 1 to m to each element of C so that there is no element e of the k-configuration such that E CC and all elements of e are assigned the same integer
Harvard-MIT Mathematics Tournament March 15, 2003 Team Round Completions and Configurations Given a set A and a nonnegative integer k, the k-completion of A is the collection of all k-element subsets of A, and a k-configuration of A is any subset of the k-completion of A (including the empty set and the entire k-completion). For instance, the 2-completion of A = {1, 2, 3} is {{1, 2}, {1, 3}, {2, 3}}, and the 2-configurations of A are {} {{1, 2}} {{1, 3}} {{2, 3}} {{1, 2}, {1, 3}} {{1, 2}, {2, 3}} {{1, 3}, {2, 3}} {{1, 2}, {1, 3}, {2, 3}} The order of an element a of A with respect to a given k-configuration of A is the number of subsets in the k-configuration that contain a. A k-configuration of a set A is consistent if the order of every element of A is the same, and the order of a consistent k-configuration is this common value. 1. (a) [10] How many k-configurations are there of a set that has n elements? (b) [10] How many k-configurations that have m elements are there of a set that has n elements? 2. [15] Suppose A is a set with n elements, and k is a divisor of n. Find the number of consistent k-configurations of A of order 1. 3. (a) [15] Let An = {a1, a2, a3, . . . , an, b}, for n ≥ 3, and let Cn be the 2-configuration consisting of {ai , ai+1} for all 1 ≤ i ≤ n − 1, {a1, an}, and {ai , b} for 1 ≤ i ≤ n. Let Se(n) be the number of subsets of Cn that are consistent of order e. Find Se(101) for e = 1, 2, and 3. (b) [20] Let A = {V, W, X, Y, Z, v, w, x, y, z}. Find the number of subsets of the 2-configuration { {V, W}, {W, X}, {X, Y }, {Y, Z}, {Z, V }, {v, x}, {v, y}, {w, y}, {w, z}, {x, z}, {V, v}, {W, w}, {X, x}, {Y, y}, {Z, z} } that are consistent of order 1. (c) [30] Let A = {a1, b1, a2, b2, . . . , a10, b10}, and consider the 2-configuration C consisting of {ai , bi} for all 1 ≤ i ≤ 10, {ai , ai+1} for all 1 ≤ i ≤ 9, and {bi , bi+1} for all 1 ≤ i ≤ 9. Find the number of subsets of C that are consistent of order 1. Define a k-configuration of A to be m-separable if we can label each element of A with an integer from 1 to m (inclusive) so that there is no element E of the k-configuration all of whose elements are assigned the same integer. If C is any subset of A, then C is m-separable if we can assign an integer from 1 to m to each element of C so that there is no element E of the k-configuration such that E ⊆ C and all elements of E are assigned the same integer. 1