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 and . Is it possible, by repeating this procedure, to reach a situation, where three of the five integers on the blackboard are 2009?
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 .
In the first move that gives 2009 on the blackboard, two integers a and b are chosen such that and either or . In the case, , one of the two chosen numbers is one; and hence, 1 will no longer appear on the blackboard. In either case, the two integers 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 and either or , and just as before; the numbers 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.
Ref: Nordic Mathematical Contest, 1987-2009.