GB-BT-CTD

Question 1

Trailing Zeros - How many trailing zeros are there in 100!

Answer 1

Easy problem. Think of prime number decomposition. There are far more 5 than 2, whose combination makes 10 hence adding a zero. 100 = 100 x 99 x …1, there are 20 fives and 4 five squared, which add up to 24. Hence total frequency of 5 is 24.

Question 2

Screwy Pirates - Five Pirates loots 100 gold coins -they are democratic pirates. Most senior pirate suggests the distribution of coins and all pirates vote (including the senior pirate). At least 50% of pirates have to approve the proposal or the most senior member will be fed to shark.

Answer 2

If 1 pirate, Sen. Pirate keeps it all. If 2 pirates, then the Sen. Pirate will keep it all (thanks to his one vote). If three pirates, Sen. Pirate keeps 99 and gives 1 to Pirate 1 (if they decide to kill the Sen. Pirate then the Pirate 2 will keep it all). For 4 Pirates, senior pirate will keep 99 and give one to Pirate 2 or the 2nd pirate won’t get anything. For 5 pirates, (think in above Pirate 3 and Pirate 1 didn’t get anything), hence Sen. Pirate keeps 98 and give one to both Pirate 1 & Pirate 3.

For each odd, 2n+1 pirates, he will offer coins to pirate 1, 3, 5…2n-1 and keeps the rest to himself

Question 3

100 Tigers, 1 Sheep. Magical Island. If a tiger eats the sheep then it will become a sheep. Would the sheep survive?

Answer 3

If there is one tiger, he would eat the sheep. If there are two tigers, then sheep won’t be eaten since one of the tigers will be eaten after it becomes the sheep. They both are rational. Hence - if there are even number of tigers then the sheep won’t be eaten while for odd number of tigers, sheep will be eaten.

Question 4

ABCD need to cross the bridge. Bridge’s weight limit can allow only 2 people to cross at a time. There is only one torch and it’s dark. A takes 10 mins, B takes 5 mins, C takes 2 mins, and D takes 1 min to cross the bridge. What is the least amount it would take to cross the bridge?

Answer 4

Key is to realize that A & B should go together. Let C and D go first (2 mins, 2), D comes back (1 min, 3), A & B cross together (10 mins, 13 mins), C comes back (2 mins, 15 mins), now C and D cross together (17 mins).

Question 5

You and your colleague know that the boss’s birthday can be on: 3/4, 3/5, 3/8, 6/4, 6/7, 9/1, 9/5, 12/1,12/2, or 12/8. You first say you don’t know his birthday and your colleague doesn’t know either. I was told the month while my colleague was told the day. But now both of you declared you don’t know, all of a sudden you know the birthday. What is the birthday?

Answer 5

Days - {1, 2, 4, 5, 7, 8} and Months - { 3, 6,9, 12}.

Frequency - (1-2, 2-1, 4 -2, 5-2, 7-1, 8-2)
Dates can’t be 2 or 7, otherwise my colleague would have known the birthday due to uniqueness of this number. Since C doesn’t know the birthday, I should be convinced that the month is not 6 or 12, because why would the boss say 2 or 7 (rationality assumption). Now months have to be 3 or 9. Since C knows that month can be either 3 or 9, he deduces that the day must be unique otherwise I would have figured it out. If it was March 4 or March 8, they both have the same month and he won’t be able to deduce what his birthday would have been. That only leaves the one option - March 1st. 9/1

Question 6

Normal deck of 52 cards. We turn over two cards at each time. For each pair of Black, they go to dealers pile and each pair of Red, they go to my pile. If cards follow BL or LB then they both are discarded. If I have more cards then the dealer then I win $100, or (including ties) dealer win. If casino is willing to negotiate the price, how much would you want to bet?

Answer 6

Zero!

Think - Probability of me winning is 50%. Every time cards are discarded, the probability remains the same. Hence the dealer will always win.

Question 7

12 Balls, 1 is defective, either heavy or light. We don’t know. How do we find out?

Answer 7

Split balls into three groups of four. Measure two groups, if equal the H or L must be in the 3rd group. Now make two groups, 2 balls from the initial 3rd group and 1B from 3rd and 1B from equal group. Measure and make the next move.

If heavy or light, make two groups of three. In which, group 1 should consist of 2B from initial group 1, 1 from initial group 2, and New Group 2 will consist of 1 EACH from group 1 and 2, and one good ball from group 3.

Question 8

There are 25 horses. 5 Lanes. How many races do we need to determine three fastest horses

Answer 8

Separate each horses into five groups. 1-5, 6-10,11-15,16-20,21-25. Race them (5 races). Let’s assume 1,6,11,16,21 wins. Race them (5+1 = 6 races). Assume they all come in this order, 1,6,11,16,21. Eliminate 16/21 hence group 4 & 5 are not feasible. There can by only horse from group 3 (b/c of 11). There can be only horse from group 2 (let’s say 7 came 2nd from our earlier race). There can be only 2 horses from group 1 (let’s say 2 and 3 from our early race results). Hence race, 2, 3, 6, 7, 11 and determine the two more fastest horses since we already know that 1 is already IN.

Question 9

Infinite sequence: If x^x^x^x… = 2, what is x?

Answer 9

x^x^x^x = x^(x^x^x^x..)
2 = x^(2)
Solve for x and we get sqrt(2). Bingo!

Question 10

Can you pack 53 bricks of dimensions 1x1x4 into a 6x6x6 Box?

Answer 10

No. It is alluring to know that volume of 6x6x6 = 216 is smaller than 53x4 = 212. However - if you work out the problem, this is not feasible. Divide the cube into 2x2x2 box, there are 27 such cubes. Since each 1x1x4 cube require at least such 2x2x2 cubes, we cannot fit them all in one 6x6x6 cube. Similar to a problem where there is a chess board and both Black boxes are taken

Question 11

Calendar Cubes - Get two dices with six sides. I can put any number in it, what number should I put in each dice such that I can arrange any possible dates such that I can figure out the current day of the month?

Answer 11

“Constrain is that there is 11, 22, hence both dices will need to contain these numbers. We can arrange a combination such that

0 | 1 | 2 | 6 | 7 | 8
0 | 1 | 2 | 3 | 4 | 5

Trick is that we can show six as nine. Think outside of the box”

Question 12

Door to Offer - Truthteller and a liar. One of them is standing in front of a door that has the job offer. What question should we ask him/her in order to get the job?

Answer 12

“This is a binary problem. Question we need to ask is that ““Would the other guy say that job offer is behind your door?””

Two possible Scenarios:

(1) Truth teller guards the door to offer, Liar guards the door to exit
(2) Truth teller guards the door to exit, Liar guards the door to offer.

If Truthteller is holding the job offer door: (1) Asked a truthteller - ““NO”” (2) Asked a liar - ““Yes””
If liar is holding the job offer door: (1) Asked a TT - ““Yes”” (2) Asked a liar - ““NO””

If you hear the answer ““Yes”” then choose the opposite door, if ““No”” then choose that door. “

Question 13

Message Delivery - I am trying to mail a secret service to a colleague of mine in a remote location. Cannot trust the messanger service. There is a padlock box, you can lock the box but there can be ONLY one key. How do we solve the problem?

Answer 13

Put the message in the padlock box, lock it and send it off. Ask your colleague to lock the box with a new lock again and send back the box to you. Now you have the box, unlock your lock and re-ship again to your colleague who has the key to his own second lock.

Question 14

Last Ball - 20 Blue balls and 14 Balls. You remove two balls in one draw and do not put these balls back. If both balls are the same color, you add one blue ball. If both balls have different colors, then you add back the red ball. What would be the color of the last ball?

Answer 14

“Let’s follow the rule based system:

(1) [B, B] = [B-1, R]
(2) [B,R] = [B+1,R]
(3) [R,R ] = [B+1,R-2]

Let’s observe two things. R never become an odd number given there are 14 Red balls and R always decreases or stays the same versus B that can go up as well as down. “

Question 15

Last Switch - 4 switches and one bulb. Close the door, how do we know which switch turns on the light?

Answer 15

“Turn switches 1 and 2 on for quite a while. Now turn off switch 1 and turn on swith 3. Run inside the room and deduce based on:

(1) On and hot bulb = Switch 2
(2) Off and hot bulb = Switch 1
(3) On and Cold bulb = Switch 3
(4) Off and cold bulb = Switch 4”

Question 16

Quant Salary - There is a group of us we want to determine our average salary without anyone finding it out.

Answer 16

Quant 1 - Pick a random number and pass the paper. Have quant 2 add his/her salary and pass that number to Quant 3. Each member should add the number and pass it around. In the end, it comes back to Quant 1, he can subtract his random number and add his salary. Divide the final number by number of quants - there we have it.

Question 17

There are 1000 coins - you are told that 980 have tails up, and 20 have heads up. You cannot feel and determine head/tail. You can flip the coin as many time as you want to change the head to tail and vice versa. How do you split these coins into 2 piles such that they both have the exact number of heads?

Answer 17

(1) Pile one has n coins, hence pile two has 1000-n coins (2) Now pile one has m coins with heads, hence pile two has 20-m coins with heads. (3) In pile one there are n-m tails, turn them all over. Hence there are n-m heads in pile one. (4) Observe: Pile one heads = n-m and Pile two heads = 20-m. Solve for n and we have n = 20. Moral of the story, when you devide the pile, make sure you have twenty coins in pile one, and flip them all. This will assure exact number of heads in both piles.

Question 18

Mis-labeled Bags. There are three bags, Apples, oranges and MIX. If ALL bags are mislabeled, what is your strategy to correct the problem by minimizing the number of either or apples taken out from each bag?

Answer 18

Take out one fruit from the MIX bag. If it is oranges, then the Mix bag has oranges, Oranges has apples, and apple bag is mixed.

Question 19

Wise Men - Sultan caputred 50 wise men. He has a glass standing bottom down. Sultan will call each wise man randomly (for infinite amount times), if a wise man speaks up and says that each wise men is called then they all will be set free or they all will go back to prison. Wise men are allowed to communicate only once before they get imprisoned. What can you do to save them?

Answer 19

Select a leader. Each time, a NEW wise man is called by a sultan, this character will make sure that the glass bottom is up. W1 will turn the bottom up, if W2 comes and observe this, he does not do anything. Untill Leader shows up and he turns the glass bottom down. The leader must keep a tally, and when his count hits 49, then he knows that the sultan has called everyone.

Question 20

Series Summation - 1 to 100

Answer 20

[ n * (n * 1) ] / 2 = (100 * 101)/ 2 = 5050

Question 21

Clock pieces. Clock falls and breaks into three pieces. Ironically - sum of each piece is equal. What are the numbers on each piece?

Answer 21

12*(12 +1)/2 = 78. 78/3 = 26. Sum of each group should add upto 26. Key is to realize that 12+1 = 11+2 = 10 + 3 ..= 13. Hence create such a group that adds up to 26.

Question 22

Counterfeit Coins 1 - 10 bags with 100 identical bags in each coin. Each counterfeit coin can weight either 9 or 11 grams. Determine a strategy which bag has a counterfeit coins?

Answer 22

Pick 1 coin from bag 1, Pick 2 coins from bag 2….Pick 10 coins from bag 10. Sum of the weight should (10 * (10+1))/ 2 = 55. 55 x 10 = 550 grams. If the weight is 539 or 541, bag 1 has counterfeit coins, 538 or 542 - bag 2 has counterfeit coins.

Question 23

Glass Ball. We have two glass balls and a 100 story building. If a ball is thrown out of the window, it will not break if the floor number is less than X. What is the strategy that will minimize the number of drops for the worst case scenario?

Answer 23

Since we are trying to minimize the number of throws: let’s say, we have a strategy with a maximum of N throws. Try the Nth floor, if the ball breaks then start from the 1st floor and go to N-1. Here we will meet our criteria of max of N throws.
However, If the ball does not break at the Nth floor, then we can only increase the number of floors by N-1, since for the 2nd ball we will only have N-2 throws left. Using such Logic we can derive that N(N+1)/2 >= 100. Hence N = 14. Since 210 > 200. 14 will be the maximum number of throws, no matter what.

Question 24

Matching Socks. 2 Red socks, 20 Yellow Socks, 31 Blue socks. How many socks do I need to guarantee that I at least have one matching pair?

Answer 24

3 + 1 = 4 Socks

Question 25

Handshakes. 25 fellow team members. Each of the member shake hand with you. Since a number of people in the room haven’t met each other, theere is also a lot of random hand shaking going on. If you don’t know the total number of handshakes, can you say with certainty that there are at least two people present who shook hands exactly with the same number of people?

Answer 25

Yes. There are 26 people and each of them shake hands with you. 25 holes and 26 pigeons.

Question 26

Have we met before? If there are six people at a party, can you show that at least three people have met each other before the party OR at least 3 people were strangers before the party?

Answer 26

Suppose I am the sixth person. I recruit three other people (A, B,C and I am D). If only pair knows each other then, there are at least three people know each other. AD, BD and AB. If no one knows each other then there are at least three people who don’t know each other.

Question 27

Ants on a square: 51 ants, 1 Square with length of 1. I have one glass, which has a radius of 1/7. How do I position a glass such that I encompass at least three ants?

Answer 27

Pigeon hole problem. Remember radius is 1/7, hence the glass will cover 2/7 = .2857 area. Let’s break squares in 5x5 small squares, hence we should have two ants in each square, plus one square with at least three ants. With the area of .2857 which covers about 1.5 squares, our probability of capturing at least three ants is very high.

Question 28

Counterfeit Coins 2: There are five bags with 100 coins each. A coin CAN weight 9, 10 or 11 grams. Each bag will contain coins that are equally weighted. How many times do I need to use the scale in order to determine which type of coin each bag contains?

Answer 28

Pigeon hole problem again: Let’s take 2 bags. Since each bag can have three different weights, there are three possible weights, 3 x 3. Hence nine combinations. Let’s normalize the weights to make our life easier. Average = [ 9+10+11] / 3 = 10. Hence [-1, 0, 1]. If I take one coin from bag 1 and two coins from bag 2, then my weights will have volatility of -3, -2, -1, 0, 1, 2, 3 (seven different possibilities). Since 9 > 7, we are stuck and we know there are two possible scenarios that will have the exact same weight, making it impossible for us to find out the exact weight of each bag. We need - 9 different weights and that is possible with 1 coin from bag 1 and 3 coins from bag 2. Possible weight distribution now is -4, -3, -2 -1, 0, 1, 2, 3,4 (9 possible scenarios, Bingo!). Similar logic can be followed, we know that there are five bags and 3^5 = 243 different combinations needed. Hence weight of our bags must add up to [243 -1 / 2 ] = 121. That is possible if we take, 1 + 3 + 9 + 27 + 81 = 121 coins from each bag in that order. All can be done in one weighting.

Question 29

Modular Arithmetic - What is it?

Answer 29

The modulo operation - denoted as x%y or x mod y - finds the remainder of division of number x by another number y. 5%3 = 2

Property: x1%y = x2%y, then (x1-x2)%y = 0. 5%3 = 2 and 8%3 = 2. (8-3)%3 = 0.

Question 30

Prisoner Problem - 100 Prisoners. Can be set free. Only Red hat or Blue hat. Each prisoner can see everyone’s hat except his own. Each prisoner will be called randomly, they cannot communicate. However they will yell out the color of their hat such that everyone can hear them. One night to solve this mystery, how many prisoner can you save?

Answer 30

99 Prisoners can be saved with 100% and 1 prisoner with 1/2 probability.

Let the first prisoner call out the odd number of hats he sees. If he sees Red hats are odd, he should yell out Red.

Next person called. If he sees even number of hats then he should call out Red (as he is wearing Red). If he still sees odd number of Red hats then obviously he should call out Blue.

Each prisoner will be able to deduce his own hat color combining the knowledge whether the number of red hats is odd among 99 prisoner (excluding his and first prisoner). Every one need to do this only ONCE.

Question 31

Prisoner Problem (hard). 100 prisoners but now we have three color hats. How many prisoners can we save?

Answer 31

Scoring system: Red = 0, Green = 1, Blue = 2. The first prisoner calculates the total score (s) of 99 prisoners and calculates s%3. If the remainder is zero, he will announce red, if 1, then green and 2 = blue.

All prisoner can deduce their scores from the color announced.

99th person sees: 32 R, 29G, 37B = 320+291+37*2 = 103. 99th calculates: (103 + “yelled color”) % 3.

If the first prisoner yelled Blue, that is two. His remainder is two as well. For 103%3 = 1, 104%3 = 2, 105%3 = 0. Hence, his number is 103, 104 or 105. Since he said 2, it would be green.

Question 32

Given an arbitrary integer, come up with a rule to decide whether it is divisible by 9.

Answer 32

Add up all digits of the integer. If the sum is divisible by nine then integer is divisible by nine.

Question 33

A remote island has three types of chameleons. 13 red Cham, 15 green cham, and 17 blue cham. Each time two Chameleon of different colors meet, they change their color to the third color. G and R meets and both of them change their colors to Blue. Is it ever possible that all chameleons to become the same color? Why or why not?

Answer 33

This is the set of [13 15 17]. Reduce this to [0,2,4] = [R G B]. If G and B meets, they both becomes R. Hence new distribution is [2 1 3].

The initial combination of (0,2,4) cannot be converted to [0 0 6]. (0, 2, 4) can be further reduced to (0,1,2). Which can never become (0,0,3).

Answer is NO. And key lies in the realization that combination of (m+1, n+1, p+1) can be converted to the (m,n,p).

Question 34

Coin Split Problem: You have 1000 coins. You split them in 2 piles, let’s say X and Y. You multiply X x Y. Keep this number. Now split X into x1 and x2, multiply x1 * x2. Now do the same with Y, multiply y1*y2. Add XY+x1x2 + y1y2 = Number. Do this till you have one coin left in each pile. What is the final sum?

Answer 34

Let’s start with something small. What if we had 2 coins, the sum would be 1 (since 1 x 1 = 1). For three coins it would (2 * 1 = 2, + 11 = 1, Total = 3). For four coins, (2 * 2 = 4, 11 =1 and 11 =1, Total = 6). Five coins (3 * 2 = 6, 21 = 2 1 1 = 1, 1 1 =1, Total = 10).

2 –> 1
3 –> 3
4 –> 6
5 –> 10

Do you notice a trend? I see [ (x-1)x]/ 2. Hence the final sum for 1000 coins is:
(1000999)/2 = 500*999 = 499500

Question 35

Chocolate Bar problem - Bar has 6 rows and 8 columns (48 small 1x1 squares). Your break it into individual squares by making a number of breaks. Each time, break one rectangle into two smaller rectangles. I can break 6x8 bars into a 6x3 and 6x5. What are the total number of breaks needed in order to break chocolate bar into 48 small squares?

Answer 35

Magic is to realize that there are 48 pieces. 6x8 pieces.

Let’s start with a smaller piece. If there is one piece, it will take 0 breaks. If there are two pieces, it will take 1 break. For three pieces, it will take 2 breaks. Etc..

For 48 pieces, it will take 47 breaks!

Question 36

Race Track - Suppose that I am on a one-way circular track. There are N gas cans randomly placed on different locations of the track. Total sum of the gas is enough to run exactly one circle. Assume we have no gas initially but you can pick up the gas tanks to fill in your gas tanks. Can you always choose a starting position on the track such that my car can complete the entire circle?

Answer 36

Yes.

Let’s say the circle’s circumference is 1 Mile. Let’s assume that I have a car filled with 1G of tank which is the exact amount I need to complete the circle. 1MPG car. Let’s start by a random location, add the gas, take the measurement. Drive to the 2nd gas tank, take the measurement. Do this till you arrive at the initial point. Read through you measurement records and find the lowest measurements, the gas can position corresponding to the lowest measurement should be your starting position if the car has no gas initially.

Question 37

Irrational number - Can you prove that Sqrt(2) is an irrational number?

Answer 37

A rational number can be expresses as a ratio of two integers. An Irrational Number is a real number that cannot be written as a simple fraction. 1.5 is rational since 3/2 = 1.5, however sqrt(2) is not. Pi and e are another irrational numbers.

Question 38

Rainbow hats: Seven prisoners are given the chance to be set free tomorrow. Executioner can choose the color of the hat at his discretion, every prisoner see the hat colors of other six prisoners but not his own. No communication allowed. Each prisoner writes down the guess of his hat color, if ANY ONE of them is right then they all will be set free immediately. How do you save them?

Answer 38

Not hard!

–> ROY G BIV - Rainbow Colors.
–> Apply Color codes:
R = 0, O = 1, Y =2, G =3, B = 4, I = 5, V = 6.

–> Each prisoner is assigned a number: i = 0,1..6

–> Each prisoner will observe the sum of other six prisoners hats’ color codes: Xi where i =1,2…6

–> Each prisoner will guess such that below equation will equal to his assigned number i.

Now Formulate the problem as such:

i = (Xi + Gi)% 7

Work out an example:

Prisoner Code: 0, 1, 2, 3, 4, 5, 6
Prisoner Hat code: 2, 4, 4, 5, 3, 2, 6
Observed Sum: 24, 22, 22, 21, 23, 24, 20

Guess of prisoner 0;

0 = (Gi + 24)%7 = 0, hence Gi must be 4

Go on for other prisoners and You will find the solution.