Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 AIME II Problems/Problem 14"

(Created page with ":D")
 
(→‎Solution)
 
(4 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
:D
+
==Problem==
 +
Let \(b\ge 2\) be an integer. Call a positive integer \(n\) \(b\text-\textit{eautiful}\) if it has exactly two digits when expressed in base \(b\)  and these two digits sum to \(\sqrt n\). For example, \(81\) is \(13\text-\textit{eautiful}\) because \(81  = \underline{6} \ \underline{3}_{13} \) and \(6 + 3 =  \sqrt{81}\). Find the least integer \(b\ge 2\) for which there are more than ten \(b\text-\textit{eautiful}\) integers.
 +
 
 +
==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==
 +
{{AIME box|year=2024|num-b=13|num-a=15|n=II}}
 +
 
 +
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 12:20, 3 September 2024

Problem

Let \(b\ge 2\) be an integer. Call a positive integer \(n\) \(b\text-\textit{eautiful}\) if it has exactly two digits when expressed in base \(b\) and these two digits sum to \(\sqrt n\). For example, \(81\) is \(13\text-\textit{eautiful}\) because \(81 = \underline{6} \ \underline{3}_{13} \) and \(6 + 3 = \sqrt{81}\). Find the least integer \(b\ge 2\) for which there are more than ten \(b\text-\textit{eautiful}\) integers.

Solution

We write the base-$b$ two-digit integer as $\left( xy \right)_b$. Thus, this number satisfies \[ \left( x + y \right)^2 = b x + y \] with $x \in \left\{ 1, 2, \cdots , b-1 \right\}$ and $y \in \left\{ 0, 1, \cdots , b - 1 \right\}$.

The above conditions imply $\left( x + y \right)^2 < b^2$. Thus, $x + y \leq b - 1$.

The above equation can be reorganized as \[ \left( x + y \right) \left( x + y - 1 \right) = \left( b - 1 \right) x . \]

Denote $z = x + y$ and $b' = b - 1$. Thus, we have \[ z \left( z - 1 \right) = b' x , \hspace{1cm} (1) \] where $z \in \left\{ 2, 3, \cdots , b' \right\}$ and $x \in \left\{ 1, 2, \cdots , b' \right\}$.

Next, for each $b'$, we solve Equation (1).

We write $b'$ in the prime factorization form as $b' = \Pi_{i=1}^n p_i^{k_i}$. Let $\left(A, \bar A \right)$ be any ordered partition of $\left\{ 1, 2, \cdots , n \right\}$ (we allow one set to be empty). Denote $P_A = \Pi_{i \in A} p_i^{k_i}$ and $P_{\bar A} = \Pi_{i \in \bar A} p_i^{k_i}$.

Because ${\rm gcd} \left( z, z-1 \right) = 1$, there must exist such an ordered partition, such that $P_A | z$ and $P_{\bar A} | z-1$.

Next, we prove that for each ordered partition $\left( A, \bar A \right)$, if a solution of $z$ exists, then it must be unique.

Suppose there are two solutions of $z$ under partition $\left( A, \bar A \right)$: $z_1 = c_1 P_A$, $z_1 - 1 = d_1 P_{\bar A}$, and $z_2 = c_2 P_A$, $z_2 - 1 = d_2 P_{\bar A}$. W.L.O.G., assume $c_1 < c_2$. Hence, we have \[ \left( c_2 - c_1 \right) P_A = \left( d_2 - d_1 \right) P_{\bar A} . \]

Because ${\rm gcd} \left( P_A, P_{\bar A} \right) = 1$ and $c_1 < c_2$, there exists a positive integer $m$, such that $c_2 = c_1 + m P_{\bar A}$ and $d_2 = d_1 + m P_A$. Thus, \begin{align*} z_2 & = z_1 + m P_A P_{\bar A} \\ & = z_1 + m b' \\ & > b' . \end{align*}

However, recall $z_2 \leq b'$. We get a contradiction. Therefore, under each ordered partition for $b'$, the solution of $z$ is unique.

Note that if $b'$ has $n$ distinct prime factors, the number of ordered partitions is $2^n$. Therefore, to find a $b'$ such that the number of solutions of $z$ is more than 10, the smallest $n$ is 4.

With $n = 4$, the smallest number is $2 \cdot 3 \cdot 5 \cdot 7 = 210$. Now, we set $b' = 210$ and check whether the number of solutions of $z$ under this $b'$ is more than 10.

We can easily see that all ordered partitions (except $A = \emptyset$) guarantee feasible solutions of $z$. Therefore, we have found a valid $b'$. Therefore, $b = b' + 1 = \boxed{\textbf{(211) }}$.

~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

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AIME_II_Problems/Problem_14&oldid=226307"