jump to navigation

## IMO 2009 #1 July 18, 2009

Posted by Martin Camacho in Problem-solving, Uncategorized.
Tags: ,
trackback

The 2009 IMO was a few days ago – in this post I tackle what I think is one of the easier IMO problems, IMO 2009 #1.

The question is as follows:

Let ${n}$ be a positive integer and let ${a_1,a_2,a_3,\cdots,a_k}$ (${k\ge 2}$) be distinct integers in the set ${1,2,\cdots,n}$ such that ${n}$ divides ${a_i(a_{i+1}-1)}$ for ${i=1,2,\cdots,k-1}$. Prove that ${n}$ does not divide ${a_k(a_1-1)}$.

My solution

For all ${i}$, ${1\le i \le k-1}$, ${a_i(a_{i+1}-1)\equiv 0\pmod n}$. Then ${a_ia_{i+1}\equiv a_i \Rightarrow a_1\equiv a_1a_2\cdots a_k\equiv }$

${a_1a_2\cdots a_{k-2}a_{k-1}a_{k}\equiv a_1a_2\cdots a_{k-2}a_k\equiv a_1a_2a_k\equiv a_1a_k \pmod n}$.

Now, suppose ${n|a_k(a_1-1)}$. Then ${a_k\equiv a_ka_1\pmod n \rightarrow a_k\equiv a_1 \pmod n}$.

But ${a_1\neq a_k}$ and ${1\le a_1,a_k\le n}$, so ${a_1=a_k}$, a contradiction. ${\square}$

Very cool problem.

Advertisements

## Comments»

1. 2009年国际数学奥林匹克竞赛问题一 « Liu Xiaochuan’s Weblog - July 24, 2009

[…] 证法二：Martin Camacho提到另一个方法，如下： […]

2. Manjil P. Saikia - October 9, 2009

My solution is almost similar. There can be other variations to this problem too.