Difference between revisions of "2024 AIME II Problems/Problem 14"
(→Solution) |
|||
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
Let | Let | ||
+ | |||
+ | ==Solution== | ||
+ | |||
+ | We write the base-<math>b</math> two-digit integer as <math>\left( xy \right)_b</math>. | ||
+ | Thus, this number satisfies | ||
+ | <cmath> | ||
+ | \[ | ||
+ | \left( x + y \right)^2 = b x + y | ||
+ | \] | ||
+ | </cmath> | ||
+ | with <math>x \in \left\{ 1, 2, \cdots , b-1 \right\}</math> and <math>y \in \left\{ 0, 1, \cdots , b - 1 \right\}</math>. | ||
+ | |||
+ | The above conditions imply <math>\left( x + y \right)^2 < b^2</math>. Thus, <math>x + y \leq b - 1</math>. | ||
+ | |||
+ | The above equation can be reorganized as | ||
+ | <cmath> | ||
+ | \[ | ||
+ | \left( x + y \right) \left( x + y - 1 \right) | ||
+ | = \left( b - 1 \right) x . | ||
+ | \] | ||
+ | </cmath> | ||
+ | |||
+ | Denote <math>z = x + y</math> and <math>b' = b - 1</math>. | ||
+ | Thus, we have | ||
+ | <cmath> | ||
+ | \[ | ||
+ | z \left( z - 1 \right) = b' x , \hspace{1cm} (1) | ||
+ | \] | ||
+ | </cmath> | ||
+ | where <math>z \in \left\{ 2, 3, \cdots , b' \right\}</math> and <math>x \in \left\{ 1, 2, \cdots , b' \right\}</math>. | ||
+ | |||
+ | Next, for each <math>b'</math>, we solve Equation (1). | ||
+ | |||
+ | We write <math>b'</math> in the prime factorization form as <math>b' = \Pi_{i=1}^n p_i^{k_i}</math>. | ||
+ | Let <math>\left(A, \bar A \right)</math> be any ordered partition of <math>\left\{ 1, 2, \cdots , n \right\}</math> (we allow one set to be empty). | ||
+ | Denote <math>P_A = \Pi_{i \in A} p_i^{k_i}</math> and <math>P_{\bar A} = \Pi_{i \in \bar A} p_i^{k_i}</math>. | ||
+ | |||
+ | Because <math>{\rm gcd} \left( z, z-1 \right) = 1</math>, there must exist such an ordered partition, such that <math>P_A | z</math> and <math>P_{\bar A} | z-1</math>. | ||
+ | |||
+ | Next, we prove that for each ordered partition <math>\left( A, \bar A \right)</math>, if a solution of <math>z</math> exists, then it must be unique. | ||
+ | |||
+ | Suppose there are two solutions of <math>z</math> under partition <math>\left( A, \bar A \right)</math>: <math>z_1 = c_1 P_A</math>, <math>z_1 - 1 = d_1 P_{\bar A}</math>, and <math>z_2 = c_2 P_A</math>, <math>z_2 - 1 = d_2 P_{\bar A}</math>. | ||
+ | W.L.O.G., assume <math>c_1 < c_2</math>. | ||
+ | Hence, we have | ||
+ | <cmath> | ||
+ | \[ | ||
+ | \left( c_2 - c_1 \right) P_A | ||
+ | = \left( d_2 - d_1 \right) P_{\bar A} . | ||
+ | \] | ||
+ | </cmath> | ||
+ | |||
+ | Because <math>{\rm gcd} \left( P_A, P_{\bar A} \right) = 1</math> and <math>c_1 < c_2</math>, there exists a positive integer <math>m</math>, such that <math>c_2 = c_1 + m P_{\bar A}</math> and <math>d_2 = d_1 + m P_A</math>. | ||
+ | Thus, | ||
+ | \begin{align*} | ||
+ | z_2 & = z_1 + m P_A P_{\bar A} \ | ||
+ | & = z_1 + m b' \ | ||
+ | & > b' . | ||
+ | \end{align*} | ||
+ | |||
+ | However, recall <math>z_2 \leq b'</math>. We get a contradiction. | ||
+ | Therefore, under each ordered partition for <math>b'</math>, the solution of <math>z</math> is unique. | ||
+ | |||
+ | Note that if <math>b'</math> has <math>n</math> distinct prime factors, the number of ordered partitions is <math>2^n</math>. | ||
+ | Therefore, to find a <math>b'</math> such that the number of solutions of <math>z</math> is more than 10, the smallest <math>n</math> is 4. | ||
+ | |||
+ | With <math>n = 4</math>, the smallest number is <math>2 \cdot 3 \cdot 5 \cdot 7 = 210</math>. | ||
+ | Now, we set <math>b' = 210</math> and check whether the number of solutions of <math>z</math> under this <math>b'</math> is more than 10. | ||
+ | |||
+ | We can easily see that all ordered partitions (except <math>A = \emptyset</math>) guarantee feasible solutions of <math>z</math>. | ||
+ | Therefore, we have found a valid <math>b'</math>. | ||
+ | Therefore, <math>b = b' + 1 = \boxed{\textbf{(211) }}</math>. | ||
+ | |||
+ | ~Shen Kislay Kai and Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | https://youtu.be/N7rLL1Xt9go | ||
+ | |||
+ | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | https://youtu.be/0FCGY9xfEq0?si=9Fu4owVaSm-WWxFJ | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
==See also== | ==See also== | ||
{{AIME box|year=2024|num-b=13|num-a=15|n=II}} | {{AIME box|year=2024|num-b=13|num-a=15|n=II}} | ||
− | [[Category:Intermediate | + | [[Category:Intermediate Number Theory Problems]] |
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 12:20, 3 September 2024
Problem
Let
Solution
We write the base- two-digit integer as . Thus, this number satisfies with and .
The above conditions imply . Thus, .
The above equation can be reorganized as
Denote and . Thus, we have where and .
Next, for each , we solve Equation (1).
We write in the prime factorization form as . Let be any ordered partition of (we allow one set to be empty). Denote and .
Because , there must exist such an ordered partition, such that and .
Next, we prove that for each ordered partition , if a solution of exists, then it must be unique.
Suppose there are two solutions of under partition : , , and , . W.L.O.G., assume . Hence, we have
Because and , there exists a positive integer , such that and .
Thus,
However, recall . We get a contradiction. Therefore, under each ordered partition for , the solution of is unique.
Note that if has distinct prime factors, the number of ordered partitions is . Therefore, to find a such that the number of solutions of is more than 10, the smallest is 4.
With , the smallest number is . Now, we set and check whether the number of solutions of under this is more than 10.
We can easily see that all ordered partitions (except ) guarantee feasible solutions of . Therefore, we have found a valid . Therefore, .
~Shen Kislay Kai and Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
https://youtu.be/0FCGY9xfEq0?si=9Fu4owVaSm-WWxFJ
~MathProblemSolvingSkills.com
See also
2024 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.