PDA

View Full Version : Here Comes Another Brain Teaser



dkpbus
10-03-2002, 08:04 AM
Hi All

Can you guys work on this....

There are 20 packs of cigarettes. Each pack has 20 cigarettes. Each pack has cigarettes weighing 2gms each except one pack. Cigarettes in this only pack weigh 1gm each. All 20 packs are randomly mixed. You have a balance and you CAN balance ONLY ONE TIME. How will you find which pack has 1gm cigarretes?

DKP

dkpbus
10-04-2002, 04:47 AM
come on Guys this is pure mathematics....

Erin
10-04-2002, 04:57 AM
The way I heard this one was that it was a Microsoft interview question...

dkpbus
10-04-2002, 05:04 AM
Originally posted by ErinBilly

The way I heard this one was that it was a Microsoft interview question...


Yes you're right. In fact, when I heard this puzzle for the first time in my college, while preparing for campus interviews, I spent almost 3-4 days to solve this, but could not solve. And solution is amazing.

DKP

raghuveer_v
10-04-2002, 04:00 PM
Originally posted by dkpbus

Hi All

Can you guys work on this....

There are 20 packs of cigarettes. Each pack has 20 cigarettes. Each pack has cigarettes weighing 2gms each except one pack. Cigarettes in this only pack weigh 1gm each. All 20 packs are randomly mixed. You have a balance and you CAN balance ONLY ONE TIME. How will you find which pack has 1gm cigarretes?

DKP




THE PROBLEM:

There are 20 packs of cigarettes. Each pack has 20 cigarettes. Each pack has cigarettes weighing 2gms each except one pack. Cigarettes in this only pack weigh 1gm each. All 20 packs are randomly mixed. You have a balance and you CAN balance ONLY ONE TIME. How will you find which pack has 1gm cigarretes?


I am not sure what exactly can be balanced ...
- whether we should only balance cigarettes/packs against each other
- or we can weigh a set of cigarettes/packs with standard weights to determine their weight

In the second case, i.e., if we can find out the weight of a set of cigarettes we choose, by balancing them against standard weights, here's my solution...



THE SOLUTION:

Let's call our cigarette packs : P1, P2, P3, ... P20.

We take as a set...

1 cigarette from P1 +
2 cigarettes from P2 +
3 cigarettes from P3 +
... so on ...
20 cigarettes from P20.

We then find out the weight (Say, W) of this set of cigarettes.

If all cigarettes were 2gm, the weight of the above chosen set would be ...

W = (1x2gm)+(2x2gm)+(3x2gm)+...+(20x2gm)
= (1+2+3+....+20)x2gm
= (20x21/2)x2gm
= (210)x2gm
= 420gm

However, one of the 20 packs contains only 1gm cigarettes.

If P1 contained 1gm cigarettes instead of 2gm cigarettes, we have W = (420-1)gm
If it's P2, we have W = (420-2)gm
If P3, W = (420-3)gm
.. so on ..
If P20, W = (420-20)gm

Thus if we weigh our set and find that it weighs 419gm, we can say that P1 is the pack that contained 1gm cigarettes.

If it's 418gm, P2 is the one.

.. so on ...

If it's 400gm, P20 is the one.



Hope that works!

Erin
10-04-2002, 05:58 PM
I've said it before, but I guess I'll say it again:

Man are you smart, Raghuveer!

I hope you use all your abilities to improve the world, not make it a worse place. Seriously.

raghuveer_v
10-05-2002, 02:52 AM
Thank you, Erin!

Let's wait for DKP's post,.... or any better solution.

And I do take your words seriously.

cinderellahn
10-05-2002, 04:44 AM
Hi all,

I think Raghuveer's solution is the best one. I heard about this problem when I was in the 5th grade. Exactly most Vietnamese students who learn in Special Mathematics Classes know this problem. It is a beautiful one.

In the 5th grade, we learn about arithmetic. There are many other "beautiful" problems in arithmetic, those anyone can understand (even the small children in primary schools) but their ideas attract many people from different ages. I want to introduce 2 more problems which I like very much, besides this great one.

