Brainstorm 脑筋急转弯

这里分享一些 CC189 上Brainstorm的题。

The Heavy Pill (天平称重问题)

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.

The constraint is a little bit tricky. It says we could only use the scale once. That being said, we must weigh
multiple pills at the same time. In fact, we know we must weigh pills from at least 19 bottles at the same time.
Otherwise, if we skipped two or more bottles entirely, how could we distinguish between those missed bottles?

So how can we weigh pills from more than one bottle and discover which bottle has the heavy pills? Let's suppose
there were just 2 bottles, one of which had heavier pills. If we took one pill from each bottle, we would get a
weight of 2.1 grams, but we couldn't know which bottle contributed the extra 0.1 grams. We know we must treat the
bottles differently somehow.

If we took one pill from Bottle #1 and two pills from Bottle #2, what would the scale show? It depends. If Bottle #1
were the heavy one, we would get 3.1 grams. If Bottle #2 were the heavy one, we would get 3.2 grams.

We know the "expected" weight of a bunch of pills. The difference between the expected weight and the actual weight
will indicate which bottle contributed the heavier pills, provided we select a different number of pills from each
bottle.

We can generalize this to the full solution: take one pill from Bottle #1, two pills from Bottle #2, three pills from
Bottle #3, and so on. Weigh this mix of pills. If all pills were one gram each, the scale would read 210 grams
(1 + 2 + 3 + ... + 19 + 20 = 20 * 21 / 2 = 210). Any "overage" must come from the extra 0.1 gram pills.

This formula will tell you the bottle number: (weight - 210) / 0.1.

So, if the set of pills weighed 211.3 grams, then Bottle #13 would have the heavy pills.

Basketball (概率问题)

You have a basketball hoop and someone says that you can play one of two games. Game 1: You get one shot to make the hoop. Game 2: You get three shots and you have to make two of three shots. If p is the possibility of making a particular shot, for which values of p should you pick one game or the other?

Game 1: p
Game 2: p * p * (1 - p) + p * (1 - p) * p + (1 - p) * p * p + p * p * p 
        = 3 * (1 - p) * p ^ 2 + p ^ 3
        = 3p^2 - 2p^3

p > 3p^2 - 2p^3
(2p - 1)(p - 1) > 0
0 < p < 0.5 => Game 1
1 > p >= 0.5 => Game 2

Dominoes (总体问题)

