Solution to Puzzle #95: How Many Ways to Play the Tabla

Posted on March 15, 2015 by Alok Goyal

Thanks for a record breaking viewership this week…this is the maximum traffic I have had on the site ever since I started the puzzle! Many people sent the correct answer (which is 34 ways to do it). Some people gave a very elegant answer to the puzzle which include Amit Jain, Mohit Khare, Pratik Poddar and Vijay Venkat Raghavan – hats off to all of you! This puzzle was the origination of Fibonacci Series (en.wikipedia.org/wiki/Fibonacci_number) which is named after Fibonacci and documented this in 1202. However, this was originally found with music as its origin in 200 BC, but more formally articulated by Hemachandra in 1150 A.D. A link to the video from famous mathematician Manjul Bhargava, who in his interview with NDTV talked about it. https://www.youtube.com/watch?v=oCpdAPt7UOs Before describing the method with Fibonacci series, I want to outline the method that most people used. The correct answers here included Anirudh Baddepudi, Karan Sharma, Amit Mittal and Pallav Pandey. The logic to arrive at the answer (Using Mohit Khare’s answer): Possible combinations of A and B are in {8,0} , {6,1} , {4,2}, {2,3} and {0,4}.  Corresponding to each , following are the number of ways to arrange As and Bs: {8,0} := 1 [ chose 8 from 8 ] {6,1} := 7 [ chose 6 from 7 ] {4,2} := 15 [ chose 4 from 6 ] {2,3} := 10 [ chose 2 from 5 ] {0,4} := 1 [ chose 0 from 4 ] So total is : 34 The more elegant way to solve this is using Fibonacci Series. Lets call F(8) the number of ways to solve the problem. If we think about it, F(8) can be derived from the sum of following: – All the ways in which F(6) can be done with a B appended at the end of it, and – All the ways in which F(7) can be done with an A appended at the end of it. Therefore F(8) = F(7) + F(6), which is essentially the Fibonacci series. We know that F(1) = 1 (only one A) and F(2) = 2 (either two As or 1 B). The series will look as follows: 1, 2, 3, 5, 8, 13, 21, 34…. Hope you all enjoyed the puzzle.

Posted in Solution | Tagged , , | Leave a comment

Puzzle #95: How Many Ways to Play the Tabla

Posted on March 8, 2015 by Alok Goyal

Heard this awesome puzzle yesterday while watching a video of Manjul Bhargava with my children (thanks to my wife Pooja to introduce me to this one). For those who do not know, Manjul Bhargava is a Princeton Professor who got the Field Medal in August last year, given for Mathematics once in 4 years. In his interview with NDTV, he asked this puzzle to children.

Assume that there are only two possible ways to hit the tabla – lets call them A and B. A requires one time unit and B requires 2 time units. You have a total of 8 time units and need to use A and B to fill these 8 time units. How many different ways are there.

As always, please send your answers directly to me at alokgoyal_2001@yahoo.com. If you like the puzzle, please share it with others. If you have interesting puzzles to share, please send them to me at my e-mail given above.

 

Happy playing!

Posted in Puzzles | Tagged , | 2 Comments

Solution to Puzzle #94: Two Eggs and a Building

Posted on March 8, 2015 by Alok Goyal

Again an overwhelming response to the puzzle, that I thought was a difficult one. But some of the die hards sent an answer immediately. Only two people gave a fully correct answer – Suman Saraf, whose 10 year old also could do this one with some hints and Karan Sharma (my nephew from Jaipur) – amazing & very well done!

The correct answer is that there is a way to do this in a maximum of 14 trials.

Here is the solution:

At any point, if you are left with only 1 egg, the only strategy that will give you the answer is to start at the lowest unknown floor and work your way up one-by-one until the egg breaks or until you reach the top floor.

