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.

About these ads

Comments»

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

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

Reply
2. Manjil P. Saikia - October 9, 2009

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

Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out / Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out / Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: