Dropping Height For Egg Breakdown!

There is a building of 100 floors.

-If an egg drops from the Nth floor or above it will break.

-If it’s dropped from any floor below, it will not break.

You’re given 2 eggs.

Find N.

How many drops you need to make?

What strategy should you adopt to minimize the number egg drops it takes to find the solution?

'This' should be the strategy! 

Finding The Dropping Height For Egg Breakdown

What was the task?

Let's suppose, the we drop the egg from N the floor & it breaks then we need to do linear search till (N-1) th floor. For example, we dropped egg from 10 the floor & it breaks then we need to test 1-9 floors using 2nd egg to find the exact floor from which the egg breaks on dropping. So the best case would be 10 drops if the first egg breaks when dropped from 10 the floor.But that's only possible if the egg breaks on drop from 10th floor.

The worst case would be when egg doesn't break at 10,20,30,40,50,60,70,80,90 and breaks at 100th floor. Here, once again 91-99 need to be tested using other egg to find exact floor from which egg will break on drop.So in worst case, 19 drops would be needed.

Best way to minimize the number of drops required is to minimize the linear search (91-99 above  in worst case) that we need to do with the second egg after 1st egg breaks on drop from particular floor (100th floor in above worst case).

So after dropping egg from N th floor & if egg doesn't break then instead of going to next Nth floor, better to go N + (N-1) th floor. And now if the egg break here at N + (N-1) th floor then we need to do linear search from (N+1) th floor to N + (N-1) th floor instead of (N+1) th floor to (N + N) th floor. That's 1 less linear search than that needed if we go to the next N th floor if egg doesn't break on drop from Nth floor.

After dropping egg from N + (N-1) th floor, if it doesn't break then we should go the the N + (N-1) + (N-2) th floor.

Adding all instances of drops i.e. drop at Nth, drop at N + (N-1) th , drop at N + (N-1) + (N-2) & so on gives us

N + (N-1) + (N-2) + (N-3).......+1 = N(N+1)/2.

which shouldn't exceed 100 as there are only 100 floors & hence total number of drops must not be greater than 100.

So,

N(N+1)/2 >= 100

N^2 + N - 200 >= 0

This is

This is quadratic equation in form ax^2 + bx + c = 0 where x = [-b +- (b^2 -4ac)^0.5]/2a.

Solving above for N gives,

N = 13.651

Rounding value of N to 14 in the case.

So we should start with floor no. 14 followed by 27,39,50,60,69,77,84,90,95,99,100

In the worst case here total drops needed are only 14. 

For example, if the egg breaks when dropped from 14th floor then for second egg we need to test 1-13 floors to find the exact floor from which egg breaks on the drop. See table below.

Similarly, for example, egg breaks after drop from 50 floor (after testing 14,27,39), we need to test at 51-59 floors by dropping second egg to know the exact floor from where egg breaks on the drop.
 

Plan an Unbeatable Strategy

Two people play a game of NIM. There are 100 matches on a table, and the players take turns picking 1 to 5 sticks at a time. The person who takes the last stick wins the game. (Both players has to make sure that the winner would be picking only 1 stick at the end) 

Who has a winning strategy?

And what must be winning strategy in the person who takes the last stick looses?

This could be the winning strategy! 

Planned The Unbeatable Strategy!

What is the game?

The first person can plan an unbeatable winning strategy.

CASE 1 : The person picking last stick is winner.

All that he has to do is pick 4 sticks straightaway at the start leaving behind 96 stick. Then, he has to make sure that the count of remaining stick will be always divisible by 6 like 96, 90, 84, 78......6. 

So if the opponent takes away 2 sticks in his first turn, then first person has to take 6 - 2 = 4 sticks leaving behind 90 sticks there. That is if the opponent takes away X stick the first person need to pick 6 - X sticks.

Now, when there are 6 stick left, even if opponent takes away 5 sticks then 1 stick will be left for the first person.

And even if the opponent picks 4 sticks then first person will take 2 remaining sticks.

CASE 2 : The person picking last stick is looser. 

Now the first person need to take away 3 sticks in first turn leaving behind 97. Next, he has to make sure the count of remaining sticks reduced by 6 after each of his turn. That is, the count should be like 91,85,79,72......7.

So if the opponent takes away 4 sticks in his first turn, then first person has to take 6 - 4 = 2 sticks leaving behind 91 sticks there. That is if the opponent takes away X stick the first person need to pick 6 - X sticks.

When there are 7 sticks are left then even if the opponent takes away 5 sticks then first person can force him to pick the last stick by picking only 1 stick of remaining 2. 

And if the opponent takes away 4 sticks at this stage, the first person still can force him to pick last stick by picking 2 of remaining 3 sticks.

Conclusion : The first person always has a chance to plan a winning strategy.

Develop an Unbeatable Strategy!

Consider a two player coin game where each player gets turn one by one. There is a row of even number of coins, and a player on his/her turn can pick a coin from any of the two corners of the row. The player that collects coins with more value wins the game. 

Develop a strategy for the player making the first turn, such he/she never looses the game.

Note : The strategy to pick maximum of two corners may not work. In the following example, first player looses the game when he/she uses strategy to pick maximum of two corners.

============================================================

Example :

  18 20 15 30 10 14

First Player picks 18, now row of coins is
  20 15 30 10 14

Second player picks 20, now row of coins is
  15 30 10 14

First Player picks 15, now row of coins is
  30 10 14

Second player picks 30, now row of coins is
  10 14

First Player picks 14, now row of coins is
  10 

Second player picks 10, game over.

The total value collected by second player is more (20 +
30 + 10) compared to first player (18 + 15 + 14).
So the second player wins.
===================================================================
 
This is the unbeatable strategy! 

The Unbeatable Strategy for a Coin Game!

Why strategy needed in the case?

Let's recall the example given in the question.
-------------------------------------------------------------------

Example

  18 20 15 30 10 14

First Player picks 18, now row of coins is
  20 15 30 10 14

Second player picks 20, now row of coins is
  15 30 10 14

First Player picks 15, now row of coins is
  30 10 14

Second player picks 30, now row of coins is
  10 14

First Player picks 14, now row of coins is
  10 

Second player picks 10, game over.

The total value collected by second player is more (20 +
30 + 10) compared to first player (18 + 15 + 14).
So the second player wins.
---------------------------------------------------------------------------------

Here, it's very clear that the player who chooses coins numbered at even positions wins & the one who chooses odd position loses.

So first player who is going to choose coin first need to be smart. All that he/she need to do is make sum of values of all coin at even position, sum of values of all coins at odd positions and compare them. 

If he finds the sum of values of coins at odd position greater then he should choose 1st coin (odd position) followed by 3rd,5th.....(odd positions) & force other to choose even coins

And if he finds the sum of values of coins at even positions greater then he should choose
last coin (which is at even position as number of coins are even).

For example, in above case, 

  18 20 15 30 10 14

first player calculates 

Sum of odd coins = 18 + 15 + 10 = 43
Sum of even coins = 20 + 30 + 14 = 64.  

Since sum of even coins is greater, he should choose 6th coin (which will be followed by 4th and 2nd) and force other player to choose 5th,3rd and 1st coin.

Even in case second player selects 1st coin after 14 at other corner is selected by first, still he can be forced to choose the coin at 3rd position (odd position) if first player selects 2nd coin.

In short, first player need to make sure that he collects all the coins that are at even positions or odd position whichever has greater sum!   

Note that the total number of coins in the case can't be odd as then distribution of coins among 2 will be unequal.

Three Hat Colors Puzzle

A team of three people decide on a strategy for playing the following game.  

