Pakistan IMO First Training Camp Test (Juniors)

Hello fellow Brilliantians!

As most of you know, the IMO is one of the biggest and most famous of all international Maths Olympiads. Following are the problems which appeared in the test at the end of the First Training Camp of Pakistan for the IMO 2017. Enjoy!:

$\textbf{Time: 4 hours}$

$\textbf{Number of Problems: 4}$

$\underline{\textbf{Problem 1}}$

Let $\Delta ABC$ be a triangle. Let $D,E,F$ be the feet of the perpendiculars from $A$ to $BC$ , $B$ to $CA$ and $C$ to $AB$ respectively. Let $P,Q,R$ and $S$ be the feet of the perpendiculars from $D$ to $AB,BE,CF$ and $CA$ respectively. Prove that $P,Q,R,S$ are collinear.

$\underline{\textbf{Problem 2}}$

Find the number of ordered pairs of sets $(A,B)$ such that $A\cup B=\{1,2,3,4,5,\cdots,n\}$ .Compute the answer for $n=5$ .

Note:

$(A,B)$ and $(C,D)$ are the same pair if $A=C$ and $B=D$ .

$A$ or $B$ can be an empty set (the pairs in which either one of $A,B$ is an empty set are to be counted as well)

$\underline{\textbf{Problem 3}}$

Let $a,b$ be two positive integers (not necessarily distinct) and let $p$ be a prime such that $lcm(a,a+p)=lcm(b,b+p)$ .Prove that $a=b$

Note:

$lcm(x,y)$ denotes the Least Common Multiple of the numbers $x$ and $y$ .

$\underline{\textbf{Problem 4}}$

Find all polynomials $P(x)$ with real coefficients such that the polynomial $Q(x)=(x+1)P(x-1)-(x-1)P(x)$ is constant.

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

Problem 4

I think my solution is correct. Please check if it is or not.

By observation, if $P(x)=c$ , then $Q(x)$ is also a constant function. If $P$ isn't constant, we can do as follows:

We can assume $P$ is monic since if it wasn't, we can divide out by the leading coefficient to still have a constant on the RHS. Let $P(x)=(x-r_1)(x-r_2) \ldots (x-r_n)$ . By Vieta's Formula,

$\begin{aligned} P(x) &= x^n - (r_1+r_2+\ldots+r_n) x^{n-1} + \ldots\\ \implies (x-1)P(x) &= x^{n+1} - (r_1+r_2+\ldots+r_n+1) x^n+\ldots\\ P(x-1) &= (x-r_1-1)(x-r_2-1)\ldots (x-r_n-1)\\ &=x^n - (r_1+r_2+\ldots + n) + \ldots\\ \implies (x+1) P(x-1) &= x^{n+1} - (r_1 + r_2 + \ldots + r_n + n - 1) x^n + \ldots \end{aligned}$

The coefficients for the $x^n$ in the expression for $(x+1)P(x)$ and $(x-1)P(x)$ must cancel each other out, so they must be equal. Thus, $r_1+r_2+\ldots+r_n+1 = r_1 + r_2 + \ldots + r_n + n - 1$ , so $n=2$ . Thus, $P(x)=x^2 - (r_1 + r_2) x + (r_1 r_2)$ . We now have (from above)

$\begin{aligned} (x-1) P(x) &= x^3 - (r_1 + r_2 + 1) x^2 + (r_1 + r_2 + r_1 r_2) x - r_1 r_2\\ P(x-1) &= x^2 - (r_1 + r_2 + 2) x + (r_1 r_2 + r_1 + r_2 + 1)\\ \implies (x+1) P(x-1) &= x^3 - (r_1 + r_2 + 1) x^2 + (r_1 r_2 - 1) x + (r_1 r_2 + r_1 + r_2 + 1) \end{aligned}$

The coefficient for $x$ in the expression for $(x+1)P(x)$ and $(x-1)P(x)$ must cancel each other out, so they must be equal. Thus, $r_1 + r_2 + r_1 r_2 = r_1 r_2 - 1$ , so $r_1 + r_2 = -1$ . Substituting back into $P(x)$ , we get $P(x)=x^2+x+k$ .

Checking, we have $P(x-1)=x^2-x+k$ , so $(x+1)P(x-1)=x^3+(k-1)x+k$ whereas $(x-1)P(x)=x^3 - (k-1)x - k$ . Subtracting these two, we get $Q(x)=2k$ , which is a constant. Therefore, our solution has been verified.

Therefore, all solutions that satisfy are $P(x)=c$ and $P(x)=A(x^2+x+k)$ , where $c$ , $A$ and $k$ are constants.

Sharky Kesa - 4 years, 9 months ago

My solution is exactly the same in the sense that it computes the coefficent of $x^n$ in $Q (x)$ but I used the binomial expansion after using a generic polynomial

$P (x)= \sum_{i=0}^n a_i x^i$

Expanding and comparing coefficents kills it

Sualeh Asif - 4 years, 9 months ago

Problem 3

I found this problem pretty trivial.

First, we will prove the $\text{gcd}(a, a+p)$ is either $1$ or $p$ . Let $k$ be the $\text{gcd}$ . We have