1. Given a matrix n x n. Write the integer numbers from 1 to n x n into the matrix, using each one only once. The matrix you get in the end must have an equal sum in each column, each row and each criss-cross. (Tell me if you don't understand the problem, it is difficult for me to tell it in English)

2. Find the 6-digit number abcdef which:
2 x abcdef, 3 x abcdef, 4 x abcdef, 5 x abcdef, 6 x abcdef all have the product which are 6-digit numbers formed from a, b, c, d, e, f (for example: fabcde...)

Hope you enjoy them.



*************************
My 100th post
*************************

Erin
10-05-2002, 01:41 PM
Originally posted by cinderellahn



*************************
My 100th post
*************************

Congrats on your 100th post, Cinderella (do you have a real name, by the way??). It's been nice having you here. :)

Vaya
10-05-2002, 01:53 PM
The 2nd aswer is 142857... Just don't ask why and how...

Renata

dkpbus
10-07-2002, 03:56 AM
Hi Raghuveer

Great Man!!!! You cracked the problem. Thats amazing !
Yes guys the solution offered by Raghuveer is right. I support Erin for saying Raghuveer SMART and Intelligent (From Me) too.

Keep it up Raghuveer

DKP

raghuveer_v
10-07-2002, 05:55 AM
Originally posted by cinderellahn

Hi all,

I think Raghuveer's solution is the best one. I heard about this problem when I was in the 5th grade. Exactly most Vietnamese students who learn in Special Mathematics Classes know this problem. It is a beautiful one.

In the 5th grade, we learn about arithmetic. There are many other "beautiful" problems in arithmetic, those anyone can understand (even the small children in primary schools) but their ideas attract many people from different ages. I want to introduce 2 more problems which I like very much, besides this great one.

1. Given a matrix n x n. Write the integer numbers from 1 to n x n into the matrix, using each one only once. The matrix you get in the end must have an equal sum in each column, each row and each criss-cross. (Tell me if you don't understand the problem, it is difficult for me to tell it in English)

2. Find the 6-digit number abcdef which:
2 x abcdef, 3 x abcdef, 4 x abcdef, 5 x abcdef, 6 x abcdef all have the product which are 6-digit numbers formed from a, b, c, d, e, f (for example: fabcde...)

Hope you enjoy them.



*************************
My 100th post
*************************



Hi,

I remember that such an nxn matrix is also known as a magic square. One of my friends told me there was an algorithm to write such a matrix. It was a long time back, and I didn't even learn it at that time. Let's see ... (Alternatively, we can use a software called MATLAB which has an in-built function to generate magic squares. say, x = magic(n); and that's it. :D )

I will try the second one soon... :)

raghuveer_v
10-07-2002, 04:20 PM
PROBLEM #1:

Given a matrix n x n. Write the integer numbers from 1 to n x n into the matrix, using each one only once. The matrix you get in the end must have an equal sum in each column, each row and each criss-cross.

SOLUTION (partial):

Algorithm obtained by observing standard magic squares (generated using MATLAB's magic() function.) ...

Case n = odd

say we have nxn matrix M with M(r,c) representing element in row=r, column=c of M.

start by putting M(1,(c+1)/2) = 1
(i.e., the middle element of the first row.)

Then, follow the following algorithm ...

after writing any number 'p' in M(r,c)...
- write 'p+1' in M(r-1,c+1) if it is empty
- if it is not empty, write 'p+1' in M(r+1,c) and continue

... until all elements are over (ends at M(n,(c+1)/2)

Note: if we say M(r,c) and r exceeds n, we take r = r%n i.e., reminder of the division r/n . similarly with c. (or simply put, we wrap around the columns and rows if they exceed their maximum limits of n.) similarly with the minimum limits also.

Make sense?

Examples...

3x3 magic square :

8 1 6
3 5 7
4 9 2

5X5 magic square :

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9



I am yet to figure out the algorithm for the case n=even.
looks a bit more involved than the above case....