返回题库

PUMaC 2008 · 团队赛 · 第 13 题

PUMaC 2008 — Team Round — Problem 13

专题
Discrete Math / 离散数学
难度
L3
来源
PUMaC

题目详情

Team B √ √ √ 6

  1. (2 points) Calculate 6 + 6 + 6 + . . . + . 6 1+ 1+ ...
  2. (2 points) Find log 3 ∗ log 4 ∗ log 5 ∗ . . . ∗ log 63 ∗ log 64. 2 3 4 62 63
  3. (3 points) What is the smallest positive integer value of x for which x ≡ 4 (mod 9) and x ≡ 7 (mod 8)?
  4. (3 points) What is the difference between the median and the mean of the following data set: 12, 41, 44, 48, 47, 53, 60, 62, 56, 32, 23, 25, 31?
  5. (4 points) Quadrilateral ABCD has both an inscribed and a circumscribed circle and sidelengths BC = 4, CD = 5, DA = 6. Find the area of ABCD .
  6. (4 points) The seven dwarves are at work on day when they find a large pile of diamonds. They want to split the diamonds evenly among them, but find that they would need to take away one diamond to split into seven equal piles. They are still arguing about this when they get home, so Snow White sends them to bed without supper. In the middle of the night, Sneezy wakes up and decides that he should get the extra diamond. So he puts one diamond aside, splits the remaining ones in to seven equal piles, and takes his pile along with the extra diamond. Then, he runs off with the diamonds. His sneeze wakes up Grumpy, who, thinking along the same lines, removes one diamond, divides the remainder into seven equal piles, and runs off. Finally, Sleepy, for the first time in his life, wakes up before sunrise and performs the same operation. When the remaining four dwarves arise, they find that the remaining diamonds can be split into 5 equal piles. Doc suggests that Snow White should get a share, so they have no problem splitting the remaining diamonds. Happy, Dopey, Bashful, Doc, and Snow White live happily ever after. What’s the smallest possible number of diamonds that the dwarves could have started out with?
  7. (5 points) The graphs of the following equations divide the xy plane into some number of regions. 2 4 + ( x + 2) y = x 2 2 ( x + 2) + y =16 Find the area of the second smallest region. 2 3 3
  8. (5 points) Suppose that the roots of the quadratic x + ax + b are α and β . Then α and β are 2 the roots of some quadratic x + cx + d. Find c in terms of a and b . 1

Team B 9. (7 points) Alex Lishkov is trying to guess sequence of 2009 random ternary digits (0, 1, or 2). After he guesses each digit, he finds out whether he was right or not. If he guesses incorrectly, and k was the correct answer, then an oracle tells him what the next k digits will be. Being Bulgarian, Lishkov plays to maximize the expected number of digits guessed correctly. Let P be the probability that n k Lishkov guesses the n th digit correctly. Find P . Write your answer in the form x + y Re( ρ ), 2009 where x and y are rational, ρ is complex, and k is a positive integer. 10. (7 points) Consider the sequence s = (1 , 2008). Define new sequences s inductively by inserting 0 i the sum of each pair of adjacent terms in s between them—for instance, s = (1 , 2009 , 2008). i − 1 1 For some n , s has exactly one term that appears twice. Find this repeated term. n 2

解析
  1. Consider the sequence s = (1 , 2008). Define new sequences s inductively by inserting the sum of 0 i each pair of adjacent terms in s between them—for instance, s = (1 , 2009 , 2008). For some n , i − 1 1 s has exactly one term that appears twice. Find this repeated term. n 4 Team ( ANS: 1805535. Instead of starting with 1 and 2008, use ordered pairs (1,0) and (0,1). (In s , for instance, you 2 have (1,0),(2,1),(1,1),(1,2),(0,1).) By induction, after n iterations the greatest number that appears in any ordered pair is F . Two pairs ( a, b ) and ( c, d ) correspond to the same integers iff n +1 2008( a − c ) + 1( b − d ) = 0, so to have equal pairs we need some element at least 2008 (we never get the same pair twice because, if we view each ordered pair ( a, b ) as a fraction a/b , they’re strictly decreasing). Since F = 1597 < 2008, we need at least 17 iterations. 17 Note that by induction, if n is the sum of the coefficients of the continued fraction expansion of a/b , then ( a, b ) first appears in s . Hence (2351, 898) first appears in s , and (343 , 899) first n 17 appears in s , since their continued fraction expansions are (2;1,1,1,1,1,1,1,1,1,1,1,2,1,1) and 16 (0;2,1,1,1,1,1,3,3,1,1,1), respectively. These both correspond to 1805535, so that’s the answer. The continued fraction expansions also give a clue how to find these (the following section will be most useful for readers who’ve already played around with the sequences): if ( a, b ) and ( c, d ) are the above integers, we saw above that we needed a close to the maximum possible, which occurs 2 only if a ≈ φb or a ≈ φ b . Hence we must have either ( a, b, c, d ) ≈ ( φb, b, φb − 2008 , b + 1) or 2 2 d ( a, b, c, d ) ≈ ( φ b, b, φ b − 2008 , b + 1). Experimentation shows that we also want to be c 2 a d 2 approximately φ or φ ; of these cases the minimum value of b occurs when ≈ ≈ φ . In this b c 2 2008 φ − 1 b +1 2 case, ≈ φ gives b ≈ ≈ 898. In that case, a ≈ 2351, c ≈ 343, and d ≈ 899, and in 2 4 φ b − 2008 φ − 1 fact these values work. All of the above was done by hand; proving that there is only one repeated value in s required 2007 a computer search. Thanks to Mathew Crawford for his contribution. CB: ACH) 5