Archive

Posts Tagged ‘puzzles’

Puzzle on the road – how many combinations of food that I can have ?

July 7, 2011 Leave a comment

Let me start with the introduction of why I come up with this puzzle. I was invited to go to Trieste, Italy for a summer school in ICTP (click here for information of ICTP). I was lucky cause ICTP sponsored me so I did not have to pay for my living cost while I was there. Everyday, I ate in a cafeteria and I did not need to pay, cause ICTP gave me coupons that I can use to buy my lunch and my dinner. Cafeteria usually provides a set of first course meal, which is usually a pasta, a set of second course meal which is usually either beef, chicken, fish or vegetarian meal and a set of cooked vegetable.

One full meal that I can buy with a coupon,  consists of one of the first courses, one of the second courses and two of the cooked vegetables. In the first course meal, there are three choices of pasta and I am only allowed to take one of these. In the second course meal, there are also three choices  whether you want, say beef or fish or vegetarian meal and again I am allowed to take one of these. In the set of vegetable, there are three choices and I am allowed to take two of these three choices.

The question is how many combinations of meal that I can have.

To make it more interesting, let us assume that these following situations can occur.  I am sometimes so hungry so I take the full meal. But there is another time when I do not feel like eating so I do not eat. There is also another time when I want to eat but actually I am not that hungry so I only choose the first course and one of the cooked vegetable.

Anyway, it was a nice experience for me to be able to visit ICTP. I made a lot of friends for different countries there. I gained a lot of information that is really really useful for my research.

Here is a picture taken from my cell phone while I was there.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ps. I am not sure what is the correct answer. I have had already a number in my mind and let us confirm whether my guess is correct.

Advertisements
Categories: math puzzle Tags: , , , ,

Rope burning logic puzzle (just slightly more generalised)

May 2, 2011 6 comments

Many seem to know already the famous rope burning puzzle. When we google it, there will be infinitely many websites discussing this puzzle. However, I try to (kind of) generalise this puzzle a little bit and relate this puzzle to understand the difference between axioms, theorems, lemmas and corollaries that are often used in mathematics articles.

Here is the puzzle: There are two ropes and one lighter. Each rope has special properties.

  1. If we light one end of the rope, it will take exactly one hour to completely burn out.
  2. The density of the rope is not uniform, which means that burning half the rope would not take half an hour.
  3. Those two ropes are not identical, they aren’t the same density nor the same length nor the same width.

The question is how do we measure exactly 45 minutes using those two ropes.

We shall not discuss the answer here, instead I would like to give some logical consequences of those rules given in the properties of the rope. Those three properties are called axioms in mathematics article. They are not to be proven. We have to believed them, we have to accept it.

The first consequence is summarized in the following lemma (which is a small relatively easy consequence of the axioms).

Lemma 1
If we burn both ends of the rope, the rope will take 30 minutes to be completely burned

This lemma is very useful and it is used in solving the puzzle. It seems obvious but we can’t just take it for granted. Anyway, here is the proof.

Proof:
Let us prove this by a contradiction. Assume it would take x minutes by burning both ends of the rope until it is completely burned. Assume x \neq 30. Let us consider the case where x > 30.  At first (t=0) the rope is burned at both ends and after x minutes the rope would be gone. However, after 30 minutes there is still a segment of the rope that hasn’t been burned yet. See the figure below.

And now, let us consider if at first the rope is burned only at one end. It would take then 30 minutes until the segment AB is completely burned and it would take another 30 minutes to completely burn the segment CD. A contradiction, as it would need more than one hour to completely burned out the rope. The case where x < 30 can be proven similarly. QED

The next consequence is summarized in the theorem below. Theorem usually used to give a significant consequence of the three axioms given above. The theorem tells us that the solution of the puzzle exists.

Theorem 2
There is such a way to measure 45 minutes using only two ropes

Proof: Burn both ends of the first rope and burn one end of the second rope. According to lemma 1, it will take 30 minutes to completely burn out the first rope. The next step is to burn the other end of the second rope, therefore it will take 15 minutes to burn out the second rope if we apply lemma 1 once more to the second rope which has 30 minutes remaining rope.  QED.

The puzzle stops here, but our discussion does not. I would like to discuss if we have n ropes then how many minutes we can measure accurately. It turns out this problem is an immediate consequence of the last theorem.

Corollary 3
Suppose there are n ropes that satisfy the properties given in the beginning of this section, then there is such a way to measure exactly (60 - 60/2^n) minutes.

Proof:
This can be shown by inductively applying theorem 2 n times to n ropes.

The next results given below are dealing with only one rope. As given in the Lemma 1, we can measure exactly 30 minutes with using only one rope. However, there are various ways how we measure exactly 30 minutes. I won’t present the proofs here as it’s just fun to figure it all ourselves.

Lemma 4
Let us take the rope that has special properties given above. Cut the rope into two pieces and burn both ends of the first piece and then burn both ends of the second piece. It takes exactly 30 minutes until the rope is completely burned.

Lemma 5
Let’s take the rope that has special properties given above. Cut the rope into n pieces. Burn both ends of the first piece and then burn both ends of the second piece and so on until the last piece. It takes exactly 30 minutes until all the pieces of the rope are completely burned.

All the results above are resulted from burning the end of the rope. We are now asking ourselves what do we get if we burn the rope somewhere in the middle. Logically, the fire will spread in two directions. Depending on the density of the rope, one end of the rope will be caught by the fire first.

Lemma 6
Let’s take the rope that has special properties given above. Burn the rope at one point in the middle. Once one end of the rope is caught by the fire, burn the other end of the rope. It takes exactly 30 minutes until the rope is completely burned.

Of all results presented above, with using only one rope, we can measure exactly 30 and 60 minutes. But I would like to ask whether there is any other time that we can measure using only one rope.

Categories: math puzzle, Teachings Tags: