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 "2013 USAJMO Problems/Problem 4"
Line 1: Line 1:
 +
==Problem==
 
Let <math>f(n)</math> be the number of ways to write <math>n</math> as a sum of powers of <math>2</math>, where we keep track of the order of the summation.  For example, <math>f(4)=6</math> because <math>4</math> can be written as <math>4</math>, <math>2+2</math>, <math>2+1+1</math>, <math>1+2+1</math>, <math>1+1+2</math>, and <math>1+1+1+1</math>.  Find the smallest <math>n</math> greater than <math>2013</math> for which <math>f(n)</math> is odd.
 
Let <math>f(n)</math> be the number of ways to write <math>n</math> as a sum of powers of <math>2</math>, where we keep track of the order of the summation.  For example, <math>f(4)=6</math> because <math>4</math> can be written as <math>4</math>, <math>2+2</math>, <math>2+1+1</math>, <math>1+2+1</math>, <math>1+1+2</math>, and <math>1+1+1+1</math>.  Find the smallest <math>n</math> greater than <math>2013</math> for which <math>f(n)</math> is odd.
 +
 +
==Solution==
 +
 +
First of all, note that <math>f(n)</math> = <math>\sum_{1}^{k} f(n-2^{k})</math> where <math>k</math> is the largest integer such that <math>2^k \le n</math>.  We let <math>f(0) = 1</math> for convenience. 
 +
 +
From here, we proceed by induction, with our claim being that the only <math>n</math> such that <math>f(n)</math> is odd are <math>n</math> representable of the form <math>2^{a} - 1, a \in \mathbb{Z}</math>

Revision as of 19:55, 11 May 2013

Problem

Let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$, where we keep track of the order of the summation. For example, $f(4)=6$ because $4$ can be written as $4$, $2+2$, $2+1+1$, $1+2+1$, $1+1+2$, and $1+1+1+1$. Find the smallest $n$ greater than $2013$ for which $f(n)$ is odd.

Solution

First of all, note that $f(n)$ = $\sum_{1}^{k} f(n-2^{k})$ where $k$ is the largest integer such that $2^k \le n$. We let $f(0) = 1$ for convenience.

From here, we proceed by induction, with our claim being that the only $n$ such that $f(n)$ is odd are $n$ representable of the form $2^{a} - 1, a \in \mathbb{Z}$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_USAJMO_Problems/Problem_4&oldid=52742"