International Mathematical Olympiad '59, First Day

The goal of this set of notes is to improve our problem solving and proof writing skills. You are encouraged to submit a solution to any of these problems, and join in the discussion in #imo-discussion at Saturday 10/26/2015 at 10pm IST, 930am PDT. For more details, see IMO Problems Discussion Group.

These are the problems from the first ever International Mathematical Olympiad. They are pretty easy and I ask every one to try and solve them! Remember that the contestants were given Four and a Half Hours, and are required to prove these statements completely. So here Goes:

Q1. For every integer $n$ , prove that the fraction $\dfrac{21n+4} {14n+3}$ cannot be reduced any further.(POL)

Q2. For which real numbers $x$ do the following equations hold: $(a) \sqrt{x+\sqrt{2x-1}}+ \sqrt{x-\sqrt{2x-1}}=√2, \\\ (b) \sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}}=1, \\\ (c) \sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}} =2.$

(ROM)

Q3. Let $x$ be an angle and let the real numbers $a, b, c, \cos x$ satisfy the following equation: $a\cos^2 {x}+ b \cos {x} + c =0.$ Write the analogous quadratic equation for $a, b, c, \cos {2x}$ . Compare the given and the obtained equality for $a = 4,b = 2,c = -1$ . (HUN)

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Q1. Let g.c.d( $a,b$ ) be represented by ( $a,b$ ).

( $21n+4,14n+3$ ) $=$ ( $7n+1,14n+3$ ) $=$ ( $7n+1, 7n+2$ ) $=$ ( $7n+1,1$ ) $=$ $1$

Therefore, it can't it reduced for any integer $n$ .

Surya Prakash - 5 years, 8 months ago

This is absolutely correct! From a collary of the Euclidean Algorithm we know that $(a,b)=(b,a-b)$ and this makes the problem trivial!

Sualeh Asif - 5 years, 8 months ago

Nice solution. For completeness, you should explain why $(a,b) = (a-b, b)$ , and state that's the reason why we have equality throughout.

At the IMO, this solution is worth 7-.

Calvin Lin Staff - 5 years, 8 months ago

Same approach!

Vinayak Verma - 5 years, 7 months ago

Same solution

Anik Mandal - 5 years, 8 months ago

Simple standard solution.

Mehul Arora - 5 years, 8 months ago

I'll give my solution to Q3 (which is probably the long way around)

Note that $\cos 2x = 2 \cos^2 x - 1$ . Let $\cos x = y$ and $\cos 2x = z$ .

We have

$y = \dfrac {-b \pm \sqrt{b^2 - 4ac}}{2a}$

$y^2 = \dfrac{2b^2-4ac \pm 2b\sqrt{b^2 - 4ac}}{4a^2}$

$2y^2 = \dfrac{b^2-2ac \pm b\sqrt{b^2 - 4ac}}{a^2}$

$2y^2 - 1 = \dfrac{b^2-a^2-2ac \pm b\sqrt{b^2-4ac}}{a^2}$

$z = \dfrac{b^2-a^2-2ac \pm b\sqrt{b^2-4ac}}{a^2}$

Now, we will reverse engineer completing the square (which is used to get the quadratic equation. I just reversed it)

$\left (z + \dfrac {2ac+a^2-b^2}{a^2} \right )^2 = \dfrac {b^4 - 4ab^2 c}{a^4}$

$z^2 + \dfrac {4ac + 2a^2 - 2b^2}{a^2} z + \dfrac {4a^2c^2+a^4 + b^4+4a^3c-4ab^2c-2a^2b^2}{a^4} = \dfrac {b^4 - 4ab^2 c}{a^4}$

$z^2 + \dfrac {4ac + 2a^2 - 2b^2}{a^2} z + \dfrac {4a^2c^2+a^4+4a^3c-2a^2b^2}{a^4} = 0$

$a^2 z^2 + (2a^2-2b^2+4ac)z + (a+2c)^2-2b^2=0$

$a^2 \cos^2 2x + (2a^2-2b^2+4ac) \cos 2x + (a+2c)^2-2b^2=0$

Therefore, the analogous equation is

Comparing for $a=4, b=2, c=-1$ , we have

$4 \cos^2 x + 2 \cos x - 1 = 0$

$4 \cos^2 2x + 2 \cos 2x - 1 = 0$

Clearly, both equations have the same coefficients. The value of $x$ in this case are certain multiples of $\dfrac {\pi}{5}$ .

I hope that's what I had to do when I had to compare.

Edit: This solution is only valid as long as $a \neq 0$ because otherwise, we have division by 0. If $a$ does equal 0, we have

$by+c=0$

$y= \dfrac{-c}{b}$

$y^2=\dfrac{c^2}{b^2}$

$2y^2=\dfrac{2c^2}{b^2}$

$2y^2-1=\dfrac{2c^2-b^2}{b^2}$

$z=\dfrac{2c^2-b^2}{b^2}$

$b^2 z = 2c^2-b^2$

$b^2 z + b^2 - 2c^2 = 0$

