[CC150] Chapter 6 Brain Teasers
6.1 You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once.
Take one pill from Bottle #1, two pills from Bottle #2, and so on. The total weight should be 1 + 2 + ... + 20 + overweight = 210 + overweight. Overweight is 0.1 grams times the index of the heavy bottle.
6.2 There is an 8x8 chess board in which two diagonal opposite have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer.
It is impossible. A good proof from the book is: original board has 32 black and 32 white squares. By removing two opposite corners (which could be both black or both white), we have 30 of the one color and 32 of the other color. However, each domino always take one white and one black.
6.3 You have a five-quart jug, a three-quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water? Note that the jugs are oddly shaped such that the filling up exactly "half" of the jug would be impossible.
Classic problem which has been done during high school ...
5, 0 --> 2, 3 --> 2, 0 --> 0, 2 --> 5, 2 --> 4, 3
6.4 A bunch of people are living on an island, when a visitor comes with a strange order: all blue-eyed people must leave the island as soon as possible. There will be a flight out at 8:00pm every evening. Each person can see everyone else's eye color, but they do not know their own (nor is anyone allowed to tell them). Additionally, they do not know how many people have blue eyes, although they do know that at least one person does. How many days will it take the blue-eyed people to leave?
Induction. If there is only one blue-eyed people, he will figure out that he is the only one, which implies that he will leave at the first day. If there are two blue-eyed people, they will know there is up to two blue-eyed people. Instead of leaving at the first day, they should wait until the next day; since if there is only one blue-eyed people, there will be no blue-eyed people at the second day. In other words, if there are two blue-eyed people, they will all leave at the second day. Similarly, if there are k blue-eyed people, they will all leave at the kth day.
6.5 There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it is dropped from any floor below, it will not break. You are given two eggs. Find N, which minimizing the number of drops for the worst case.
TBF.
6.6 There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers. Next, he closes every second locker. Then, on his third pass, he toggles every third locker (closes if it is open of opens if it is closed). This process continues for 100 passes, such that on each pass i, the man toggles every ith locker. After his 100th pass in the hallway, in which he toggles only lock #100, how many lockers are open?
nth door is toggled once for each factor of n, including itself and 1. For example, 48 is toggled on rounds 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. A door is left open if and only if the number of factors is odd, which implies that n is a perfect square.
Take one pill from Bottle #1, two pills from Bottle #2, and so on. The total weight should be 1 + 2 + ... + 20 + overweight = 210 + overweight. Overweight is 0.1 grams times the index of the heavy bottle.
6.2 There is an 8x8 chess board in which two diagonal opposite have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer.
It is impossible. A good proof from the book is: original board has 32 black and 32 white squares. By removing two opposite corners (which could be both black or both white), we have 30 of the one color and 32 of the other color. However, each domino always take one white and one black.
6.3 You have a five-quart jug, a three-quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water? Note that the jugs are oddly shaped such that the filling up exactly "half" of the jug would be impossible.
Classic problem which has been done during high school ...
5, 0 --> 2, 3 --> 2, 0 --> 0, 2 --> 5, 2 --> 4, 3
6.4 A bunch of people are living on an island, when a visitor comes with a strange order: all blue-eyed people must leave the island as soon as possible. There will be a flight out at 8:00pm every evening. Each person can see everyone else's eye color, but they do not know their own (nor is anyone allowed to tell them). Additionally, they do not know how many people have blue eyes, although they do know that at least one person does. How many days will it take the blue-eyed people to leave?
Induction. If there is only one blue-eyed people, he will figure out that he is the only one, which implies that he will leave at the first day. If there are two blue-eyed people, they will know there is up to two blue-eyed people. Instead of leaving at the first day, they should wait until the next day; since if there is only one blue-eyed people, there will be no blue-eyed people at the second day. In other words, if there are two blue-eyed people, they will all leave at the second day. Similarly, if there are k blue-eyed people, they will all leave at the kth day.
6.5 There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it is dropped from any floor below, it will not break. You are given two eggs. Find N, which minimizing the number of drops for the worst case.
TBF.
6.6 There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers. Next, he closes every second locker. Then, on his third pass, he toggles every third locker (closes if it is open of opens if it is closed). This process continues for 100 passes, such that on each pass i, the man toggles every ith locker. After his 100th pass in the hallway, in which he toggles only lock #100, how many lockers are open?
nth door is toggled once for each factor of n, including itself and 1. For example, 48 is toggled on rounds 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. A door is left open if and only if the number of factors is odd, which implies that n is a perfect square.
Comments
Post a Comment