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.

This entry was posted on Friday, July 23rd, 2010 at 5:21 pm and is filed under Education, Math and Science. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

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.

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.

Participate in the World's Largest Math Competition. Contest Day: 26 March 2015!

BEAVER INFORMATICS COMPETITION

To be held for the first time in Malaysia. Tentative: August 2015. Stay tuned!

Order My Books

Click on image for more details

My Amazon.com Wishlist

Books as gifts

SUHAIMI RAMLY

I am an entrepreneur and educator. I am based in Kuala Lumpur, Malaysia.

Many people know me as Bal. This is the nickname that I am stuck with since high school.

My day job is running two companies I founded in 2007: Aidan Corporation (an IT company) and ArdentEdu (an educational consulting company). Both companies are based in KL.

Since 2006, I have been training the Malaysian national team to the International Mathematical Olympiad (IMO). Also, I volunteer as an MIT Educational Counselor. I conduct interviews for MIT applicants from Malaysia.

I founded the Malaysian Informatics and Programming Society (MIPS) in 2011, to disseminate algorithmic thinking and programming education among high school students. MIPS run the Malaysian Computing Competition, which is open to all Malaysian school students, and the Malaysian Computing Olympiad, which is an invitation-only programming contest.

Since 2012, I am the Director of Kangaroo Math Competition (KMC) Malaysia. KMC is the largest math competition in the world, with more than 6 million participants annually.

To know more about me, click on the About page.

Welcome to my website. Don't forget to leave comments.

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.

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.

2010^(2010^2010)?

man.. nothing but respect…

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*

saya lebih berminat kat ‘thinking cat’ ;P

meowww…

*KABOOMM!!!* – head explode.

is the origanal problem harder?

sorry cancel>

Find the 50th prime, if the primes are listed in increasing order.(exercise 1.4 book 1)

Find the 50th prime, if the primes are listed in increasing order.(exercise 1.4 book 1)..

Just list them down, that is just an exercise to familiarize readers with small primes.

oh< thank you

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/

I dont understand

Find the 50th prime, if the primes are listed in increasing order.(exercise 1.4 book 1);;;