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 "2023 SSMO Team Round Problems/Problem 12"

(Created page with "==Problem== Let <math>T</math> be the set of rationals of the form <math>\frac{a}{2^b}</math> for nonnegative <math>a</math> and <math>b</math>. Define the function <math>f \c...")
 
 
Line 13: Line 13:
  
 
==Solution==
 
==Solution==
 +
Define 
 +
<cmath>S_n = \sum_{i=0}^{2^n-1} \frac{f\left(\frac{i+1}{2^n}\right)}{f\left(\frac{i}{2^n}\right)}</cmath> 
 +
for <math>n \ge 1</math>. We want to find <math>S_{10}</math>.
 +
 +
We claim by induction that 
 +
<cmath>S_n = \frac{5}{2} + 3 \cdot (2^{n-1} - 1).</cmath>
 +
 +
The base case is <math>S_1 = \frac{f(\frac{1}{2})}{f(0)} + \frac{f(1)}{f(\frac{1}{2})} = \frac{3}{2} + 1 = \frac{5}{2}</math>, so it holds.
 +
 +
Now suppose the formula holds for some <math>n</math>. Note that for <math>t \in [0,1]</math>, by symmetry we have <math>f(t) = f(1 - t)</math>.
 +
 +
Next, observe:
 +
\begin{align*}
 +
S_{n+1} &= \sum_{i=0}^{2^{n+1}-1} \frac{f\left(\frac{i+1}{2^{n+1}}\right)}{f\left(\frac{i}{2^{n+1}}\right)} \\
 +
&= \sum_{i=0}^{2^{n}-1} \left[ \frac{f\left(\frac{2i+1}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i+1}{2^{n+1}}\right)} \right].
 +
\end{align*}
 +
 +
Since <math>f\left(\frac{2i+1}{2^{n+1}}\right) = f\left(\frac{2i}{2^{n+1}}\right) + f\left(\frac{2i+2}{2^{n+1}}\right)</math>, the two terms become:
 +
\begin{align*}
 +
&\frac{f\left(\frac{2i}{2^{n+1}}\right) + f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i}{2^{n+1}}\right) + f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)} \\
 +
&= 1 + \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + 1 + \frac{f\left(\frac{2i}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)} = 2 + \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)}.
 +
\end{align*}
 +
 +
Summing over <math>i</math> from <math>0</math> to <math>2^{n-1} - 1</math>, we get:
 +
\begin{align*}
 +
S_{n+1} &= \sum_{i=0}^{2^{n-1} - 1} \left(2 + \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)}\right) \\
 +
&= 2 \cdot 2^{n-1} + \sum_{i=0}^{2^{n-1}-1} \left( \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)} \right) \\
 +
&= 2^{n} + S_n + 2^{n} = S_n + 3 \cdot 2^{n-1}.
 +
\end{align*}
 +
 +
So the recurrence is valid.
 +
 +
Applying the closed-form:
 +
<cmath>S_{10} = \frac{5}{2} + 3 \cdot (2^9 - 1) = \frac{5}{2} + 3 \cdot 511 = \frac{5}{2} + 1533 = \frac{3071}{2},</cmath> 
 +
so the final answer is <math>\boxed{3073}</math>.
 +
 +
~SMO_Team

Latest revision as of 21:33, 9 September 2025

Problem

Let $T$ be the set of rationals of the form $\frac{a}{2^b}$ for nonnegative $a$ and $b$. Define the function $f \colon T \to \mathbb{Z}$ such that, for $t = \frac{a}{2^b}$ such $b$ is minimal, we have that \[f\left(\frac{a}{2^b}\right) = \begin{cases} 1 & b = 0 \\ f\left(\frac{a-1}{2^b}\right) + f\left(\frac{a+1}{2^b}\right) & b \ne 0 \\ \end{cases}\]

Suppose \[\sum_{i=0}^{2^{10} - 1} \frac{f\left(\frac{i+1}{2^{10}}\right)}{f\left(\frac{i}{2^{10}}\right)}\] equals $\frac{m}{n}$. Find $m+n$.

Solution

Define \[S_n = \sum_{i=0}^{2^n-1} \frac{f\left(\frac{i+1}{2^n}\right)}{f\left(\frac{i}{2^n}\right)}\] for $n \ge 1$. We want to find $S_{10}$.

We claim by induction that \[S_n = \frac{5}{2} + 3 \cdot (2^{n-1} - 1).\]

The base case is $S_1 = \frac{f(\frac{1}{2})}{f(0)} + \frac{f(1)}{f(\frac{1}{2})} = \frac{3}{2} + 1 = \frac{5}{2}$, so it holds.

Now suppose the formula holds for some $n$. Note that for $t \in [0,1]$, by symmetry we have $f(t) = f(1 - t)$.

Next, observe: \begin{align*} S_{n+1} &= \sum_{i=0}^{2^{n+1}-1} \frac{f\left(\frac{i+1}{2^{n+1}}\right)}{f\left(\frac{i}{2^{n+1}}\right)} \\ &= \sum_{i=0}^{2^{n}-1} \left[ \frac{f\left(\frac{2i+1}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i+1}{2^{n+1}}\right)} \right]. \end{align*}

Since $f\left(\frac{2i+1}{2^{n+1}}\right) = f\left(\frac{2i}{2^{n+1}}\right) + f\left(\frac{2i+2}{2^{n+1}}\right)$, the two terms become: \begin{align*} &\frac{f\left(\frac{2i}{2^{n+1}}\right) + f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i}{2^{n+1}}\right) + f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)} \\ &= 1 + \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + 1 + \frac{f\left(\frac{2i}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)} = 2 + \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)}. \end{align*}

Summing over $i$ from $0$ to $2^{n-1} - 1$, we get: \begin{align*} S_{n+1} &= \sum_{i=0}^{2^{n-1} - 1} \left(2 + \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)}\right) \\ &= 2 \cdot 2^{n-1} + \sum_{i=0}^{2^{n-1}-1} \left( \frac{f\left(\frac{2i+2}{2^{n+1}}\right)}{f\left(\frac{2i}{2^{n+1}}\right)} + \frac{f\left(\frac{2i}{2^{n+1}}\right)}{f\left(\frac{2i+2}{2^{n+1}}\right)} \right) \\ &= 2^{n} + S_n + 2^{n} = S_n + 3 \cdot 2^{n-1}. \end{align*}

So the recurrence is valid.

Applying the closed-form: \[S_{10} = \frac{5}{2} + 3 \cdot (2^9 - 1) = \frac{5}{2} + 3 \cdot 511 = \frac{5}{2} + 1533 = \frac{3071}{2},\] so the final answer is $\boxed{3073}$.

~SMO_Team

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_SSMO_Team_Round_Problems/Problem_12&oldid=260191"