$b^2 \cos 2x + b^2 - 2c^2 = 0$

Sharky Kesa - 5 years, 8 months ago

Good approach, though you should justify some of the steps. For example, what happens in the case that $a = 0$ ? Then your solution is no longer valid.

At the IMO, your solution would be worth a 7-.

Another thing to note is that the coefficients of both the equations are proportional. That is that the coefficients of the L.H.S of the $\cos{2x}$ quadratic are $4\times$ that of the original equation.

This ends our questions for the First (ever) day of the IMO! Great work @Sharky Kesa ,@Surya Prakash @Chew-Seong Cheong and all others!

Q2. I will just write the solution for the first one. Try the remaining on your own.

Clearly, the root is satisfied iff $x \geq \dfrac{1}{2}$ . Squaring on both sides gives $2x +2|x-1| = 2$ .

So, $x+ |x-1| = 1$ .

If $x > 1$ , then $2x - 1 = 1$ which gives $x=1$ which is false since we assumed that $x>1$ .

If $x \leq 1$ , then we get $1=1$ which is true. So, all reals less than or equal to $1$ satisfied the above equation. But $x \geq \dfrac{1}{2}$ . So, all reals $x \in \Big[ \dfrac{1}{2}, 1 \Big]$ satisfy this equation.

At the IMO, avoid words like "Clearly" and "Obviously". You have to explain what you mean by "Clearly, the root is satisfied iff $x \geq \frac{1}{2}$ .

Furthermore, when you square an equation, you introduce extraneous roots. So, any solution that you obtain still has to be verified that it is a solution to the original problem. So far, we can only conclude that "the solution is a subset of ....".

At the IMO, this solution would be worth 0+.

Got it Sir!! Thanks for suggestion.

It might seem like a silly question to some, but how do you jump from the original equation to $2x + 2|x - 1| = 2$

N Solomon - 5 years, 8 months ago

This is a perfect solution. All reals $\frac{1}{2} \leq x \leq 1$ satisfy the equation for the part one. It can be proved using the same method that no solutions exist for the second part. The main thing is to note that $x\geq \frac{1}{2}$ and then square to obtain expressions. The third one is just a follow up from this.

Yes. U r right.

Answer to Question 3:

$\color{#3D99F6}{a\cos^2{x} + b\cos{x} + c = 0 \quad \quad ...(1) }$ $\begin{aligned} \Rightarrow a\cos^2{x} & = - b\cos{x} - c \\ \frac{a}{2}(\cos{2x}+1) & = - b\cos{x} - c \\ a \cos{2x} & = -a - 2b\cos{x} - 2c \\ a^2 \cos^2{2x} & = a^2 + 4b^2\cos^2{x} + 4c^2 + 2(2ab \cos{x} + 4bc \cos{x} + 2ca) \\ & = \frac{4b^2}{2}(\cos{2x}+1) + 4(a+2c)b\cos{x} + a^2 + 4c^2+4ca \\ & = 2b^2\cos{2x} - 2(a+2c)(-a-2b\cos{x} -2c) - 2a^2 - 8c^2 - 8ca + a^2 + 2b^2 + 4c^2+4ca \\ & = 2b^2\cos{2x} - 2a(a+2c)\cos{2x} - a^2 + 2b^2 - 4c^2 - 4ca \end{aligned}$

The required equation is:

$\color{#3D99F6}{a^2 \cos^2{2x}+ (2a^2-2b^2+4ca)\cos{2x} + a^2 - 2b^2 + 4c^2 + 4ca = 0 \quad \quad ...(2)}$

For $a=4$ , $b=2$ and $c=-1$ ,

$\begin{cases} (1): & 4\cos^2{x} + 2\cos{x} - 1 = 0 \\ \\ (2): & 16\cos^2{2x} + 8\cos{2x} - 4 = 0 & \Rightarrow 4\cos^2{2x} + 2\cos{2x} - 1 = 0 \end{cases}$

$\begin{aligned} \text{From }(1): \quad \cos{x} & = \frac{-2\pm\sqrt{20}}{8} = \frac{-1\pm\sqrt{5}}{4} \\ \Rightarrow \cos{2x} & = 2\cos^2{x} - 1 \\ & = 2 \left( \frac{-1\pm\sqrt{5}}{4} \right)^2 - 1 \\ & = 2 \left( \frac{6 \color{#D61F06}{\mp} 2 \sqrt{5}}{16} \right) - 1 \\ & = \frac{3 \color{#D61F06}{\mp} \sqrt{5} - 4}{4} = \frac{-1 \color{#D61F06}{\mp} \sqrt{5}}{4} \end{aligned}$

Therefore, both $\cos{x}$ and $\cos{2x}$ satisfy the equation $4\cos^2{x} + 2\cos{x} - 1 = 0$ .

Actually, $\cos{72^\circ} = \frac{-1 + \sqrt{5}}{4}$ and $\cos{144^\circ} = \frac{-1 - \sqrt{5}}{4}$ .

Chew-Seong Cheong - 5 years, 8 months ago

Another great solution! Do note that the coefficients of $(1),(2)$ are proportional.

Another typo in the eleventh line. I think the equation in (2) is in $\cos {2x}$

Thanks. I have edited it.

In your third line, I think you mean $\frac{a}{2} ( \cos 2x + 1 )$ ?

Good solution. At the IMO, this would be worth 7-.

Yes, you are right. Edited it.

Solution for Q1:

Lemma - (1) : Let (a,b) denote the GCD of a and b. Then, (a,b) = (a-b,b).

Proof : Let (a,b) = d and (a-b,b) = e. Then, from the definition of GCD, we have (a,b) = d $\Rightarrow$ d|a and d|b $\Rightarrow$ d|(a-b) and d|b $\Rightarrow$ d|(a-b,b), i.e. d|e. Similarly, (a-b,b) = e $\Rightarrow$ e|(a-b) and e|b $\Rightarrow$ e|a and e|b $\Rightarrow$ e|(a,b), i.e. e|d. Hence, e|d and d|e implies |e| = |d|, thereby proving that |(a,b)| = |(a-b,b)|. But the greatest common divisor of any two integers is the largest positive integer that divides both of them, i.e. GCD range is the set of positive integers. Hence, we can say |(a,b)| = |(a-b,b)| $\Rightarrow \boxed{(a,b) = (a-b,b)}$ .

Now, from repeated use of Lemma-(1), we can write (21n+4, 14n+3) = (7n+1, 14n+3) = (7n+1, 7n+2) = (7n+1,1) = 1. Therefore, the fraction is irreducible for any integer n.

Venkata Karthik Bandaru - 5 years, 8 months ago

1) gcd{21n + 4, 14n + 3} = 1 so they cant be reduced

Dev Sharma - 5 years, 8 months ago

Sorry that's not what I meant. Just went out of track!

Hrithik Nambiar - 5 years, 8 months ago

Ya, this can be proved by Euclidean Algorithm.

Swapnil Das - 5 years, 8 months ago

At the IMO, this solution is a 0+, because you have not proven the statement.

Yes sir! Thanks' a lot.

Did it the same way .But , Let me ask you guys something - won't the numerator be even always if "n" is not equal to zero and the denominator would always be odd. So , obviously, it can not be further reduced.

No what guarantee do you have that say the numerator and denominator are divisible by 7.

I.e. The numerator is 14(yet even) and denominator 7(yet odd). The fraction can be reduced.

And This is to be proved for all primes!

@Sualeh Asif – exactly! sorry

@Sualeh Asif – by using the fact ax + by = 1

How did you declare gcd as 1 directly?

Aditya Chauhan - 5 years, 8 months ago

NO ! I USED THE METHOD AS THAT OF @Dev Sharma ! BUT THEN I HAD A SENSE OF DOING IT IN ANOTHER WAY! ANYWAYS MY BAD !

@Hrithik Nambiar – Avoid using upper case of letters. It is considered as rude on brilliant.

Nihar Mahajan - 5 years, 8 months ago

@Hrithik Nambiar – Please refrain from typing in all caps, as that is considered very rude on the internet. Thanks for your assistance!

@Calvin Lin – yes sir .

Q#2 $(a) \sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}}=1$ For the L.H.S to be real, $\sqrt{2x-1}$ must be greater then or equal to zero.So $\sqrt{2x-1}\geq 0\\2x-1\geq 0\\x\geq \frac {1}{2}$ ............................................................................................................................................................................................. $\begin{aligned}\sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}}=1\\ \text{Squaring both sides} 2x+2(\sqrt{x+\sqrt{2x-1}})(\sqrt{x-\sqrt{2x-1}})=1\\2x+2\sqrt{(x-1)^2}=1\\2x+2|x-1|=1\\x+|x-1|=\frac{1}{2}\end{aligned}$ $\text{CASE 1:} x>1\\ x+|x-1|=\frac{1}{2}\rightarrow x+x-1=\frac{1}{2}\\2x=\frac{1+2}{2}\\x=\frac{3}{4}$ Here $\frac{3}{4}<1$ ,but we assumed that (x>1/),a contradiction.Hence no solutions exist in this case. $\text{CASE 2:} x<1 \\x+|x-1|=\frac{1}{2}\rightarrow x-x+1=\frac{1}{2}\\1=\frac{1}{2} \text{A contradiction}$ Therefore no solutions can exust in this case. As no solutions can exist in either case,so the equation has no solutions.

Abdur Rehman Zahid - 5 years, 8 months ago

Great work, Though you made a mistake. In case 1 you assumed $x>1$ while the answer you got was less than 1. Contradiction. No solutions for the first or second case. Put in a complete solutoon doing the third part too.

@Sualeh Asif please open your slack :)

I just realized it now.sorry!!!! (Ican't edit my solution,can I?)

@Abdur Rehman Zahid – Sure you can! :D Just click the "EDIT" button at the bottom of your solution :)

@Mehul Arora – Thanks!!!!

Let $\dfrac{21n + 4}{ 14 n +3 }= k$

D H - 4 years, 9 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$