4.(a)[15 Suppose A has n elements, where n >> 2, and C is a 2-configuration of A that is not m-separable for any m n. What is(in terms of n) the smallest number of elements that C can have (b)[15Show that every 3-configuration of an n-element set A is m-separable for every integer m≥n/2 c)25 Fix k> 2, and suppose A has k elements. Show that any k-configuration of A with fewer than(k-1) elements is k-separable 5. 30 Let Bk(n) be the largest number of elements in a 2-separable k-configuration of a set with 2n elements(2< k<n). Find a closed-form expression (i.e. an expression not involving any sums or products with an variable number of terms) for Bk(n) 40 Prove that any 2-configuration containing e elements is m-separable for some m≤b+√2e+ a cell of a 2-configuration of a set A is a nonempty subset C of A such that i. for any two distinct elements a, b of C, there exists a sequence co, C1,..., Cn of elements of A with co=a, Cn= b, and such that ico, c1, C1, c2,..., cn-1,Cn are all elements of the 2-configuration, and ii. if a is an element of C and b is an element of a but not of C. there does not exist a sequence Co, C1,..., Cn of elements of A with co= a, Cn= b, and such that C1, C1, c2,.(Cn-1,Cn) are all elements of the 2-configuration Also, we define a 2-configuration of A to be barren if there is no subset ao, a1, .. an of A with n 2 2, such that a0, a1, a1,a2,.,an-1, an and (an, ao are all elements of the 2-configuration 7.20 Show that, given any 2-configuration of a set A, every element of A belongs to exactly one cell 8.(a)[15 Given a set A with n> 1 elements, find the number of consistent 2- configurations of A of order 1 with exactly 1 cell (b)[25]Given a set A with 10 elements, find the number of consistent 2-configurations of A of order 2 with exactly 1 cell (c)25] Given a set A with 10 elements, find the number of consistent 2-configurations of order 2 with exactly 2 cell 9.(a)[15 Show that if every cell of a 2-configuration of a finite set A is m-separable then the whole 2-configuration is m-sep (b)[30 Show that any barren 2-configuration of a finite set A is 2-separable 10.[45] Show that every consistent 2-configuration of order 4 on a finite set A has a subset that is a consistent 2-configuration of order 2
4. (a) [15] Suppose A has n elements, where n ≥ 2, and C is a 2-configuration of A that is not m-separable for any m < n. What is (in terms of n) the smallest number of elements that C can have? (b) [15] Show that every 3-configuration of an n-element set A is m-separable for every integer m ≥ n/2. (c) [25] Fix k ≥ 2, and suppose A has k 2 elements. Show that any k-configuration of A with fewer than ³ k 2−1 k−1 ´ elements is k-separable. 5. [30] Let Bk(n) be the largest number of elements in a 2-separable k-configuration of a set with 2n elements (2 ≤ k ≤ n). Find a closed-form expression (i.e. an expression not involving any sums or products with an variable number of terms) for Bk(n). 6. [40] Prove that any 2-configuration containing e elements is m-separable for some m ≤ 1 2 + q 2e + 1 4 . A cell of a 2-configuration of a set A is a nonempty subset C of A such that i. for any two distinct elements a, b of C, there exists a sequence c0, c1, . . . , cn of elements of A with c0 = a, cn = b, and such that {c0, c1}, {c1, c2}, . . . , {cn−1, cn} are all elements of the 2-configuration, and ii. if a is an element of C and b is an element of A but not of C, there does NOT exist a sequence c0, c1, . . . , cn of elements of A with c0 = a, cn = b, and such that {c0, c1}, {c1, c2}, . . ., {cn−1, cn} are all elements of the 2-configuration. Also, we define a 2-configuration of A to be barren if there is no subset {a0, a1, . . . , an} of A, with n ≥ 2, such that {a0, a1}, {a1, a2}, . . . , {an−1, an} and {an, a0} are all elements of the 2-configuration. 7. [20] Show that, given any 2-configuration of a set A, every element of A belongs to exactly one cell. 8. (a) [15] Given a set A with n ≥ 1 elements, find the number of consistent 2- configurations of A of order 1 with exactly 1 cell. (b) [25] Given a set A with 10 elements, find the number of consistent 2-configurations of A of order 2 with exactly 1 cell. (c) [25] Given a set A with 10 elements, find the number of consistent 2-configurations of order 2 with exactly 2 cells. 9. (a) [15] Show that if every cell of a 2-configuration of a finite set A is m-separable, then the whole 2-configuration is m-separable. (b) [30] Show that any barren 2-configuration of a finite set A is 2-separable. 10. [45] Show that every consistent 2-configuration of order 4 on a finite set A has a subset that is a consistent 2-configuration of order 2. 2
Harvard-MIT Mathematics Tournament February 28, 2004 Individual Round: Algebra Subject Test How many ordered pairs of integers(a, b)satisfy all of the following inequalities? 2. Find the largest number n such that(2004! ) is divisible by(n!)!) 3. Comput 2005 2003·20042004·2005 4. Evaluate the sum 2√+1+2√2」+1+2√③+1++2√00+1 5. There exists a positive real number r such that cos(tan())=a. Find the value of 6. Find all real solutions to r+(2-x)=34 7. If a, y, k are positive reals such that × find the maximum possible value of k 8. Let r be a real number such that x3+4.r =8. Determine the value of x7+64 r2 9. A sequence of positive integers is defined by ao= l and an+1=an+1 for each n>0. Find gcd(agg, a2004) 10. There exists a polynomial P of degree 5 with the following property: if z is a complex number such that 26+20042=1, then P(22)=0. Calculate the quotient P(1)/P(1)
Harvard-MIT Mathematics Tournament February 28, 2004 Individual Round: Algebra Subject Test 1. How many ordered pairs of integers (a,b) satisfy all of the following inequalities? a 2 + b 2 < 16 a 2 + b 2 < 8a a 2 + b 2 < 8b 2. Find the largest number n such that (2004!)! is divisible by ((n!)!)!. 3. Compute: $ 20053 2003 · 2004 − 20033 2004 · 2005% . 4. Evaluate the sum 1 2b √ 1c + 1 + 1 2b √ 2c + 1 + 1 2b √ 3c + 1 + · · · + 1 2b √ 100c + 1 . 5. There exists a positive real number x such that cos(tan−1 (x)) = x. Find the value of x 2 . 6. Find all real solutions to x 4 + (2 − x) 4 = 34. 7. If x, y, k are positive reals such that 3 = k 2 à x 2 y 2 + y 2 x 2 ! + k à x y + y x ! , find the maximum possible value of k. 8. Let x be a real number such that x 3 + 4x = 8. Determine the value of x 7 + 64x 2 . 9. A sequence of positive integers is defined by a0 = 1 and an+1 = a 2 n + 1 for each n ≥ 0. Find gcd(a999, a2004). 10. There exists a polynomial P of degree 5 with the following property: if z is a complex number such that z 5+2004z = 1, then P(z 2 ) = 0. Calculate the quotient P(1)/P(−1). 1
Harvard-MIT Mathematics Tournament February 28, 2004 Individual Round: Geometry Subject Test n trapezoid ABCD, AD is parallel to BC.∠A=∠D=45°, while∠B=LC=135 If AB=6 and the area of AbcD is 30. find BC 135 Area=30 2. A parallelogram has 3 of its vertices at(1, 2),(3, 8), and(4, 1). Compute the sum of the possible x-coordinates for the 4th vertex 3. A swimming pool is in the shape of a circle with diameter 60 ft. The depth varies linearly along the east-west direction from 3 ft at the shallow end in the east to 15 ft at the diving end in the west(this is so that divers look impressive against the sunset) but does not vary at all along the north-south direction. What is the volume of the pool, in ft3? 4. P is inside rectangle ABCD. PA=2, PB=3, and PC=10. Find PD 5. Find the area of the region of the xy-plane defined by the inequality I+lv+lc+yl<1 6. In trapezoid ABCD shown, AD is parallel to BC, and AB=6, BC=7, CD 8. AD= 17. If sides AB and CD are extended to meet at e. find the resulting angle at E (in degrees 7. Yet another trapezoid ABCD has AD parallel to BC. AC and BD intersect at P If [ADP/BCP=1/2, find [ADPI/ABCD.(Here the notation [Pi.Pn denot the area of the polygon Pi.. Pn) 8. A triangle has side lengths 18, 24, and 30. Find the area of the triangle whose vertices are the incenter circumcenter, and centroid of the original triangle 9. Given is a regular tetrahedron of volume 1. We obtain a second regular tetrahedron by reflecting the given one through its center. What is the volume of their intersection? Right triangle XYZ has right angle at Y and XY=228, YZ= 2004. Angle y is trisected, and the angle trisectors intersect XZ at P and Q so that X, P, Q, Z lie on XZ in that order. Find the value of (Py+yZ)(QY+XY)
Harvard-MIT Mathematics Tournament February 28, 2004 Individual Round: Geometry Subject Test 1. In trapezoid ABCD, AD is parallel to BC. 6 A = 6 D = 45◦ , while 6 B = 6 C = 135◦ . If AB = 6 and the area of ABCD is 30, find BC. ? C A 45 45 135 135 B D 6 Area = 30 2. A parallelogram has 3 of its vertices at (1, 2), (3,8), and (4, 1). Compute the sum of the possible x-coordinates for the 4th vertex. 3. A swimming pool is in the shape of a circle with diameter 60 ft. The depth varies linearly along the east-west direction from 3 ft at the shallow end in the east to 15 ft at the diving end in the west (this is so that divers look impressive against the sunset) but does not vary at all along the north-south direction. What is the volume of the pool, in ft3 ? 4. P is inside rectangle ABCD. P A = 2, P B = 3, and P C = 10. Find PD. 5. Find the area of the region of the xy-plane defined by the inequality |x|+|y|+|x+y| ≤ 1. 6. In trapezoid ABCD shown, AD is parallel to BC, and AB = 6, BC = 7, CD = 8, AD = 17. If sides AB and CD are extended to meet at E, find the resulting angle at E (in degrees). A E B C 17 8 7 6 D 7. Yet another trapezoid ABCD has AD parallel to BC. AC and BD intersect at P. If [ADP]/[BCP] = 1/2, find [ADP]/[ABCD]. (Here the notation [P1 · · · Pn] denotes the area of the polygon P1 · · · Pn.) 8. A triangle has side lengths 18, 24, and 30. Find the area of the triangle whose vertices are the incenter, circumcenter, and centroid of the original triangle. 9. Given is a regular tetrahedron of volume 1. We obtain a second regular tetrahedron by reflecting the given one through its center. What is the volume of their intersection? 10. Right triangle XY Z has right angle at Y and XY = 228, Y Z = 2004. Angle Y is trisected, and the angle trisectors intersect XZ at P and Q so that X, P, Q, Z lie on XZ in that order. Find the value of (P Y + Y Z)(QY + XY ). 1
Harvard-MIT Mathematics Tournament February 28, 2004 Individual Round: Combinatorics Subject Test There are 1000 rooms in a row along a long corridor. Initially the first room contains 1000 people and the remaining rooms are empty. Each minute, the following happens for each room containing more than one person, someone in that room decides it is too crowded and moves to the next room. All these movements are simultaneous(so nobody moves more than once within a minute). After one hour, how many different rooms will have people in them? 2. How many ways can you mark 8 squares of an 8x8 chessboard so that no two marked squares are in the same row or column, and none of the four corner squares is marked (Rotations and reflections are considered different. 3. A class of 10 students took a math test. Each problem was solved by exactly 7 of the students. If the first nine students each solved 4 problems, how many problems did the tenth student solve? 4. Andrea Hips a fair coin repeatedly, continuing until she either Hips two heads in a row (the sequence H)or flips tails followed by heads(the sequence TH). What is the probability that she will stop after Hipping HH? a best-of-9 series is to be played between two teams; that is, the first team to win 5 games is the winner. The Mathletes have a chance of 2/3 of winning any given game What is the probability that exactly 7 games will need to be played to determine a winner? 6. A committee of 5 is to be chosen from a group of 9 people. How many ways can it be hosen. if Bill and Karl must serve together or not at all. and Alice and Jane refuse to serve with each other? 7. We have a polyhedron such that an ant can walk from one vertex to another traveling only along edges, and traversing every edge exactly once. What is the smallest possible total number of vertices, edges, and faces of this polyhedron? 8. Urn a contains 4 white balls and 2 red balls. Urn b contains 3 red balls and 3 black balls. An urn is randomly selected, and then a ball inside of that urn is removed. We then repeat the process of selecting an urn and drawing out a ball, without returning the first ball. What is the probability that the first ball drawn was red, given that the second ball drawn was black? 9. A classroom consists of a 5 5 array of desks, to be filled by anywhere from 0 to 2: students, inclusive. No student will sit at a desk unless either all other desks in its row or all others in its column are filled (or both). Considering only the set of desks that are occupied(and not which student sits at each desk), how many possible arrangements are there?
Harvard-MIT Mathematics Tournament February 28, 2004 Individual Round: Combinatorics Subject Test 1. There are 1000 rooms in a row along a long corridor. Initially the first room contains 1000 people and the remaining rooms are empty. Each minute, the following happens: for each room containing more than one person, someone in that room decides it is too crowded and moves to the next room. All these movements are simultaneous (so nobody moves more than once within a minute). After one hour, how many different rooms will have people in them? 2. How many ways can you mark 8 squares of an 8 ×8 chessboard so that no two marked squares are in the same row or column, and none of the four corner squares is marked? (Rotations and reflections are considered different.) 3. A class of 10 students took a math test. Each problem was solved by exactly 7 of the students. If the first nine students each solved 4 problems, how many problems did the tenth student solve? 4. Andrea flips a fair coin repeatedly, continuing until she either flips two heads in a row (the sequence HH) or flips tails followed by heads (the sequence T H). What is the probability that she will stop after flipping HH? 5. A best-of-9 series is to be played between two teams; that is, the first team to win 5 games is the winner. The Mathletes have a chance of 2/3 of winning any given game. What is the probability that exactly 7 games will need to be played to determine a winner? 6. A committee of 5 is to be chosen from a group of 9 people. How many ways can it be chosen, if Bill and Karl must serve together or not at all, and Alice and Jane refuse to serve with each other? 7. We have a polyhedron such that an ant can walk from one vertex to another, traveling only along edges, and traversing every edge exactly once. What is the smallest possible total number of vertices, edges, and faces of this polyhedron? 8. Urn A contains 4 white balls and 2 red balls. Urn B contains 3 red balls and 3 black balls. An urn is randomly selected, and then a ball inside of that urn is removed. We then repeat the process of selecting an urn and drawing out a ball, without returning the first ball. What is the probability that the first ball drawn was red, given that the second ball drawn was black? 9. A classroom consists of a 5 × 5 array of desks, to be filled by anywhere from 0 to 25 students, inclusive. No student will sit at a desk unless either all other desks in its row or all others in its column are filled (or both). Considering only the set of desks that are occupied (and not which student sits at each desk), how many possible arrangements are there? 1
10. In a game similar to three card monte, the dealer places three cards on the table: the queen of spades and two red cards. The cards are placed in a row, and the queen starts in the center; the card configuration is thus RQR. The dealer proceeds to move With each move, the dealer randomly switches the center card with one of the two edge cards(so the configuration after the first move is either RRQ or QRR). What is the probability that, after 2004 moves, the center card is the queen?
10. In a game similar to three card monte, the dealer places three cards on the table: the queen of spades and two red cards. The cards are placed in a row, and the queen starts in the center; the card configuration is thus RQR. The dealer proceeds to move. With each move, the dealer randomly switches the center card with one of the two edge cards (so the configuration after the first move is either RRQ or QRR). What is the probability that, after 2004 moves, the center card is the queen? 2