There is an 8x8 chessboard in which two diagonally opposite corners have been cur off. You are given 31 dominoes, and a single domino can cover exactly two squares. Can you use the 31 dominoes to cover the entire board? Prove your answer (by providing an example or showing why it's impossible).

It's impossible.

Because the chessboard initially has 32 black and white squares. By removing opposite corners (which must have the
same color), we're left with 30 of one color and 32 of the other color. Let's say, for the sake of argument, that
we have 30 black and 32 white squares.

Each domino we set on the chessboard will always take up one black and one white square. Therefore, 31 dominoes will
take up 31 black and 31 white squares exactly. On this board, however, we must have 30 black and 32 white squares.
Hence, it's impossible.

Ants on a Triangle (概率问题，从对立面)

T here are three ants on different vertices of a triangle. What is the possibility of collision (between any two or all of them) if they start walking on the sides of the triangle? Assume each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed.

Similarly, find the possibility of collision with n ants on an n-vertex polygon.

The ants will collide if any of them are moving towards each other. So, the only way that they won't collide
is if they are all moving in the same direction (clockwise or counterclockwise). We can compute this probability
and work backwards from there.

Since each ant can move in two directions, and there are 3 ants, the probability is:
P(clockwise) = 1 / 2 ^ 3
P(counterclockwise) = 1 / 2 ^ 3
P(same direction) = 2 / 2 ^ 3

The probability of collision is therefore the probability of the ants not moving in the same direction:
P(collision) = 1 - 2 / 2 ^ 3 = 3 / 4

To generalize this to an n-vertex polygon: there are still only two ways in which the ants can move to avoid a
collision, but there are 2^n ways they can move in total. Therefore, in general, probability of collision is:
P(clockwise) = 1 / 2 ^ n
P(counterclockwise) = 1 / 2 ^ n
P(same direction) = 2 / 2 ^ n = 1 / 2 ^ (n - 1)
P(collision) = 1 - 1 / 2 ^ (n - 1)

Jugs of Water (倒水问题)

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 filling up exactly "hall" of the jug would be impossible.

1. fill up 5-quart jug, and pour the water from 5-quart jug to 3-quart jug. Thus, we have 2-quart water left in
5-quart jug.
2. pour out the water from 3-quart jug, and pour the water from 5-quart jug to 3-quart jug. Thus, we have 2-quart 
water in 3-quart jug.
3. fill up 5-quart jug, and pour the water from 5-quart jug to 3-quart jug until the 3-quart jug is full.
Thus, we have 4-quart water left in 5-quart jug.

If the two jug sizes are relatively prime, you can measure any value between one and the sum of the jug sizes.

Blue-Eyed Island (逻辑推理，从小到大)

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:00 pm every evening. Each person can see everyone else's eye color, but they don't know their own (nor is anyone allowed to tell them). Additionally, they don't 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?

Let's apply the Base Case and Build approach. Assume that there are n people on the island and c of them have
blue eyes. We are explicitly told that c > 0.

Case c = 1: Exactly one person has blue eyes.
Assuming all the people are intelligent, the blue-eyed person should look around and realize that no one else has
blue eyes. Since he knows that at least one person has blue eyes, he must conclude that it is he who has blue eyes.
Therefore, he would take the flight that evening.

Case c = 2: Exactly two persons have blue eyes.
The two blue-eyed persons see each other, but are unsure whether c is 1 or 2. They know, from the previous case,
that if c = 1, the blue-eyed person would leave on the first night.Therefore, if the other blue-eyed person is
still there, he must deduce that c = 2, which means that he himself has blue eyes. Both men would then leave on
the second night.

Case c > 2: The General Case.
As we increase c, we can see that this logic continues to apply. If c = 3, then those three people would immediately
know that there are either 2 or 3 people with blue eyes. If there were two people, then those two people would have
left on the second night. So, when the others are still around after that night, each person would conclude that
c = 3 and that they, therefore, have blue eyes too. They would leave that night.

This same pattern extends up through any value of c. Therefore, if c men have blue eyes, it will take c nights for
the blue-eyed men to leave. All will leave on the same night.

The Apocalypse (概率问题)

In the new post-apocalyptic world, the world queen is desperately concerned about the birth rate. Therefore, she decrees that all families should ensure that they have one girl or else they face massive fines. If all families abide by this policy --- that is, they have continue to have children until they have one girl, at which point they immediately stop --- what will the gender ratio of the new generation be? (Assume that the odds of someone having a boy or a girl on any given pregnancy is equal.) Solve this out logically and then write a computer simulation of it.

G: P = 1 / 2
BG : P = 1 / 2 ^ 2
BBG : P = 1 / 2 ^ 3
BBBG : P = 1 / 2 ^ 4
BBBBG : P = 1 / 2 ^ 5
...

P(B / G) = 0 * 1 / 2 + 1 * 1 / 4 + 2 * 1 / 8 + 3 * 1 / 16 + 4 * 1 / 32 + ...
= 1 - (n + 1) / 2 ^ n

If n is infinite, then P(B / G) = 1.

The Egg Drop Problem (负载均衡系统)

There is a building of 100 floors. If the egg drops from the N-th floor or above, it will break. If it's dropped from any floor below, it will not break. You're given two eggs. Find N, while minimizing the number of drops for the worst case.

As a first try, suppose we drop an egg from the 10th floor, then the 20th, ...
1. If Egg 1 breaks on the first drop (floor 10), then we have at most 10 drops total. (1-9 + 10)
2. If Egg 1 breaks on the last drop (floor 100), then we have at most 19 drops total. (10, 20, ..., 90, 100 + 91 - 99)

Our goal is to create a system for dropping Egg 1 such that the number of drops is as consistent as possible, whether
Egg 1 breaks on the first drop or the last drop.

1. A perfectly load-balanced system would be one in which Drops (Egg 1) + Drops (Egg 2) is always the same, regardless
of where Egg 1 breaks.
2. For that to be the case, since each drop of Egg 1 takes one more step, Egg 2 is allowed one fewer drop.
3. We must, therefore, reduce the number of steps potentially required by Egg 2 by one drop each time. For example,
if Egg 1 is dropped on floor 20 and then floor 30, Egg 2 is potentially required to take 9 steps. When we drop Egg 1
again, we must reduce potential Egg 2 steps to only 8. That is, we must drop Egg 1 at floor 39.
4. Therefore, Egg 1 must start at floor X, then go up by X - 1 floors, then X - 2, ..., until it gets to 100.
5. Solve for X.
X + (X - 1) + (X - 2) + ... + 1 = 100
X * (X + 1) / 2 = 100
X = 13.65

X must be integer.
6. If we round X up to 14, then we would go up by 14, then 13, then 12, and so on. The last increment would be 4,
and it would happen on floor 99. If Egg 1 broke on any of the prior floors, we know we've balanced the eggs such
that the number of drops of Egg 1 and Egg 2 always sum to the same thing: 14. If Egg 1 hasn't broken by floor 99,
then we just need one more drop to determine if it will break at floor 100. Either way, the number of drops is no
more than 14.
If we round X down to 13, then we would go up by 13, then 12, then 11, and so on. The last increment would be 1 and
it would happen at floor 91. This is after 13 drops. Floors 92 through 100 have not been covered yet. We can't
cover those floors in just one step.
Thus, X should be 14. And this takes 14 steps in the worst case.

100 Lockers

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 it if it is open or opens it if it's closed). This process continues for 100 passes, such that on each pass i, the man toggles every i-th locker. After his 100th pass in the hallway, in which he toggles only locker #100, how many lockers are open?

6 closed lockers:
1st: 1 2 3 4 5 6
2nd: 1 -2 3 -4 5 -6
3rd: 1 -2 -3 -4 5 6
4th: 1 -2 -3 4 5 6
5th: 1 -2 -3 4 -5 6
6th: 1 -2 -3 4 -5 -6

number: 1
factors: 1
number: 2
factors: 1, 2
number: 3
fators: 1, 3
number: 4
factors: 1, 2, 4
number: 5
factors: 1, 5
number: 6
factors: 1, 2, 3, 6
...

perfect square: 100
factors: 1 2 4 5 10 20 25 50 100
number of factors: 9

Thus, if the number has odd number of factors, then the locker is open at last.
Only perfect squares have odd number of factors.
So,
1, 4, 9, 16, 25, 36, 49, 64, 81, 100

10 open

Poison

You have 1000 bottles of soda, and exactly one is poisoned. You have 10 test strips which can be used to detect poison. A single drop of poison will turn the test strip positive permanently. You can put any number of drops on a test strip at once and you can reuse a test strip as many times as you'd like (as long as the results are negative). However, you can only run tests once per day and it takes seven days to return a result. How would you figure out the poisoned bottle in as few days as possible?

458. Poor Pigs

7 days.

( x / 7 + 1 ) ^ 10 >= 1000 => x = 7

For example
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

We can use 2 strips to test 25 bottles within 7 * 4 days.
We use strip 1 to detect the row number, and strip 2 to detect the column number.
For example, at day 1, use strip 1 to test the 1st row, use strip 2 to test the 1st column, after 7 days, if strip 1
detects the bottle with poison, and strip 2 doesn't, we just use strip 2 to test 2nd column, until we detects the
bottle with poison. If it still doesn't have the expected bottle after 28 days, we know it must be Bottle #5.

So, we can generalize to a formula:
(total_time / test_time + 1) ^ strip_number = how many bottles can be tested within the total time.

Thus, we only need to put the numbers into the formula and we will get the answer, which is 7 days.