返回题库

PUMaC 2008 · 团队赛 · 第 12 题

PUMaC 2008 — Team Round — Problem 12

专题
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. Let X = 1 + 2 + · · · + 100. If p is the polynomial of minimal degree with integer coefficients such that p ( X ) = 0, find the prime factorization of the sum of the roots of p . 25 ( ANS: 2 · 5 · 11 There are 25 prime numbers less than 100, p , . . . , p . We may write 1 n ∑ ∑ √ √ X = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + n = 55 + n . 2 ≤ n ≤ 99 not a square 2 ≤ n ≤ 99 not a square √ 25 Given any 25-tuple ∈ {− 1 , 1 } , let X be X where we replace every occurence of p with i i √ p for all i . Now suppose P ( T ) is the minimal polynomial for X = X 25 . Then when we i i 1 √ √ multiply out P ( X ), all the p must cancel. Thus if we change the sign of each occurence of p , i i we do not change P ( X ). Thus we conclude that for all , we have P ( X ) = 0. Thus P has at least ∏ 25 2 roots. Conversely, let us show that P ( T ) = ( T − X ) has rational coefficients, and thus is the minimal polynomial of X . To see this, observe that the coefficients of P ( T ) are polynomials √ √ in 1 and p . However, we see that changing the sign on every occurence of p just permutes i i the roots of P ( T ), and thus does not change its coefficients. Thus we conclude that the √ coefficients of P ( T ) actually do not involve p . Hence we see that P ( T ) has rational coefficients i as claimed. Now we just need to calculate the sum of the roots of P . But this is now easy: we get ∑ √ 25 2 · 55, since the stuff in the sum n all cancels when summed over all sign 2 ≤ n ≤ 99 not a square 25 flips . Thus the answer is 2 · 5 · 11 as claimed. CB: IAF, JVP)