With 2 eggs, you can improve your strategy by starting somewhere between the lowest unknown floor and the highest unknown floor. If the egg breaks, you can eliminate all upper floors, but then you have to revert to the 1 egg strategy. If the egg doesn’t break, you can eliminate that floor plus all floors below it, and then choose another starting point among the remaining floors and repeat.

Many people tried variations, i.e. you do at try 50th floor first (binary method) and then if it breaks, then you try from 1st onwards until 50 or start 51st onwards if it does not break.

Some others tried alternate floor strategy, i.e. go 2, 4, 6, …and wherever it breaks try n-1.

One of the more intuitive and innovative solutions is to start with sqrt (n), n in this case being 100, so start with 10, 20, 30, ….and wherever it breaks, start with the previous one+1 onwards. This will require a maximum of 19 trials, or ~2 sqrt(n).

However, the best way to do this is the following (taken directly from Gurmeet’s site) – With 100 floors, you can find the correct floor in 14 drops or less by starting at floor 14. If the egg breaks, you then go to floor 1, work your way up, and will find the correct floor with at most 14 drops. If the egg doesn’t break, then move up 13 floors to 27. Again, if it breaks, you work your way up from 15 and will find the correct floor in at most 14 drops. If it didn’t, you move up 12 floors, then 11, etc. Using this method, you can see that you will always find the correct floor in 14 or fewer drops.

If you attempt to find the floor with 13 or fewer drops, you can see that you must start at the 13th floor or lower, and after the first drop you can move at most 12 floors, then 11, etc. You will not reach the top of the building within 13 drops, so you cannot guarantee you will find the correct floor.

Therefore, any strategy will in worst case require at least 14 drops.

Hope you all enjoyed the puzzle!

Posted in Solution | Tagged , | Leave a comment

Puzzle #94: Two Eggs and a Building

Posted on March 1, 2015 by Alok Goyal

This is another beauty of a puzzle from Gurmeet’s puzzle collection at gurmeet.net/puzzles/, thanks Gurmeet!

With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped?

As a hint, think of the same problem with only one egg – in this situation, the only option you have is to linearly try dropping the egg from each floor beginning from Floor 1 upwards until it breaks. What can you do differently if there are two eggs?

As always, please send your answers directly to me at alokgoyal_2001@yahoo.com. If you like the puzzle, please share it with others. If you have interesting puzzles to share, please send them to me at my e-mail given above.

Happy egging!

Posted in Puzzles | Tagged , | Leave a comment

Solution to Puzzle #93: Slice a Pizza Within a Cricket Team

Posted on March 1, 2015 by Alok Goyal

I got a lot of correct responses for this puzzle. My real intent was to see how children/ other people can apply a concept learnt earlier to new problems. Many people sent me correct answers that include Anupam Jain, Abhinav Jain, Suman Saraf, Anubhav Garg and Girish Tutakne.

In Puzzle #74 (https://alokgoyal1971.com/2014/09/21/solution-to-puzzle-74-overlapping-clock-hands/) we learnt a concept that can be applied to this puzzle. Essentially, we learnt that in a 12 hour period, the clocks overlap exactly 11 times (and not 12 times). All these occurrences happen at equal intervals of about 1 hour 5 minutes 57 seconds. All one needs to do therefore is to move the hands of the clock forward until they overlap, keep the watch at the center of the pizzle and cut in the direction of the overlapping hands.

Hope you all enjoyed the puzzle!

Posted in Solution | Tagged , , | Leave a comment

Puzzle #93: Slice a Pizza Within a Cricket Team

Posted on February 21, 2015 by Alok Goyal

Here is a world cup cricket puzzle, the text modified from an original one from http://www.mindcipher.com

In Australia, the Indian cricket team was not able to get anything to eat, and were finally able to get one large circular vegetarian pizza. There are 11 players who need to divide this equally within themselves. They only have a wrist watch and a simple knife. How can they divide it equally.

