Difference between revisions of "2013 USAJMO Problems/Problem 4"
Mathboy100 (talk | contribs) (→Solution with Explanations) |
|||
(8 intermediate revisions by 6 users not shown) | |||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
− | First of all, note that <math>f(n)</math> = <math>\sum_{i= | + | First of all, note that <math>f(n)</math> = <math>\sum_{i=0}^{k} f(n-2^{i})</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> | 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> | ||
− | We induct on <math>a</math>. It is trivially true for <math>a = 0</math> and <math>a = 1</math>. From here, we show that, if the only numbers <math>n \le 2^{a-1} - 1</math> where <math>f(n)</math> is odd are of the form described above, then the only numbers <math>n \le 2^{a} -1</math> that are odd are of that form. We first consider all numbers <math>b</math>, such that <math>2^{a-1} \le b \le 2^{a} - 2</math>, going from the lower bound to the upper bound (a mini induction, you might say). We know that <math>f(b) = \sum_{i= | + | We induct on <math>a</math>. It is trivially true for <math>a = 0</math> and <math>a = 1</math>. From here, we show that, if the only numbers <math>n \le 2^{a-1} - 1</math> where <math>f(n)</math> is odd are of the form described above, then the only numbers <math>n \le 2^{a} -1</math> that are odd are of that form. We first consider all numbers <math>b</math>, such that <math>2^{a-1} \le b \le 2^{a} - 2</math>, going from the lower bound to the upper bound (a mini induction, you might say). We know that <math>f(b) = \sum_{i=0}^{a-1} f(b-2^{i})</math>. For a number in this summation to be odd, <math>b - 2^i = 2^m -1 \rightarrow b = 2^i + 2^m - 1</math>. However, we know that <math>b > 2^{a-1}</math>, so <math>m</math> must be equal to <math>a-1</math>, or else <math>b</math> cannot be in that interval. Now, from this, we know that <math>i < a-1</math>, as <math>b<2^{a} - 1</math>. Therefore, <math>i</math> and <math>m</math> are distinct, and thus <math>f(b - 2^i)</math> and <math>f(b- 2^{a-1})</math> are odd; since there are just two odd numbers, the ending sum for any <math>b</math> is even. Finally, considering <math>2^{a} - 1</math>, the only odd number is <math>f(2^{a} - 1 - 2^{a-1})</math>, so the ending sum is odd. <math>\Box</math> |
The smallest <math>n</math> greater than <math>2013</math> expressible as <math>2^d - 1, d \in \mathbb{N}</math> is <math>2^{11} -1 = \boxed{2047}</math> | The smallest <math>n</math> greater than <math>2013</math> expressible as <math>2^d - 1, d \in \mathbb{N}</math> is <math>2^{11} -1 = \boxed{2047}</math> | ||
+ | |||
+ | ==Solution with Explanations== | ||
+ | Of course, as with any number theory problem, use actual numbers to start, not variables! By plotting out the first few sums (do it!) and looking for patterns, we observe that <math>f(n)=\sum_{\textrm{power}=0}^{\textrm{pow}_{\textrm{larg}}} f(n-2^{\textrm{power}})</math>, where <math>\textrm{pow}_{\textrm{larg}}</math> represents the largest power of <math>2</math> that is smaller than <math>n</math>. I will call this sum the Divine Sign, or DS. | ||
+ | |||
+ | But wait a minute... we are trying to determine odd/even of <math>f(n)</math>. Why not call all the evens 0 and odds 1, basically using mod 2? Sounds so simple. Draw a small table for the values: as <math>n</math> goes up from <math>0</math>, you get: <math>1,1,0,1,0,0,0,1,0...</math>. We have to set <math>f(0)=1</math> for this to work. Already it looks like <math>f(n)</math> is only odd if <math>n=2^{\textrm{power}}-1</math>. | ||
+ | |||
+ | The only tool here is induction. The base case is clearly established. Then let's assume we successfully made our claim up to <math>2^n-1</math>. We need to visit numbers from <math>2^n</math> to <math>2^{n+1}-1</math>. Realize that <math>2^n</math> has <math>0</math> for <math>f</math> because there will be two numbers in DS that give a <math>f</math> of one: <math>2^{n-1}</math> and <math>1</math>. | ||
+ | |||
+ | But to look at whether a value of <math>f(\textrm{number})</math> is 1 or 0, we need to revisit our first equation. We can answer this rather natural question: When will a number to be inducted upon, say <math>2^n+k</math>, ever have a 1 as <math>f(\textrm{number})</math> in the DS equation? Well- because by our assumption of the claim up to <math>2^n-1</math>, we know that the only way for that to happen is if <math>2^n+k-2^{\textrm{power}}</math> in the DS is equal to <math>2^{\textrm{Some power}} - 1</math>. Clearly <math>1 \leq k \leq 2^n - 1</math>. | ||
+ | |||
+ | Finally, we can simplify. Using our last equation, <math>2^n+k-2^{\textrm{power}}=2^{\textrm{Some power}}-1</math>, regrouping gives <math>2^n+k=2^{\textrm{power}}+2^{\textrm{Some power}}-1</math>. | ||
+ | |||
+ | Most importantly, realize that <math>\textrm{power}</math> can be from <math>0</math> to <math>n</math>, because of the restraints on <math>k</math> mentioned earlier. Same with <math>\textrm{Some power}</math>. Immediately at least one of <math>\textrm{power}</math> and <math>\textrm{Some power}</math> has to be <math>n</math>. If both were smaller, LHS is greater, contradiction. If both were greater, RHS is greater, contradiction. | ||
+ | |||
+ | Therefore, by setting one of <math>\textrm{power}</math> or <math>\textrm{Some power}</math> to <math>n</math>, we realize <math>k=2^{\textrm{A certain power}}-1</math>. | ||
+ | |||
+ | The conclusion is clear, right? Each <math>k</math> from <math>1</math> to <math>2^{n-1}-1</math> yields two distinct cases: one of <math>\textrm{power}</math> and <math>\textrm{Some power}</math> is equal to <math>n</math>, while the other is LESS THAN <math>n</math>. But for <math>k=2^n-1</math>, there is ONE CASE: BOTH values have to equal <math>n</math>. Therefore, the only <math>k</math> that has <math>f(2^n+k)</math> as odd must only be <math>2^n-1</math>, because the other ones yield a <math>f</math> of 1+1=0 in our mod. That proves our induction for a new power of 2, namely <math>n+1</math>, meaning that <math>f(\textrm{number})</math> is only odd if <math>\textrm{number} = 2^{\textrm{Power of two}} - 1</math>, and we are almost done... | ||
+ | |||
+ | Thus, the answer is <math>2^{11}-1=\boxed{2047}</math>. | ||
+ | |||
+ | This was pretty intuitive, and realizing quite <math>elementary</math> steps about how powers of 2 work gave us the solution! Estimated time: ~50 minutes. | ||
+ | |||
+ | ~expiLnCalc. | ||
+ | |||
+ | minor edits ~mathboy100 | ||
+ | |||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 14:05, 28 November 2022
Problem
Let be the number of ways to write
as a sum of powers of
, where we keep track of the order of the summation. For example,
because
can be written as
,
,
,
,
, and
. Find the smallest
greater than
for which
is odd.
Solution
First of all, note that =
where
is the largest integer such that
. We let
for convenience.
From here, we proceed by induction, with our claim being that the only such that
is odd are
representable of the form
We induct on . It is trivially true for
and
. From here, we show that, if the only numbers
where
is odd are of the form described above, then the only numbers
that are odd are of that form. We first consider all numbers
, such that
, going from the lower bound to the upper bound (a mini induction, you might say). We know that
. For a number in this summation to be odd,
. However, we know that
, so
must be equal to
, or else
cannot be in that interval. Now, from this, we know that
, as
. Therefore,
and
are distinct, and thus
and
are odd; since there are just two odd numbers, the ending sum for any
is even. Finally, considering
, the only odd number is
, so the ending sum is odd.
The smallest greater than
expressible as
is
Solution with Explanations
Of course, as with any number theory problem, use actual numbers to start, not variables! By plotting out the first few sums (do it!) and looking for patterns, we observe that , where
represents the largest power of
that is smaller than
. I will call this sum the Divine Sign, or DS.
But wait a minute... we are trying to determine odd/even of . Why not call all the evens 0 and odds 1, basically using mod 2? Sounds so simple. Draw a small table for the values: as
goes up from
, you get:
. We have to set
for this to work. Already it looks like
is only odd if
.
The only tool here is induction. The base case is clearly established. Then let's assume we successfully made our claim up to . We need to visit numbers from
to
. Realize that
has
for
because there will be two numbers in DS that give a
of one:
and
.
But to look at whether a value of is 1 or 0, we need to revisit our first equation. We can answer this rather natural question: When will a number to be inducted upon, say
, ever have a 1 as
in the DS equation? Well- because by our assumption of the claim up to
, we know that the only way for that to happen is if
in the DS is equal to
. Clearly
.
Finally, we can simplify. Using our last equation, , regrouping gives
.
Most importantly, realize that can be from
to
, because of the restraints on
mentioned earlier. Same with
. Immediately at least one of
and
has to be
. If both were smaller, LHS is greater, contradiction. If both were greater, RHS is greater, contradiction.
Therefore, by setting one of or
to
, we realize
.
The conclusion is clear, right? Each from
to
yields two distinct cases: one of
and
is equal to
, while the other is LESS THAN
. But for
, there is ONE CASE: BOTH values have to equal
. Therefore, the only
that has
as odd must only be
, because the other ones yield a
of 1+1=0 in our mod. That proves our induction for a new power of 2, namely
, meaning that
is only odd if
, and we are almost done...
Thus, the answer is .
This was pretty intuitive, and realizing quite steps about how powers of 2 work gave us the solution! Estimated time: ~50 minutes.
~expiLnCalc.
minor edits ~mathboy100
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.