$\begin{aligned} k &\mid a\\ k &\mid a+p\\ \implies k &\mid a+p-a\\ \implies k &\mid p \end{aligned}$

Thus, the $\text{gcd}$ is either $1$ or $p$ . The same goes for $b$ and $b+p$ . We now have three cases:

Case 1: $\text{gcd} (a, a+p) = \text{gcd} (b, b+p) = 1$

Thus, their $\text{LCM}$ for each is equal to their product, so $a(a+p)=b(b+p)$ , which simplifies as $a^2 - b^2 = p(b-a)$ so $-(a+b)=p$ or $b-a=0$ . The former cannot be true since $a, b, p$ are all positive integers. Therefore, $b-a=0$ so $a=b$ .

Case 2: $\text{gcd} (a, a+p) = \text{gcd} (b, b+p) = p$

Thus, their $\text{LCM}$ for each is equal to their product divided by $p$ , so $\dfrac {a(a+p)}{p} = \dfrac {b(b+p)}{p}$ , which simplifies to the statement in the previous case. Thus, $a=b$ .

Case 3: $\text{gcd} (a, a+p) = 1$ , $\text{gcd} (b, b+p) = p$

Thus, each of their $\text{lcm}$ 's are $a(a+p)$ and $\dfrac {b(b+p)}{p}$ . Therefore,

$ap(a+p) = b(b+p)$ However, we know that $p \mid b$ and $p \mid b+p$ . Thus, $p^2 \mid b(b+p)$ , which means $p^2 \mid ap(a+p)$ , so $p \mid a(a+p)$ . However, this means either $p \mid a$ or $p \mid a+p$ , which is contradictory since either statement results in the other being also true, so their $\text{gcd}=p\neq 1$ . Thus, we have a contradiction, so this case cannot occur.

Therefore, over all the cases $a=b$ .

This is pretty trivial...

Exactly! But I wanted to case bash one of the problems.

Problem 2

This was a fairly simple problem.

Let $S$ be the set $\{1, 2, \ldots n\}$ . Let $A=\{a_1, \ldots, a_k\}$ with $k \leq n$ . Then, $B$ must contain at least $\{S/A\}$ as well as any element chosen from $A$ . This gives us $2^k$ choices since each element in $A$ may or may not be in $B$ . The number of ways to choose $k$ elements in $A$ for this to satisfy is $n \choose k$ . Thus, we must sum $n \choose k$ $\times 2^k$ from $k=0$ to $n$ .

$\begin{aligned} \displaystyle \sum_{k=0}^n \dbinom{n}{k} 2^k &= \displaystyle \sum_{k=0}^n \dbinom{n}{k} 2^k 1^{n-k}\\ &= (2+1)^n\\ &= 3^n \end{aligned}$

Thus, the general formula is $3^n$ , so if $n=5$ , $3^n=243$ .

Here is another solution I found:

Note that we have exactly 3 choices for each element, It goes in A,B or A and B. Since the choices for each element is exclusive we have that the number of ways is exactly $3^n$

Yep, that works as well, and is fairly quick. I saw my way first but this is an even quicker solution.

Problem 1 is from India's RMO 2006. Check the solution here

A Former Brilliant Member - 4 years, 9 months ago

The question isn't too hard. Angle chasing is all it takes.

I found at least 2 solutions for this:

A nicer approach, Consider the triangle $BFH$ . PQR is its simson line. Similarly QRS is collinear and we are done!

@Sualeh Asif – Yeah, I considered using Simson's line but I saw the angle chasing solution straight off.

@Sualeh Asif – I probably should have seen the Simson's line solution first, but I saw this instead.

Problem 1

This was fairly trivial, with a good diagram.

Firstly, since $DP$ is perpendicular to $AB$ and $CF$ was perpendicular to $AB$ , $DP$ and $CF$ are parallel. Similarly, $DS$ and $BE$ are parallel. Also, since $APDS$ and $BFEC$ are cyclic, we have $\angle APS = \angle ADS = \angle ECB = \angle EFA$ , Thus, $PS$ and $EF$ are parallel.

Note that $QPBD$ is cyclic, as well as $EFBC$ . Since they both share angle $ABC$ , both $P$ and $F$ are on $AB$ , and $D$ and $C$ are on $BC$ , it follows that $EF$ is parallel to $PQ$ . From the previous result, we get that $P,Q,S$ are collinear and parallel to $EF$ . Using a similar argument for $R$ , we get $P,Q,R,S$ are all collinear parallel to $EF$ .

Alternate solution (Kudos to Sualeh Asif)

This is the slick solution.

Since $HFBD$ is cyclic, where $H$ is the orthocentre, and $DP, DQ, DR$ are perpendiculars to $BF$ , $BH$ and $HF$ respectively, $PQR$ is the Simson Line of $HBF$ ( $D$ is the point on the circumcircle). Thus, $P,Q,R$ are collinear. Similarly, $Q,R,S$ are collinear so we are done.

sigma upper limit 2001 and lower limit k=1 (x+k)^2=y^2 has no integer solutions prove this was a problem at the imo training camp at Romania Please help me with the solution

RK Rohit - 4 years, 8 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}$