Olympiad Maths Prep

Track / Stage 6 / 223 of 400 #1223 of 2000

Problem 1223

National olympiad, first round
Number theory Difficulty 6.4 Find the answer

p1. Some natural numbers can be written as the sum of consecutive natural numbers. For example: 5=2+35 = 2 + 3, 6=1+2+36 = 1 + 2 + 3, 10=1+2+3+410 = 1 + 2 + 3 + 4, 25=3+4+5+6+725 = 3 + 4 + 5 + 6 + 7. However, this is not possible with all natural numbers. Determine with what numbers it is not possible and prove such impossibility.

p2. Show that number 22+25+2j2^2+2^5+2^j is a perfect square only for the case j=6j = 6.

p3. You have the numbers from 1 1 to 100100 and each one of them is painted in one of the four colors red, blue, yellow or green. Show that there are two numbers of the same color, whose difference is also the same color.

p4. ABCDABCD is a trapezoid, ABIEABIE is a parallelogram where EE is the midpoint of ADAD; FF is the midpoint of BCBC; the points GG and HH are the intersection of the segment EIEI with the diagonals of the trapezoid. Show that if AB/FI=2001AB/FI = 2001, then DC/GH=1999DC/GH = 1999.

p5. Determine all integer solutions of the equation 1x+1y=12\frac{1}{x}+\frac{1}{y}=\frac{1}{2}.

PS. Wording of P4 has been corrected thanks to vanstraelen.

Official solution

1. Define the Problem:
We need to determine which natural numbers cannot be written as the sum of consecutive natural numbers and prove such impossibility.

2. Claim 1:
If n n has an odd divisor k>1 k > 1 , then n n is a beautiful number (i.e., it can be written as the sum of consecutive natural numbers).

Proof:
- If n n is an odd number, then we can write n=a+(a+1) n = a + (a + 1) with a=n12 a = \frac{n-1}{2} .
- If n n is an even number, then write n=2st n = 2^s \cdot t with t>1 t > 1 being an odd number.
- Let b=t12 b = \frac{t-1}{2} .
- If 2sb 2^s \ge b , then we can write n=i+(i+1)++(i+t1)=t(i+b) n = i + (i+1) + \ldots + (i+t-1) = t(i+b) with i=2sb i = 2^s - b .
- If b>2s b > 2^s , then we can write n=[b(2s1)]+[b(2s2)]++b+(b+1)++(b+2s) n = [b - (2^s - 1)] + [b - (2^s - 2)] + \ldots + b + (b+1) + \ldots + (b + 2^s) .

3. Claim 2:
If n n is a beautiful number, then there exists an odd natural number k>1 k > 1 such that kn k \mid n .

Proof:
- Since n n is a beautiful number, there exist i,hN,h>1 i, h \in \mathbb{N}, h > 1 such that
n=i+(i+1)+(i+2)++(i+h1)=h(i+h12) n = i + (i+1) + (i+2) + \ldots + (i+h-1) = h \left( i + \frac{h-1}{2} \right)
- If h h is odd, then h12N \frac{h-1}{2} \in \mathbb{N} , so hn h \mid n and we are done.
- If h h is even, then
n=h2(2i+h1) n = \frac{h}{2} (2i + h - 1)
so 2i+h1 2i + h - 1 is odd and 2i+h1n 2i + h - 1 \mid n , we are done.

4. Conclusion:
From Claims 1 and 2, we have shown that n n is beautiful if and only if n n has an odd divisor greater than 1. Therefore, the numbers that cannot be written as the sum of consecutive natural numbers are those that do not have any odd divisors greater than 1. These numbers are the powers of 2.

Hence, the numbers that cannot be written as the sum of consecutive natural numbers are 2s 2^s with sN s \in \mathbb{N} , for example, 1,2,4,8, 1, 2, 4, 8, \ldots .

The final answer is 2s \boxed{ 2^s } with sN s \in \mathbb{N} .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.