As always, please send your answers directly to me at alokgoyal_2001@yahoo.com. If you like the puzzle, please share it with others. If you have interesting puzzles to share, please send them to me at my e-mail given above.

Happy pizza!

Posted in Puzzles | Tagged , , | Leave a comment

Solution to Puzzle #92: Connecting the Four Corners of the Square

Posted on February 21, 2015 by Alok Goyal

Very good response to the puzzle, and lot of people sent me answers. The most common answer was that we should connect the two diagonals, which 2*sqrt(2) = 2.82 km. However, as it so happens, there is an answer which can do it in a shorter way than the diagonals. Abhinav Jain was the first one to send the correct answer. Other people to send the right answers included Vikas and Shray Vats combo and Suman Saraf. Very well done!

In the graphic below is the configuration that is the optimal way to do it. The answer does require knowledge of calculus, and therefore my apologies to younger folks who do not know calculus (I do not remember either!).

Puzzle 92 Solution

Puzzle 92 Solution

A good way to understand the answer can be through this video:

https://www.youtube.com/watch?v=dAyDi1aa40E

Also attaching a link to the more generic discussion on how to connect multiple points in the shortest way. The general class of problems is called the Stenier Trees.

http://en.wikipedia.org/wiki/Steiner_tree_problem

Hope you enjoyed the puzzle!

Posted in Solution | Tagged , | Leave a comment

Puzzle #92: Connecting the Four Corners of a Square

Posted on February 15, 2015 by Alok Goyal

This is a beautiful geometry puzzle that my friend, Alok Mittal, gave to children in his Mathematical Circles class yesterday.

There are four towns at the corners of a perfect square with a side of 1 km. Your task is to connect these towns through a railroad such that all the four towns are connected such that the length of the railroad is the smallest. As an example, if you connect all the four sides of the square, then the length of the railroad is 4 km. If you connect any three sides, all the four towns are still connected, and the length is 3 km. Can you do better?

As always, please send your answers directly to me at alokgoyal_2001@yahoo.com. If you like the puzzle, please share it with others. If you have interesting puzzles to share, please send them to me at my e-mail given above.

 

Happy railroading!

 

Posted in Puzzles | Tagged , | 4 Comments

Solution to Puzzle #91: Pebble Piles

Posted on February 15, 2015 by Alok Goyal

I again got a very high response this week – thanks again!

There was only one correct answer from Gyora – well done!

I am taking the liberty of reproducing the answer from Gurmeet, whose site is the source of this puzzle.

Since all three piles are odd, the first operation must be merger of two existing piles, resulting in an even-sized pile and an odd-sized pile. Let g denote the greatest common divisor of these two pile sizes. Since one pile is odd sized and the other pile is even sized, g must be odd. For odd g, no matter what sequence of operations is carried out (merger of two existing piles or division of an even pile into two equal piles), every pile size will continue to be a multiple of g. If g > 1, then we can never reach a configuration where all piles are size 1. Now, starting with {5, 49, 51}, three states are possible: {54, 51}, {5, 100} and {49, 56}. The GCD is 3, 5 and 7, respectively, in these three states. So we can never get 105 piles with 1 pebble each.

Hope you enjoyed the puzzle!

Posted in Solution | Tagged , | Leave a comment

Puzzle #91: Pebble Piles

Posted on February 8, 2015 by Alok Goyal

Another very nice puzzle I read on gurmeet.net/puzzles/, which as I have mentioned before, has a set of very nice mathematical puzzles.

You are given three piles with 5, 49 and 51 pebbles respectively. Two operations are allowed: (a) merge two piles together or (b) divide a pile with an even number of pebbles into two equal piles. Is there a sequence of operations that would result in 105 piles with one pebble each?

As always, please send your answers directly to me at alokgoyal_2001@yahoo.com. If you like the puzzle, please share it with others. If you have interesting puzzles to share, please send them to me at my e-mail given above.

Happy pebbling!

Posted in Puzzles | Tagged , , | 1 Comment