Solution to Puzzle #195: 1989!

I received many correct answers. These included  Suman Saraf, Vishal Poddar and Anand Sanghi. Thank you and well done!

This puzzle can be solved using the concept of “invariants” and parity.

Note that for any numbers a and b (a > b), numbers a and b get replaced by c. If a and b are both odd or both even, then c will be even. If one of them is odd and the other is even, then c will be odd. Essentially, in all the cases, if (a+b) is odd, c will be odd; If (a+b) is even, then c will be even. Therefore, parity of a+b is an invariant.

For the final set of numbers to be zero (which is even parity), the sum of all the numbers must be even, i.e. 1, 2, 3, …., 1989 must add up to an even number, which is not the case. Hence we can never achieve zeros as the final state.

Hope you all enjoyed the puzzle!

 

This entry was posted in Solution and tagged , , . Bookmark the permalink.

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