Each player walks into a room.  On the way in, a fair coin is tossed for each player, deciding that player’s hat color, either red or blue.  Each player can see the hat colors of the other two players, but cannot see her own hat color.  

After inspecting each other’s hat colors, each player decides on a response, one of: “I have a red hat”, “I had a blue hat”, or “I pass”.  The responses are recorded, but the responses are not shared until every player has recorded her response.  

The team wins if at least one player responds with a color and every color response correctly describes the hat color of the player making the response.  In other words, the team loses if either everyone responds with “I pass” or someone responds with a color that is different from her hat color.

What strategy should one use to maximize the team’s expected chance of winning?

These could be the strategies to maximize the chances of winning!

Three Colors Hats Puzzle - Solution

What's the puzzle? 

There can be two strategies to maximize the chances of winning in the game.

STRATEGY - 1 :   

There are 8 different possible combinations of three color hats on the heads of 3 people. If we assume red is represented by 0 & blue by 1 then those 8 combinations are - 

Here only 2 combinations are there where all are wearing either red or blue hats. That is 2/8 = 25% combinations where all are wearing hat of same color and 6/8 = 75% combinations where either 1 is wearing the different colored hat than the other 2.  In short, at least 2 will be wearing either red or blue in 75% of combinations.

Now for any possible combination, there will be 2 hats of the same color (either blue or red). The one who sees the same color of hats on heads of other two should tell the opposite color as there are 75% such combinations. That will certainly increase the chances of winning to 75%.

STRATEGY 2 :    

Interestingly, here 3 responses from each member of team are possible viz RED (R), BLUE (B) and PASS (P). And every member can see 3 possible combinations of hats on the heads of other 2 which are as 2 RED (2R),  2 BLUE (2B) and 1RED:1BLUE (RB). See below.

Let's think as instructor of this team. We need to cover up all the possible 8 combinations in form of responses in the above table. 

For every possible combination, at least 1 response need to be correct to ensure win. But out of 9 above, 3 responses of 'PASS' are eliminated as they won't be counted as correct responses. So we are left with only 6. Let's see how we can do it.

First of let's take case of 2R. There are 2 responses where A sees 2 RED hats (000,100). We can't make sure A's response correct in both cases. So let A's response for this case be R. So whenever this 000 combination will appear A's response will secure win.

After covering up 000, let's cover up 001. For that, C's response should be B whenever she sees 2 red hats on other 2. And only left response P would be assigned to B.

So far,we have covered up these 2 combination via above responses.  

--------------------------------------------------------------------------

Now, let's take a case of 2B. A can see 2B hats whenever there 011 or 111 appears. Since A's R response is already used previously, let B be her response in the case. So the combination 111 will be covered up with A's response.  

B can see 2B hats in case of 101 or 111. Since 111 is already covered above, to cover up 101, B should say R whenever she sees 2 BLUE hats on the heads of other 2. With this only response left for C in case of 2B is P.

 
With these responses, we have covers of so far,

 
 -------------------------------------------------------------------------

After filling remaining 1 possible response in response table for every team member in case of 1 RED and 1 BLUE hat, 

 B's response as BLUE in this case will ensure win whenever 011 or 110 combination will appear. Similarly, C's response as a RED will secure win whenever 010 or 100 appears as a combination.

------------------------------------------------------------------------------

In this way, there will be at least 1 response correct for every possible 8 combinations. This strategy will give us 100% chances of winning this game!

The above table shows who is going to respond correctly for the given combination ( the block of combination & correct response are painted with the same background color).
 
SIMPLE LOGIC : 

The same strategy can be summarized with very simple logic. 

There must be someone to say RED whenever she sees 2 RED hats; someone should say BLUE and remaining one should say PASS. Similarly, one has to say BLUE; other should say RED & third one should say PASS whenever 2 BLUE hats are seen. Same logic to be followed in case of 1 RED and  1 BLUE hats seen. But while doing this, we need to make sure responses are well distributed & not repeated by single member of team (See table below).