HMMT 二月 2019 · 冲刺赛 · 第 32 题
HMMT February 2019 — Guts Round — Problem 32
题目详情
- [ 20 ] For positive integers a and b such that a is coprime to b , define ord ( a ) as the least positive integer
b
k
k such that b | a − 1, and define ϕ ( a ) to be the number of positive integers less than or equal to a
which are coprime to a . Find the least positive integer n such that
ϕ ( n )
ord ( m ) <
n
10
for all positive integers m coprime to n .
Warning: The next (and final) set contains problems in different formats.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HMMT February 2019, February 16, 2019 — GUTS ROUND
Organization Team Team ID#
Welcome to Ultra Relay ! This is an event where teams of twenty-five students race to solve a set of
twenty-five problems and ultimately find the answers to the four “anchor” problems. Many of the problems
will depend on answers to other problems, hence the team members will need to relay the answers from one
person/problem to the next, along the network shown below. (The anchor problems are indicated by a box.)
Only the answers to the four anchor problems will be graded.
H H M M M M T T T
1 2 1 2 3 4 1 2 3
H H H M M M T
3 4 5 5 6 7 4
M M
8 9
H H M M M M T
6 7 10 11 12 13 5
What? You don’t have twenty-five people on your team, you say? That’s unfortunate. Anyway, here are all
the problems. (You may work on them together.) Have fun!
For ease of reference, the label of each problem also denotes the answer to that problem.
H . Let r = H be the answer to this problem. Given that r is a nonzero real number, what is the value
1 1
4 3 2
of r + 4 r + 6 r + 4 r ?
H . Given two distinct points A , B and line
that is not perpendicular to AB , what is the maximum 2 possible number of points P onsuch that ABP is an isosceles triangle? H . Let A = H , B = H + 1. A real number x is chosen randomly and uniformly in the interval [ A, B ]. 3 1 6 2 3 Find the probability that x > x > x . H . Let A = d 1 /H e , B = d H / 2 e . How many ways are there to partition the set { 1 , 2 , . . . , A + B } into 4 3 5 two sets U and V with size A and B respectively such that the probability that a number chosen from 1 U uniformly at random is greater than a number chosen from V uniformly at random is exactly ? 2 H . Let A = H , B = H . Two circles with radii A and B respectively are given in the plane. If the length 5 2 7 of their common external tangent is twice the length of their common internal tangent (where both tangents are considered as segments with endpoints being the points of tangency), find the distance between the two centers. H . How many ways are there to arrange the numbers 21 , 22 , 33 , 35 in a row such that any two adjacent 6 numbers are relatively prime? 2 2 H . How many pairs of integers ( x, y ) are there such that | x − 2 y | ≤ 1 and | 3 x − 4 y | ≤ 1? 7 M . Let S = M . Determine the number of ordered triples ( a, b, c ) of nonnegative integers such that 1 10 a + 2 b + 4 c = S . M . Let S = b M c . Two integers m and n are chosen between 1 and S inclusive uniformly and independently 2 5 n m at random. What is the probability that m = n ? ◦ M . Let S = d M e . In right triangle ABC , ∠ C = 90 , AC = 27 , BC = 36. A circle with radius S is 3 7 tangent to both AC and BC and intersects AB at X and Y . Find the length of XY . M . Let S = M + 5. Compute the product of all positive divisors of S . 4 13 √ 1 1 M . Let A = M , B = d M e . Given complex numbers x and y such that x + = A , + y = B , compute 5 1 11 y x 1 the value of xy + . xy 2 M . Let A = b 1 /M c , B = b M / 100 c . Let P and Q both be quadratic polynomials. Given that the real 6 2 3 roots of P ( Q ( x )) = 0 are 0 , A, B, C in some order, find the sum of all possible values of C . M . Let A = d log M e , B = M + 1. A 5-term sequence of positive reals satisfy that the first three terms 7 4 12 2 and the last three terms both form an arithmetic sequence and the middle three terms form a geometric sequence. If the first term is A and the fifth term is B , determine the third term of the sequence. 2 2 M . Let A = b M c , B = b M c . A regular A -gon, a regular B -gon, and a circle are given in the plane. 8 5 6 What is the greatest possible number of regions that these shapes divide the plane into? M . Let A and B be the unit digits of d 7 M e and b 6 M c respectively. When all the positive integers not 9 6 7 th containing digit A or B are written in increasing order, what is the 2019 number in the list? M . What is the smallest positive integer with remainder 2 , 3 , 4 when divided by 3 , 5 , 7 respectively? 10 M . An equiangular hexagon has side lengths 1 , 2 , 3 , 4 , 5 , 6 in some order. Find the nonnegative difference 11 between the largest and the smallest possible area of this hexagon. 3 2 M . Determine the second smallest positive integer n such that n + n + n + 1 is a perfect square. 12 M . Given that A, B are nonzero base-10 digits such that A · AB + B = BB , find AB . 13 √ T . Let S, P, A, C, E be (not necessarily distinct) decimal digits where E 6 = 0. Given that N = ESCAP E 1 is a positive integer, find the minimum possible value of N . T . Let X = b T / 8 c , Y = T − 1 , Z = T − 2. A point P lies inside the triangle ABC such that P A = 2 1 3 4 X, P B = Y, P C = Z . Find the largest possible area of the triangle. T . How many ways can one tile a 2 × 8 board with 1 × 1 and 2 × 2 tiles? Rotations and reflections of the 3 same configuration are considered distinct. 2 2 2 2 T . Let S = T . Given real numbers a, b, c such that a + b + c + ( a + b + c ) = S , find the maximum 4 5 possible value of ( a + b )( b + c )( c + a ). T . A regular tetrahedron has volume 8. What is the volume of the set of all the points in the space ( not 5 necessarily inside the tetrahedron ) that are closer to the center of the tetrahedron than any of the four vertices?
解析
- [ 20 ] For positive integers a and b such that a is coprime to b , define ord ( a ) as the least positive integer
b
k
k such that b | a − 1, and define ϕ ( a ) to be the number of positive integers less than or equal to a
which are coprime to a . Find the least positive integer n such that
ϕ ( n )
ord ( m ) <
n
10
for all positive integers m coprime to n .
Proposed by: Andrew Gu
Answer: 240
The maximum order of an element modulo n is the Carmichael function, denoted λ ( n ). The following
properties of the Carmichael function are established:
k k − 1
• For primes p > 2 and positive integers k , λ ( p ) = ( p − 1) p .
• For a positive integer k ,
{
k − 2
2 if k ≥ 3
k
λ (2 ) = .
k − 1
2 if k ≤ 2
∏
k
i
• For a positive integer n with prime factorization n = p ,
i
( )
k k
1 2
λ ( n ) = lcm λ ( p ) , λ ( p ) , . . .
1 2
∏ ∏
k k − 1
i i
Meanwhile, for n = p , we have ϕ ( n ) = ( p − 1) p . Hence the intuition is roughly that the
i
i i
ϕ ( n )
k − 1
i
( p − 1) p terms must share divisors in order to reach a high value of .
i
i
λ ( n )
ϕ ( n )
We will now show that n ≥ 240 by doing casework on the prime divisors of z = . Suppose p | z
λ ( n )
k k
1 2
and p > 2. This requires two terms among λ ( p ) , λ ( p ) , . . . to be multiples of p because λ ( n ) is the
1 2
lcm of the terms whereas the product of these numbers has the same number of factors of p as ϕ ( n )
k k − 1
(note that this does not hold for p = 2 because λ (2 ) 6 = 2 in general). These correspond to either
2
p | n or q | n with q ≡ 1 (mod p ). Therefore
2
n ≥ max( p (2 p + 1) , (2 p + 1)(4 p + 1))
because the smallest primes congruent to 1 (mod p ) are at least 2 p + 1 and 4 p + 1. For p ≥ 5 this gives
n > 240, so we may assume p ≤ 3.
First we address the case p = 3. This means that two numbers among 9 , 7 , 13 , 19 , 31 , 37 , . . . divide n .
As 7 × 37 > 240, we discard primes greater than 31. Of the remaining numbers, we have
λ (9) = 6 , λ (7) = 6 , λ (13) = 12 , λ (19) = 18 , λ (31) = 30 .
No candidate value of n is the product of just two of these numbers as the gcd of any two of the
associated λ values is at most 6. Furthermore, multiplying by just 2 will not affect ϕ ( n ) or λ ( n ), so
we must multiply at least two of these numbers by a number greater than 2. Throwing out numbers
greater than 240, this leaves only 3 × 9 × 7, which does not work. (A close candidate is 3 × 7 × 13 = 273,
for which ϕ ( n ) = 144 , λ ( n ) = 12.)
ϕ ( n )
The remaining case is when the only prime divisors of are 2. It is not hard to see that λ ( n ) ≥ 4
λ ( n )
when n - 24 (and when n | 24 it’s clear that φ ( n ) ≤ 8, so we do not need to consider them). When
4 4
λ ( n ) = 4, we need ϕ ( n ) ≥ 4 · 2 = 64 and v ( n ) ≤ 4, so the smallest such integer is n = 2 · 3 · 5 = 240,
2
ϕ ( n )
which we can check does indeed satisfy > 10. It is not difficult to check that higher values of λ ( n )
λ ( n )
will not yield any n below 240, so 240 is indeed the smallest possible n .
ϕ ( n )
is given by A034380 in the OEIS.
Note: The sequence
λ ( n )
H . Let r = H be the answer to this problem. Given that r is a nonzero real number, what is the value
1 1
4 3 2
of r + 4 r + 6 r + 4 r ?
Answer: − 1
4 3 2 4
Since H is the answer, we know r + 4 r + 6 r + 4 r = r ⇒ ( r + 1) = r + 1. Either r + 1 = 0, or
1
3
( r + 1) = 1 ⇒ r = 0. Since r is nonzero, r = − 1.
H . Given two distinct points A , B and line
that is not perpendicular to AB , what is the maximum 2 possible number of points P onsuch that ABP is an isosceles triangle? Answer: 5 In an isosceles triangle, one vertex lies on the perpendicular bisector of the opposite side. Thus, either P is the intersection of AB and, or P lies on the circle centered at A with radius AB , or P lies on the circle centered at B with radius AB . Each circle-line intersection has at most two solutions, and the line-line intersection has at most one, giving 5. This can be easily constructed by taking any AB , and takingthat isn’t a diameter but intersects both relevant circles twice. H . Let A = H , B = H + 1. A real number x is chosen randomly and uniformly in the interval [ A, B ]. 3 1 6 2 3 Find the probability that x > x > x . 1 Answer: 4 3 2 3 A = − 1 , B = 3. For x > x , either x > 1 or − 1 < x < 0. However, for x > 1, x < x , so there are no 2 3 solutions. − 1 < x < 0 also satisfies x > x , so our answer is 1 / 4. H . Let A = d 1 /H e , B = d H / 2 e . How many ways are there to partition the set { 1 , 2 , . . . , A + B } into 4 3 5 two sets U and V with size A and B respectively such that the probability that a number chosen from 1 U uniformly at random is greater than a number chosen from V uniformly at random is exactly ? 2 Answer: 24 A = 4 , B = 7. There are 28 total ways of choosing an element from U and V , so there must be 14 ways where U ’s is larger. If we relabel the elements to be 0 , 1 , · · · , 10, then element i is greater than exactly i elements in the set. However, we overcount other elements in U , so the four elements in U = { a, b, c, d } must satisfy ( a − 0) + ( b − 1) + ( c − 2) + ( d − 3) = 14 ⇒ a + b + c + d = 20 . To remove the uniqueness condition, we subtract 1 from b , 2 from c , and 3 from d , so we wish to find solutions a ≤ b ≤ c ≤ d ≤ 7 to a + b + c + d = 14. From here, we do casework. If a = 0, b = 0 , 1 , 2 , 3 , 4 give 1 , 1 , 2 , 2 , 3 solutions, respectively. If a = 1, b = 1 , 2 , 3 , 4 give 2 , 2 , 3 , 1 solutions, respectively. If a = 2, b = 2 , 3 , 4 give 3 , 2 , 1 solutions, respectively. If a = 3, the only solution is 3 , 3 , 4 , 4. Thus, the answer is (1 + 1 + 2 + 2 + 3) + (2 + 2 + 3 + 1) + (3 + 2 + 1) + 1 = 24. H . Let A = H , B = H . Two circles with radii A and B respectively are given in the plane. If the length 5 2 7 of their common external tangent is twice the length of their common internal tangent (where both tangents are considered as segments with endpoints being the points of tangency), find the distance between the two centers. √ 2 429 Answer: 3 Let the distance between the centers be d . The length of the common external tangent is E = √ √ √ 12 5 2 2 2 2 2 d − (7 − 5) = d − 4, and the length of the internal tangent is I = ( d ) − 5 . Solving the 5 12 √ 2 429 equation E = 2 I gives d = ( ≈ 13 . 8). 3 H . How many ways are there to arrange the numbers 21 , 22 , 33 , 35 in a row such that any two adjacent 6 numbers are relatively prime? Answer: 2 21 cannot be adjacent to 33 or 35, so it must be on one end bordering 22. 33 cannot be adjacent to 21 or 22, so it must be on the other end bording 35. Thus, there are only 2 orderings: 21, 22, 35, 33, and 33, 35, 22, 21. 2 2 H . How many pairs of integers ( x, y ) are there such that | x − 2 y | ≤ 1 and | 3 x − 4 y | ≤ 1? 7 Answer: 7 Note that if ( x, y ) is a solution, so is ( − x, − y ). Thus, we consider x ≥ 0. 2 When x ≡ 0 (mod 4), y = 3 x/ 4 by inequality 2. Inequality 1 gives | x / 9 | ≤ 1, so x ≤ 3, so x = 0. 2 2 When x ≡ 1 (mod 4), y = (3 x + 1) / 4 by inequality 2. Beyond x = 1, 2 y − x > 1, so there are no more solutions. When x ≡ 2 (mod 4), there are no solutions for y . 2 2 When x ≡ 3 (mod 4), y = (3 x − 1) / 4 by inequality 2. Beyond x = 7, 2 y − x > 1, so there are no more solutions. Thus, the solutions are (0 , 0) , (1 , 1) , (3 , 2) , (7 , 5), and the negations of the latter three, giving 7 solutions. M . Let S = M . Determine the number of ordered triples ( a, b, c ) of nonnegative integers such that 1 10 a + 2 b + 4 c = S . Answer: 196 S = 53. Firstly, the number of solutions is the same as the number of solutions to a + 2 b + 4 c = 52, since 2 b, 4 c are both even. Then, a + 2 b = 2 x has x + 1 solutions in nonnegative integers, so we wish 2 to find 27 + 25 + · · · + 1. This is the sum of the first 14 odd numbers, which is 14 = 196. M . Let S = b M c . Two integers m and n are chosen between 1 and S inclusive uniformly and independently 2 5 n m at random. What is the probability that m = n ? 7 Answer: 72 S = 12. The solutions are ( x, x ) for all x , and (2 , 4) , (4 , 2). Thus, there are S + 2 = 14 solutions out 2 of S = 196 possibilities, so the answer is 14 / 144 = 7 / 72. ◦ M . Let S = d M e . In right triangle ABC , ∠ C = 90 , AC = 27 , BC = 36. A circle with radius S is 3 7 tangent to both AC and BC and intersects AB at X and Y . Find the length of XY . √ Answer: 16 3 S = 14. We first note that the distance from the center of the circle to AB (which has length 27 · 36 − 27 · 14 − 36 · 14 45 by Pythagorean theorem) is = 2, so the length of the chord XY is equal to 45 √ √ 2 2 2 14 − 2 = 16 3. M . Let S = M + 5. Compute the product of all positive divisors of S . 4 13 Answer: 810000 S = 30 = 2 · 3 · 5. The divisors of S are 1 , 2 , 3 , 5 , 6 , 10 , 15 , 30. Each prime factor appears 4 times, so 4 4 4 4 the product is 2 3 5 = 30 = 810000. √ 1 1 M . Let A = M , B = d M e . Given complex numbers x and y such that x + = A , + y = B , compute 5 1 11 y x 1 the value of xy + . xy Answer: 12 A = 14 , B = 1. Multiplying the two given equations gives xy + 1 / ( xy ) + 2 = 14, so the answer is 14 − 2 = 12. 2 M . Let A = b 1 /M c , B = b M / 100 c . Let P and Q both be quadratic polynomials. Given that the real 6 2 3 roots of P ( Q ( x )) = 0 are 0 , A, B, C in some order, find the sum of all possible values of C . Answer: 17 A = 10 , B = 7. Let the roots of P ( x ) = 0 be p, q . Then, the roots of P ( Q ( x )) = 0 are when Q ( x ) = p or Q ( x ) = q . If these are r, s, t, u in order, then note that ( r + s ) / 2 = ( t + u ) / 2 must both be the center of the parabola Q . Thus, 0 , 10 , 7 , C must divide into two pairs with equal sum. When we consider the three possible groupings, we get that the possible values are 10+7 − 0 = 17 , 10+0 − 7 = 3 , 7+0 − 10 = − 3. Therefore the sum is 17 + ( − 3) + 3 = 17. M . Let A = d log M e , B = M + 1. A 5-term sequence of positive reals satisfy that the first three terms 7 4 12 2 and the last three terms both form an arithmetic sequence and the middle three terms form a geometric sequence. If the first term is A and the fifth term is B , determine the third term of the sequence. 40 Answer: 3 A = 20 , B = 8. If the middle term is x , then ( x + 20) / 2 , x, ( x + 8) / 2 forms a geometric series.This 2 means that ( x + 20) / 2 · ( x + 8) / 2 = x , which upon solving gives x = 40 / 3 or x = − 4 (which we discard because x > 0). 2 2 M . Let A = b M c , B = b M c . A regular A -gon, a regular B -gon, and a circle are given in the plane. 8 5 6 What is the greatest possible number of regions that these shapes divide the plane into? Answer: 1156 A = 144 , B = 289. First, note that with only the circle, there are 2 regions. If the three shapes never coincide at a point, then each intersection adds precisely one region. Optimistically, we wish to have the maximal number of intersections where all intersections have both shapes. The maximum number of intersections between the 289-gon and the circle is 578, since each side can only intersect the circle twice. Similarly, the 144-gon and the circle add at most 288. Finally, each side of the 144-gon can only intersect the 289-gon twice, so this adds another 288. This maximum can be achieved when all three shapes have the same circumcenter and circumradius, and are rotated slightly. The answer is 2 + 598 + 288 + 288 = 1156. M . Let A and B be the unit digits of d 7 M e and b 6 M c respectively. When all the positive integers not 9 6 7 th containing digit A or B are written in increasing order, what is the 2019 number in the list? Answer: 3743 A = 9 , B = 0. First, there are 8 numbers with 1 digit, 64 with two digits, and 512 with three digits. This leaves 2019 − 512 − 64 − 8 = 1435 of four-digit numbers we have to go through, starting with 1111. Since we don’t have two digits 0 and 9, we are basically counting in base 8, where the digits 01234567 in base 8 are actually 12345678, and 1111 = 0000 . Converting 1435 to base 8, we get 2633 , and 10 8 8 mapping this back, we get 3744. However, we must remember that 1111 is 0 under our mapping, so 8 th the 1435 four-digit number is actually 3743. M . What is the smallest positive integer with remainder 2 , 3 , 4 when divided by 3 , 5 , 7 respectively? 10 Answer: 53 We note that if we double the number then it leaves a remainder of 1 when divided by all of 3, 5, and