A tough nut from Norway: RMO training !

Problem:

The integers 1, 2, 3, 4, and 5 are written on a blackboard. It is allowed to wipe out two integers a and b and replace them with a+b and ab. Is it possible, by repeating this procedure, to reach a situation, where three of the five integers on the blackboard are 2009?

Solution:

The answer is NO.

First notice that in each move, two integers will be replaced with two greater integers (except in the case where the number 1 is wiped out). Also note that from the start there are three odd integers. If one chooses to replace two odd integers on the blackboard, the number of odd integers on the blackboard decreases. If one chooses to replace two integers, which are not both odd, the number of odd integers on the blackboard is unchanged. To end up in a situation, where three of the integers on the blackboard are 2009, then it is not allowed in any move to replace two odd integers. Hence, the number 2009 can only be obtained as a sum of a+b.

In the first move that gives 2009 on the blackboard, two integers a and b are chosen such that a+b=2009 and either ab>2009 or ab=2008. In the case, ab=2008, one of the two chosen numbers is one; and hence, 1 will no longer appear on the blackboard. In either case, the two integers a+b=2009 and ab that appear in the creation of the first 2009 cannot be used anymore to create new instances of 2009. The second 2009 can only be obtained by choosing c and d such that c+d=2009 and either cd>2009 or cd=2008, and just as before; the numbers c+d=2009 and cd cannot be used in obtaining the last 2009. So, after forming two instances of 2009, there are four integers on the blackboard that have become useless for obtaining the third instance. Hence, the last integer 2009 cannot be obtained.

Wow!!

Ref: Nordic Mathematical Contest, 1987-2009.

Nalin Pithwa.

Leave a Reply

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

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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s