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

2023 SSMO Team Round Problems/Problem 12

Revision as of 21:33, 9 September 2025 by Pinkpig (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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"