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 "1968 IMO Problems/Problem 6"

(Created page with "== Problem == For every natural number <math>n</math>, evaluate the sum <cmath>\sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = \Big[\frac{n + 1}{2}\Big] + \Big[\frac{...")
 
(→‎Solution)
Line 15: Line 15:
 
where <math>S</math> is the number of 1's in the binary representation of <math>n</math>. [[Legendre's Formula]] states that <math>n-S=\sum_{k=0}^{x} \bigg[\frac{n}{2^{k + 1}}\bigg]</math>, which proves the assertion. <math>\blacksquare</math>
 
where <math>S</math> is the number of 1's in the binary representation of <math>n</math>. [[Legendre's Formula]] states that <math>n-S=\sum_{k=0}^{x} \bigg[\frac{n}{2^{k + 1}}\bigg]</math>, which proves the assertion. <math>\blacksquare</math>
  
−
{{alternate solutions}}
+
 
 +
== Solution 2 ==
 +
We observe
 +
<cmath>n \equiv 2^k \text{mod }2^{k+1} \longrightarrow \left[\frac{n+1+2^k}{2^{k+1}}\right] - \left[\frac{n+2^k}{2^{k+1}}\right] = 1 \text{ and } \left[\frac{n+1+2^k}{2^{k+1}}\right] - \left[\frac{n+2^k}{2^{k+1}}\right] = 0 \text{ otherwise.}</cmath>
 +
 
 +
But <cmath>D = [d \text{ } | \text{ } \exists \text{ } s \in \mathbb{N} \text{ such that } d \equiv 2^{s-1} \text{ mod } 2^s] = \mathbb{N} \longrightarrow \sum_{k = 0}^\infty\bigg[\frac{n+1 + 2^k}{2^{k + 1}}\bigg] - \sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = 1,</cmath>
 +
 
 +
so the result is just <math>n</math>. <math>\square</math>
 +
 
 +
~ilovepi3.14
  
 
== Resources ==
 
== Resources ==

Revision as of 00:07, 26 August 2019

Problem

For every natural number $n$, evaluate the sum \[\sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = \Big[\frac{n + 1}{2}\Big] + \Big[\frac{n + 2}{4}\Big] + \cdots + \bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] + \cdots\] (The symbol $[x]$ denotes the greatest integer not exceeding $x$.)

Solution

I shall prove that the summation is equal to $n$.

Let the binary representation of $n$ be $\overline{d_xd_{x-1}\dots d_1d_0}_2$, where $d_i\in\{0,1\}$ for all $i$, and $x=\lfloor \log_2 n\rfloor$. Note that if $d_i=0$, then $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=\Big[\frac{n}{2^{i+1}}\Big]$; and if $d_i=1$, then $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=\Big[\frac{n}{2^{i+1}}\Big]+1$. Also note that $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=0$ for all $i\geq x+1$. Therefore the given sum is equal to

\[\sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] =S+\sum_{k=0}^{x} \bigg[\frac{n}{2^{k + 1}}\bigg]\]

where $S$ is the number of 1's in the binary representation of $n$. Legendre's Formula states that $n-S=\sum_{k=0}^{x} \bigg[\frac{n}{2^{k + 1}}\bigg]$, which proves the assertion. $\blacksquare$


Solution 2

We observe \[n \equiv 2^k \text{mod }2^{k+1} \longrightarrow \left[\frac{n+1+2^k}{2^{k+1}}\right] - \left[\frac{n+2^k}{2^{k+1}}\right] = 1 \text{ and } \left[\frac{n+1+2^k}{2^{k+1}}\right] - \left[\frac{n+2^k}{2^{k+1}}\right] = 0 \text{ otherwise.}\]

But \[D = [d \text{ } | \text{ } \exists \text{ } s \in \mathbb{N} \text{ such that } d \equiv 2^{s-1} \text{ mod } 2^s] = \mathbb{N} \longrightarrow \sum_{k = 0}^\infty\bigg[\frac{n+1 + 2^k}{2^{k + 1}}\bigg] - \sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = 1,\]

so the result is just $n$. $\square$

~ilovepi3.14

Resources

1968 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last Problem
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1968_IMO_Problems/Problem_6&oldid=109381"