IMO 2010 Problem 5

There are six boxes; we label them B1, B2, B3, B4, B5, B6. At the beginning, each box contains one coin.

We are allowed to perform any one of these nine operations:

  • Operation X1: If B1 is not empty, take one coin out of B1 and add two coins to B2.
  • Operation X2: If B2 is not empty, take one coin out of B2 and add two coins to B3.
  • Operation X3: If B3 is not empty, take one coin out of B3 and add two coins to B4.
  • Operation X4: If B4 is not empty, take one coin out of B4 and add two coins to B5.
  • Operation X5: If B5 is not empty, take one coin out of B5 and add two coins to B6.
  • Operation Y1: If B1 is not empty, take one coin out of B1, and swap the contents of B2 and B3.
  • Operation Y2: If B2 is not empty, take one coin out of B2, and swap the contents of B3 and B4.
  • Operation Y3: If B3 is not empty, take one coin out of B3, and swap the contents of B4 and B5.
  • Operation Y4: If B4 is not empty, take one coin out of B4, and swap the contents of B5 and B6.

Call these nine operations legal. Note that, in operation Y1, we may swap the contents of boxes B2 and B3 even if they are empty (similar comment applies to operations Y2, Y3 and Y4).

Problem: Perform a series of legal operations, so that in the end, boxes B1, B2, B3, B4, B5 are empty, and box B6 contains 100 coins.

___________________________

Note: I’ve modified the problem significantly to remove all mathematical content from the problem statement and solution. In this version, the problem reduces to a simple puzzle which anyone with a high school math background can understand.

Try it!

16 Responses to IMO 2010 Problem 5

  1. samah says:

    Dammit bal. Takde2, aku nak tido malam ni. Sori cincai sikit.

    X1 or Y1 can only be used once. Hmm.

    Smells like binary.

    We start with = 111111, kalau belasah X operations on everything, we will get

    X1 = puts 32 in B6
    X2 = puts 16 in B6
    ..
    X5 = puts 2 in B6

    So by X operations along, we will only get = 63.

    Kene main dengan Y operation such that we can ‘increase’ the value of our existing bits.

    Bab ni aku malas hahahahaha…. Actually just kene figure out what is the ‘value’ of Y operations… malas2… dah dapat dah tadi through brute force tapi tak record steps (ntah2 salah). anyway the wiser solution is to get the meaning of the operations and combine them wisely.

    Pastu bila dah dapat enough bits to amount to more than 100 in base 10, simply use X operations to put the coins in B6. Kalau terlebih, guna taktik swap between empty boxes untuk hilangkan coins.

    • suhaimiramly says:

      That’s the right ideas: use Y operations to increase coins in the middle boxes, and swap empty boxes to bring down the number of coins to the amount we want.

      This version is easy enough that you don’t need a precise bound to reach the final state. Almost any adhoc algorithms work. However, it is a good idea to find a general and systematic solution which can still be used if we e.g. change 100 to 1,000 or 1,000,000.

      A helpful hint: If we have three consecutive boxes containing (A,0,0) coins, then we can apply legal operations to get (0,2^A,0) coins without touching the other boxes.

      The actual IMO problem is very difficult; the last box must end up with 2010^(2010^2010) coins, a very large number. To solve this version, we have to find the most efficient algorithm to increase the coins (otherwise we will end up short) using some clever intermediate steps. Then we apply the trick of swapping empty boxes to bring down the number of coins to our exact level.

      • samah says:

        2010^(2010^2010)?

        man.. nothing but respect…

      • suhaimiramly says:

        Even that is quite “small”. The IMO problem committee pointed out that it is possible to get N coins in the last box, where

        N = 2^(2^(2^(2^(2…))))

        where the number of twos in the “tower of power” N is M, where

        M = 2^(2^(2^(2^(2…)))) ,

        where the number of twos in the “tower of power” M is 16384.

        *head explodes*

  2. Ijan says:

    saya lebih berminat kat ‘thinking cat’ ;P

  3. Yus Rezal says:

    *KABOOMM!!!* – head explode.

  4. Amirul Fitri says:

    is the origanal problem harder?

  5. Amirul Fitri says:

    btw if it asks for the 50th prime,(primes are arranged in increasing order), how is it solved? i dont actually get what the question prompts for/

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

%d bloggers like this: