19th USA Mathematical Olympiad 1990 Problems
1. A license plate has six digits from 0 to 9 and may have leading zeros. If two plates must always differ in at least two places, what is the largest number of plates that is possible?
2. Define f1(x) = √(x2 + 48) and fn(x) = √(x2 + 6fn-1(x) ). Find all real solutions to fn(x) = 2x.
3. Show that for any odd positive integer we can always divide the set {n, n+1, n+2, ... , n+32} into two parts, one with 14 numbers and one with 19, so that the numbers in each part can be arranged in a circle, with each number relatively prime to its two neighbours. For example, for n = 1, arranging the numbers as 1, 2, 3, ... , 14 and 15, 16, 17, ... , 33, does not work, because 15 and 33 are not relatively prime.
4. How many positive integers can be written in base n so that (1) the integer has no two digits the same, and (2) each digit after the first differs by one from an earlier digit? For example, in base 3, the possible numbers are 1, 2, 10, 12, 21, 102, 120, 210.
5. ABC is acute-angled. The circle diameter AB meets the altitude from C at P and Q. The circle diameter AC meets the altitude from B at R and S. Show that P, Q, R and S lie on a circle.
Solution
19th USA Mathematical Olympiad 1990
Problem 1
A license plate has six digits from 0 to 9 and may have leading zeros. If two plates must always differ in at least two places, what is the largest number of plates that is possible?
Solution
Answer: 105.
We show by induction that we can find a set of 10n-1 plates for n > 1 digits. It is true for n = 2: take the plates 00, 11, 22, ... , 99. Suppose it is true for n. If d is a digit from 0 to 9 and s is a plate of n digits, let [d, s] be the plate of n+1 digits which has a as its first digit, and the remaining digits the same as those of s, except that the last digit is that for s plus d (reduced mod 10 if necessary). Let S be a set of plates for n digits. We claim that the set S' = { [d, s] : d = 0, 1, ... or 9 and s belongs to S} is a set of plates for n+1 digits. It obviously has 10 times as many members as S, so this claim is sufficient to establish the induction.
We have to show that [a, s] and [b, t] differ in at least two places. If a = b, then s ≠ t, so s and t differ in at least two places. The same change is made to their last digits, so [a, s] and [a, t] differ in at least two places. If a ≠ b and s = t, then [a, s] and [b, s] differ in both their first and last places. If a ≠ b and s ≠ t, then s and t differ in at least two places and so the modified s and t, differ in at least one place. But [a, s] and [b, t] also differ in the first place, so they differ in at least two places.
So we have established that the largest number is at least 10n-1 for n digits.
But any two plates which differ only in the last digit cannot both be chosen. So at most 1/10 of the 10n possible plates can be chosen. That shows that 10n-1 is best possible. Problem 2
Define f1(x) = √(x2 + 48) and fn(x) = √(x2 + 6fn-1(x) ). Find all real solutions to fn(x) = 2x.
Solution
Answer: For each n, x = 4 is the only solution.
Obviously x = 4 is a solution. Since fn(x) >= 0, any solution must be non-negative. So we restrict attention to x ≥ 0.
Suppose x < 4. We show by induction that fn(x) > 2x. For n = 1, the claim is equivalent to 4x2 < x2 + 48, or x2 < 16, which is true. So suppose the result is true for n. Then x2 + 6fn(x) > x2 + 12x. But x < 4, so 3x2 < 12x, so 4x2 < x2 + 12x. Hence fn+1(x) > 2x, as required.
An exactly similar argument shows that fn(x) < 2x for x > 4. Hence x = 4 is the only solution.
Show that for any odd positive integer we can always divide the set {n, n+1, n+2, ... , n+32} into two parts, one with 14 numbers and one with 19, so that the numbers in each part can be arranged in a circle, with each number relatively prime to its two neighbours. For example, for n = 1, arranging the numbers as 1, 2, 3, ... , 14 and 15, 16, 17, ... , 33, does not work, because 15 and 33 are not relatively prime.
Solution
Suppose we use n, n+1, ... , n+13 for the first circle. That certainly works for n not divisible by 13, since consecutive numbers are always relatively prime and any common divisor of n and n+13 must also divide their difference 13. We could then take the second circle to be n+15, n+14, n+16, n+17, ... , n+32 for n ≠ 2 mod 17 or n+14, n+15, ... , n+29, n+30, n+32, n+31 if n = 2 mod 17. Note that any common factor of n+14 and n+16 must divide their difference 2, but n is odd, so they are relatively prime. Similarly, n+30 and n+32.
If n is divisible by 13, then n+19 is not, so we can take n+19, n+20, ... , n+32 for the first circle. Then we can take the second circle to be n+1, n, n+2, n+3, ... , n+18 for n ≠ 16 mod 17 or n, n+1, ... , n+15, n+16, n+18, n+17 if n = 16 mod 17.
How many positive integers can be written in base n so that (1) the integer has no two digits the same, and (2) each digit after the first differs by one from an earlier digit? For example, in base 3, the possible numbers are 1, 2, 10, 12, 21, 102, 120, 210.
Solution
Answer: 2n+1 - 2n - 2.
We use a more elaborate induction hypothesis. We claim that for base n+1, the following numbers of integers satisfy the two conditions: 2n+1- 2n - 2 not using the digit n; 2n - 1 with the digit n is the last position; 2n-1 with the digit n in the last but 1 position; 2n-2 with the digit n having 2 following digits; 2n-3 with the digit n having 3 following digits; ... ; 1 with the digit n having n following digits.
Thus for n = 2, the claim is that there are 2 numbers only involving 0 and 1 (1, 10), 3 numbers with 2 as the last digit (2, 12, 102), 2 numbers with one digit after 2 (21, 120) and 1 number with two digits after 2 (210). Suppose this holds for base n+1.
If we add up the various possibilities we get 2n+1 - 2n - 2 + (2n - 1 + 2n-1 + 2n-2 + ... + 1) = 2n+1 - 2n - 2 + 2n+1 - 2 = 2n+2 - 2(n+1) - 2. The number of base n+2 integers not involving the digit n+1 is the same as the number of base n+1 numbers, which is (by induction and the addition above) 2n+2 - 2(n+1) - 2. If a base n+2 number has the digit n+1 in the last place, then either that is the only digit in the number or the earlier digits must form a base n+1 number with the digit n in it. There are (2n - 1 + 2n-1 + ... + 1) = 2n+1 - 2 such numbers, so in total we have 2n+1 - 1 base n+2 numbers with n+1 in the last place. If a base n+2 number has the digit n+1 in the penultimate place, then either the number has n+1 as the first digit, in which case it must be n+1 n, or the other digits form a base n+1 number with the digit n in the penultimate place or earlier. There are 2n-1 + ... + 1 = 2n - 1 such numbers. So 2n in total. Similarly for the other possibilities.
Finally, we need to check the answer for n = 2 (1, 10, so two numbers and 22+1 - 2·2 - 2 = 8 - 4 - 2 = 2).
ABC is acute-angled. The circle diameter AB meets the altitude from C at P and Q. The circle diameter AC meets the altitude from B at R and S. Show that P, Q, R and S lie on a circle.
Solution
Use vectors. Take A as the origin. Let AB = b, AC = c, AR = r. AR is perpendicular to RC, so r.(c - r) = 0. BR is perpendicular to AC, so (b - r).c = 0. Hence r.r = r.c = b.c. Thus |AR| = √(|AB|·|AC| cos A). But the identical argument gives the same value for |AS|. The situtation is symmetrical between B and C, so we get the same result for |AP| and |AQ|. Hence all four points lie on a circle center A.
Labels:
USAMO
Previous Article
