Saturday, May 14, 2011

Which Box Has Defective Balls

You have 10 boxes of balls (each ball weighing exactly10 gm) with one box with defective balls (each one of the defective balls weigh 9 gm). You are given an electronic weighing machine and only one chance at it. How will find out which box has the defective balls?



Firstly 10 boxes of ball kept in a queue and mark it as box1,box2,box3.........box10
then from 1st box we have to take 1 ball,from 2nd box 2 ball..........from 10th box we kept 10 balls. and weight the total ball....

so if total nos ball is :n(n+1)/2 (n= total nos of box that is 10)=55
if all the ball is 10 gm.then total weight will be=550gm.
suppose total weight is 546gm.
so the difference is(550-546=4gm).
then the d defective ball is in box no:4.
similarly we can try for all possible box difference gives us the box number which contains the defective balls

Whats The Age of 3 Childs .?????

A man walks into a bar, orders a drink, and starts chatting with the bartender. After a while, he learns that the bartender has three children. "How old are your children?" he asks. "Well," replies the bartender, "the product of their ages is 72." The man thinks for a moment and then says, "that's not enough information." "All right," continues the bartender, "if you go outside and look at the building number posted over the door to the bar, you'll see the sum of the ages." The man steps outside, and after a few moments he reenters and declares, "Still not enough!" The bartender smiles and says, "My youngest just loves strawberry ice cream." How old are the children?




Answer :

First, determine all the ways that three ages can multiply together to get 72:


72 1 1 (quite a feat for the bartender)
36 2 1
24 3 1
18 4 1
18 2 2
12 6 1
12 3 2
9 4 2
9 8 1
8 3 3
6 6 2
6 4 3
As the man says, that's not enough information; there are many possibilities. So the bartender tells him where to find the sum of the ages--the man now knows the sum even though we don't. Yet he still insists that there isn't enough info. This must mean that there are two permutations with the same sum; otherwise the man could have easily deduced the ages.

The only pair of permutations with the same sum are 8 3 3 and 6 6 2, which both add up to 14 (the bar's address). Now the bartender mentions his "youngest"--telling us that there is one child who is younger than the other two. This is impossible with 8 3 3--there are two 3 year olds. Therefore the ages of the children are 6, 6, and 2.

Question

A variant of the problem is for the sum of the ages to be 13 and the product of the ages to be the number posted over the door. In this case, it is the oldest that loves ice cream. Then how old are they?


In the sum-13 variant, the possibilities are:
11 1 1
10 2 1
9 3 1
9 2 2
8 4 1
8 3 2
7 5 1
7 4 2
7 3 3
6 6 1
6 5 2
6 4 3

The two that remain are 9 2 2 and 6 6 1 (both products equal 36). The final bit of info (oldest child) indicates that there is only one child with the highest age. This cancels out the 6 6 1 combination, leaving the childern with ages of 9, 2, and 2.

Chess Queen Puzzle

Imagine there are infinite number of Queens (Chess Game Piece) with u. Find the minimum number of queens required so that every square grid on the chess board is under the attack of a queen. Arrange this minimum no. of Queens on a chess board.



to solve it we have to think all possible combination. because we have to find out the one can easily solve it if he has strong foundation of backtracking algorithm its the geeks way to solve . although it can also be solve by trying all possible combinatios thats the normal way

start by putting queen at all position where i=j e.g. 1,1, 2,2 3,3, & so on
so then we have 8 queens like It can also be keeping one at diagonal (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7)

can we do better ..??

as we know This problem has more than one solutions. I found one with 6 queens placed at (0,0), (1,7), (2,1), (3,4), (4,2), (6, 3) now if we rotate the chess board then we can get other solution so in this case we need 6 queen can we do still do better..?? think again



it requires much deep thinking then i was able to come up with two more solution that requires 5 queens & i think that are minimum number of queens we are looking for ...

1st (1,1) (3,4) (3,6) (4,2) (5,5)
2nd (0,0) (1,7) (2,4) (4,0), (7,6)

Queen Needed 5

Feel Free to Update & Optimize Th Solution

Wednesday, May 11, 2011

Find 3 Fastest Horses from set of 25 Horses

There are 25 horses and only five tracks in a race (i.e., you can race 5 horses at a time). There is no stop clock !! Assume that there are no ties.

1: What is the minimum number of races needed to determine the 3 fastest horses in order from fastest to slowest ?

We group the 25 horses in 5 groups each containing 5 horses.In each of first five races we will rank each five horsesA, B,C,D and E ( A : fastest and E: slowest) in the group.

1A 1B 1C 1D 1E
2A 2B 2C 2D 2E
3A 3B 3C 3D 3E
4A 4B 4C 4D 4E
5A 5B 5C 5D 5E


In the sixth race ( among the first of each group) we will get the fastest horse and rank these five horses 1A,2A,3A,4A & 5A (1A : fastest and 5A slowest)
Similarly .just select the fastest of the remaining horses from each row for the race.

Now we have got the fastest horse 1A and will also set nomenclature for each horses.
The fastest of the remaining horses in the row will take part.For e.g. the seventh race will be between 1B & 2A (no need to run 3A,4A & 5A)for determining
2nd fastest horse.

The 8th race will determine the third place and it will be between 1C and 2B ( in case 1B wins 7th race) or among 1B,2B & 3A ( in case 2A wins 7th race).

The 9th race will determine the 4th place and the 10th race will determine 5th place.

And moving on 25 th race will determine 20th place.The 26th race will tel the remaining 5 ranks.



Follow Up minimum number of races needed to find
1:....... to rank all of them from fastest to slowest ?
2:....... to find the top k fastest horses ?


* min number of races to rank all of them

sol:-

1. I can re-phrase this question to ask the min number of races to get 25 fastest horses.
2. You need 6 races to get the fastest ranked (steps 1 thru 3).
3. After that every race will give you the next fastest.
4. We can continue this till we have got the 20 fastest horses. After that we just need 1 race to rank the remaining 5.

total = 6 (to get rank 1) + 19 (to get rank 2-20) + 1 (to get rank 21-25) = 26

* min number of races to get k fastest horse

sol:-

5 + k (for k <= 20 )
26 (otherwise)