Some Fun Problems, Parts 3, 4, 5, 6, 7, 8, and 9

The following is a set of ten multiple-choice questions:

1. Which question is the first whose answer is b?

(a) 2; (b) 3; (c) 4; (d) 5; (e) 6

2. The only consecutive pair of questions with the same answer is:

(a) 2, 3; (b) 3, 4; (c) 4, 5; (d) 5, 6; (e) 6, 7;

3. The answer to this question is the same as the answer to which question?

(a) 1; (b) 2; (c) 4; (d) 7; (e) 6

4. The number of questions whose answer is a is:

(a) 0; (b) 1; (c) 2; (d) 3; (e) 4

5. The answer to this question is the same as the answer to which question?

(a) 10; (b) 9; (c) 8; (d) 7; (e) 6

6. The number of questions whose answer is a is the same as the number of questions whose answer is what?

(a) b; (b) c; (c) d; (d) e; (e) none of the above

7. In alphabetical order, how many letters apart is the answer to this question from the answer to the next question?

(a) 4; (b) 3; (c) 2; (d) 1; (e) 0. (Note: a and b are one letter apart.)

8. The number of questions whose answer is a vowel is:

(a) 2; (b) 3; (c) 4; (d) 5; (e) 6. (Note: a and e are vowels.)

9. The number of questions whose answer is a consonant is:

(a) a prime number; (b) a factorial number; (c) a square number; (d) a cube number; (e) a multiple of 5

10. The answer to this question is:

(a) a; (b) b; (c) c; (d) d; (e) e

…supposedly this was a Microsoft interview question?

………………………………………………………………

Answers:

1.c, 2.d, 3.e, 4.b, 5.e, 6.e, 7.d, 8.c, 9.b, 10.a

September 5, 2006

Latest Comments

• kiki

  2007-01-30 20:37:31

  Oh my God, Microsoft’s multiple-choice question really is**
  I admit I don’t have the courage to work it out

Some Amusing Puzzles, IV: Problems I Wrote Myself, Guess the Ranking
Xingding posted on 2006-09-05 16:49:00

Problems I Wrote Myself, Guess the Ranking:

Warm-up problem:

In one competition, A, B, C, D, and E took part. After the contest they each predicted:

A said: B is third, C is fifth;

B said: E is fourth, D is fifth;

C said: A is first, E is fourth;

D said: C is first, B is second;

E said: A is third, D is fourth.

It was later discovered that every ranking position was guessed correctly by someone. What place was C?

—This problem is extremely simple. Start from second place: C is first, and second through fifth are, in order, B, A, E, D.

Now look at the problem I made up:

In one competition, A, B, C, D, and E took part. After the contest they each predicted:

A said: At the very least, I won’t rank below B; C ranks below D.

B said: D ranks below C; C ranks below me.

C said: B certainly won’t rank above A; but the worst is still E.

D said: C is worse than E; but the worst is B.

E said: If I’m not the worst, then A is; in any case I’m definitely below B, and A can’t possibly be first.

It was later discovered that exactly one of the two sentences each person said was true.

What place was C?

………………………………………………………………

Hint:

Start with the two sentences spoken by C and D.

………………………………………………………………

Solution:

First, start with the two sentences spoken by C and D. “The worst is still E” and “C is worse than E” cannot both be true; at least one of them must be false. Therefore, at least one of the corresponding other two sentences must be true. And if “the worst is B” is true, then “B certainly won’t rank above A” is also true. So “B certainly won’t rank above A” must be true. Therefore C’s other sentence, “The worst is still E,” is false. A’s statement, “At the very least, I won’t rank below B,” is also true, so A’s other sentence, “C ranks below D,” is false.

If E’s first sentence is true, then since we already know E cannot be the worst, A must be the worst. But we also know that “B certainly won’t rank above A”…

If E’s first sentence is false, then its second sentence is true; that is, E is below B and A is not first. Then B cannot be the worst, so D’s second sentence is false, and D’s first sentence is true, namely that C is worse than E. And since E is worse than B, C is worse than B, which means B’s second sentence is correct. Then B’s first sentence, “D ranks below C,” is false. But earlier we had “C ranks below D”… Could it be that this problem has no solution? Of course not. If you pay attention to the way the problem is stated, you can probably think of it: in fact, the problem never says that tied rankings are not allowed! So when both “D ranks below C” and “C ranks below D” are false, we learn that C and D are tied. At this point C and D are both below E, E is below B, and A cannot rank worse than B, so A is first, which is a contradiction.

So E’s second sentence is false. Going back to the first sentence. Since A is the worst and B cannot rank below A, A and B are tied for last. Therefore D’s second sentence is true, so D’s first sentence is false. That is, “C does not rank worse than E.” And since B’s second sentence is false, its first sentence means D ranks below C. Therefore C must be first place (possibly tied with E).

September 5, 2006

Some Amusing Puzzles, V: Another Ranking Problem, a GMAT Question, a Problem Said to Have Been Set by Einstein, a Problem from “The Best Mathematical Problem of the Last Fifty Years,” and an Olympiad Problem
Xingding posted on 2006-09-05 19:17:07

Another Ranking Problem

A, B, C, D, and E took first through fifth place. They said:

A: I am not in last place.

B: C is third.

C: A is ranked behind E.

D: E is second.

E: D is not first.

It turned out that exactly the first- and second-place finishers lied. What were the rankings?

………………………………………………………………

Solution:

What A said must be true, because otherwise he would be last, and the last-place finisher tells the truth, a contradiction. So A is third or fourth.

If what D said is true, then what E said is false, and D is first; so D said false, contradiction. Therefore D said something false. E is not second, and D is first or second.

If what E said is false, then D is first, so E is second, contradiction. Therefore what E said is true, and D is second.

If B is not first, then what he said is true, so C is third. At that point nobody is first, contradiction. So B is first, and C is not third.

C is neither first nor second, so what he said is true; thus E is third, A is fourth, and C is fifth.

The rankings, in order, are B, D, E, A, C.

A GMAT Question

A, B, C, and D are assigned first, second, third, and fourth places. It is known that:

1. If A is first, then B is fourth;

2. If B is third, then A is fourth;

3. A ranks above C;

4. If D is not first, then A is second;

5. If B is second, then C is not fourth;

6. If B is first, then C is second.

Question: What are the rankings of the four people?

………………………………………………………………

Answer:

From first to fourth place, respectively, they are D, A, C, B.

Supposedly a Problem Set by Einstein:

●Premises:

⒈ There are 5 houses of 5 different colors;

⒉ The owner of each house has a different nationality;

⒊ The 5 people each drink only one kind of beverage, smoke only one brand of cigarette, and keep only one kind of pet;

⒋ No one has the same pet, smokes the same brand of cigarette, or drinks the same beverage as anyone else;

●Clues:

⒈ The Englishman lives in the red house;

⒉ The Swede keeps dogs;

⒊ The Dane drinks tea;

⒋ The green house is to the left of the white house;

⒌ The owner of the green house drinks coffee;

⒍ The person who smokes PALL MALL keeps birds;

⒎ The owner of the yellow house smokes DUNHILL;

⒏ The person who lives in the middle house drinks milk;

⒐ The Norwegian lives in the first house;

⒑ The person who smokes blends lives next to the person who keeps cats;

⒒ The person who keeps horses lives next to the person who smokes DUNHILL;

⒓ The person who smokes BLUE MASTER lives next to the person who keeps horses;

⒔ The German smokes PRINCE;

⒕ The Norwegian lives next to the blue house;

⒖ The neighbor of the person who smokes blends drinks mineral water.

●Question:

Who keeps the fish?

………………………………………………………………

A solution copied from the internet:

Step 1: It can be determined that the Norwegian lives in the yellow house, smokes Dunhill, and is in the first house on the left. Next to him is the blue house with the horses. (Clues: 7, 9, 11, 14. Since the other colors have already been mentioned—green, white, red, blue—the Norwegian must be in the yellow house, and from this we get the cigarette clue.)

Step 2: According to the problem, they each keep a different kind of pet. By elimination, we can know that the Norwegian may keep either “cats” or “fish.” That gives us two paths. The correct answer is to assume he keeps cats; the path with fish does not work.

Step 3: Now we can determine the cigarette brands. The blue house, that is, the person in the second house from the left, smokes Blends. (Clue: 10)

Step 4: Thus, we can directly infer that the Norwegian in the yellow house drinks water. (Clues: 8, 15)

Step 5: At this point there is one question: is the white house fourth from the left, or the last one? But now we can determine it. The clue is “5, the owner of the green house drinks coffee,” because the person in the middle house drinks milk (clue 8). So the middle house is red, the Englishman, and drinks milk. At this point we know the order of the houses: yellow – blue – red – green – white.

Step 6: Again by elimination, we know that the person in the red house smokes “Pall Mall.” (Reasoning: the person in the red house does not drink alcohol—(clues 8 and 12), the owners of the yellow and blue houses’ cigarettes are already known, and the owner of the red house is not German but English (clue 13).) Then at this point we can also determine that the Englishman keeps birds. (Clue 6)

Step 7: Since the owner of the blue house keeps horses, we can determine that he is neither English, Norwegian, nor Swedish. And he smokes Blends (already known). So we can determine that he is not German either. The only remaining explanation is the remaining nationality: Danish. So we also know he drinks tea. (Clue 2)

Step 8: At this point the person who drinks beer is also uniquely determined: it must be the person in the white house. So he smokes Blue Master. At this point, the owners of the first three houses have all been determined, and only German and Swedish remain. Then, via clue 13 that the German smokes Prince, we determine that the owner of the white house is Swedish, and since it is already known that Swedes keep dogs (clue 2), we determine that the German lives in the green house, smokes Prince, and drinks coffee. Then the only remaining pet is — fish.

A Problem from “The Best Mathematical Problem of the Last Fifty Years”

A certain bank has 11 different positions: president, first vice president, second vice president, third vice president, manager, cashier, assistant cashier, accountant, first stenographer, second stenographer, and doorman. These positions are held by Mr. A, Mrs. B, Mr. C, Ms. D, Mr. E, Mrs. F, Mr. G, Miss H, Mr. J, Mrs. K, and Mr. L. It is known that:

1） The third vice president is the president’s adored grandson, but is not liked by Mrs. B or the assistant cashier.

2） The assistant cashier and the second stenographer divide equally their father’s estate.

3） The second vice president and the assistant cashier wear hats of the same style.

4） Mr. G asks Miss H to send him a stenographer at once.

5） The president’s neighbors are Mrs. K, Mr. G, and Mr. L.

6） The first vice president and the manager live in a bachelor club that does not readily admit new members.

7） The doorman has lived since childhood in the same attic room.

8） Mr. A and the second stenographer are social butterflies among the young unmarried people.

9） The second vice president was once engaged to the accountant.

10） The fashionable cashier is the first stenographer’s son-in-law.

11） Mr. J regularly gives his old clothes to Mr. E to wear, but does not let the older accountant know about this.

What position does each of the eleven people hold?

………………………………………………………………

Answer:

A is the third vice president, B is the first stenographer, C is the accountant, D is the second stenographer, E is the guard, F is the president, G is the first vice president, H is the second vice president, J is the cashier, K is the assistant cashier, and L is the manager.

An Olympiad Problem

From Problem 7 for Grade 8 of the 25th All-Union Mathematical Olympiad (1991)

A wants to conduct a certain survey of B. In all, A needs to learn the correct answers to 91 yes-or-no questions. But B may tell a lie in the course of answering one of the questions. How many yes-or-no questions must A ask in order to be sure of obtaining the correct information for those 91 questions? Please design a way of asking questions that satisfies the requirement within 105 questions.

………………………………………………………………

Solution:

Divide the 91 questions to be learned into the following 13 groups: the first group has 13 questions, the second has 12, and so on. After asking each group of questions, insert a check question: “Did you tell a lie in the previous group of questions?” If the answer is yes, then ask that group of questions again one by one; once you find the question to which a lie was given, there is no need to insert any further check question. If B has told no lies in any of the questions, then the questioning will also end after 105 questions.

It should be noted that B may also tell a lie in response to the inserted check question. If, when a group is asked again because of an affirmative answer to the check question, all the answers to that group are consistent with the previous ones, then the one that was a lie is precisely the check question. For example, if the answer to the check question for the last group—the very last question—is that a lie was told, then the last question still has to be asked again; otherwise, one cannot distinguish whether it was the last question itself that contained the lie or whether the lie was in the check question for the last question. Therefore, another apparently quicker method of checking, such as asking “Did you tell a lie in the first half of the questions?” and proceeding by bisection, would be inefficient, because each answer to such a bisection question would require additional confirmation.

September 5, 2006

Latest Comments

• mist

  2006-09-05 21:36:23 

  I posted the version of the problem I tampered with on my blog too; you can come and take a look.
  ps: Recently, when I visit your blog, an error message keeps popping up, and after I confirm it, IE just closes by itself. I wonder what’s going on.

• mist

  2006-09-05 22:48:18 

  I’m still far from being able to publish a book, because it’s really too hard to create a new kind of problem by myself. Right now, all that’s in my head are other people’s patterns。。。。。

• Gu

  2006-09-05 23:19:37

  Sigh, how many of those “fun problem collections” on the market actually have their own original patterns? Aren’t they mostly copied from here and stitched from there, at most changing the characters’ names? Just stringing together a few existing famous problems into one story is enough to make a book. I’ve read some books with only 50 or 100 problems (and many of them are just filler—silly beyond belief—but they get compiled into a book anyway, with print runs of over ten thousand copies!). The few dozen problems we’ve helped Bobo piece together should be about enough to compile a book too~ heh heh~~

Some Fun Problems, VI: A Question About a Set of Keys and Locks
Xing Ding, posted 2006-09-05 23:10:20

A Question About a Set of Keys and Locks

1．

Three custodians guard a vault. The vault is to be fitted with several locks, and the keys are to be distributed appropriately so that:

No one person can open the door alone;

Any two people together can open the door.

How many locks are needed?

………………………………………………………………

Solution:

Three locks are enough. The first person holds keys A and B, the second person holds B and C, and the third person holds C and A. As for why two locks are not enough, that is left to the reader to prove.

2．

A bank’s manager, deputy manager, and four custodians guard a vault. The vault is to be fitted with several locks, and the keys are to be distributed appropriately so that:

The manager can open the door;

The deputy manager can open the door only by cooperating with one custodian of his choice;

Any three custodians working together can open the door, while only two custodians cannot.

How many locks are needed?

………………………………………………………………

Solution:

The manager should obviously hold the keys to all the locks.

The deputy manager should hold all the keys except one kind, and that kind of key should be held by any one of the custodians.

Any two custodians are insufficient to open the door; that is to say, any two custodians together are still missing at least one key. There are 6 possible pairs among the four custodians. Since any three people can certainly come up with the keys, each such pair corresponds to one kind of key; adding the one key held by all four and not held by the deputy manager, there must be at least seven kinds of keys in all. The distribution is as follows:

The manager has all the keys; the deputy manager has keys 2 through 7; and the four custodians’ keys are, in order: (1, 5, 6, 7), (1, 3, 4, 7), (1, 2, 4, 6), (1, 2, 3, 5).

3．

A bank’s manager, two deputy managers, and five custodians guard a vault. The vault is to be fitted with several locks, and the keys are to be distributed appropriately so that:

The manager can open the door;

One deputy manager can open the door only by cooperating with the other deputy manager, or with any two custodians;

Any four custodians working together can open the door, while only three custodians cannot.

How many locks are needed?

………………………………………………………………

Answer:

20 locks are needed.

Some Fun Problems, VII: A Problem Related to the Voting Paradox
Xing Ding, posted 2006-09-05 23:11:21

A Problem Related to the Voting Paradox

Three councilors A, B, and C are allocating a total budget of 400 million yuan in the city council. There are three budget plans: Plan A, Plan B, and Plan C.

Plan A: A gets 200 million, B gets 100 million, C gets 100 million;

Plan B: A gets 100 million, B gets nothing, C gets 300 million;

Plan C: A gets nothing, B gets 200 million, C gets 200 million.

First, Plan A and Plan B are put to a vote, and whichever gets more votes then goes to a vote against Plan C.

How should Councilor A vote?

………………………………………………………………

Solution:

If, in the first vote, A votes for Plan A, then Plan A is also more favorable to B, so Plan A will win. But in the second round, if it is Plan A versus Plan C, then both B and C will think Plan C is more favorable, and in the end A gets nothing at all.

Therefore, in the first vote A should vote for Plan B, and C will also vote for Plan B, so Plan B wins. And in the contest between Plan B and Plan C, A and C will still choose Plan B, and in the end A can obtain 100 million.

Some Fun Problems, VIII: An Improved Fair Division Problem
Xing Ding, posted 2006-09-05 23:27:02

The solution to the previously written “Three People Dividing Peach Juice” problem was far too cumbersome! I really am hopelessly clumsy. In fact, it is not only for three people; the fair-division problem for any number of people has a simple general solution:
The Fair Division Problem for n People

Generalize the problem above (equal division among three people) to any number of people. Is there a general method? (Still assume that repeated subdivision of the item being divided causes no loss.)

………………………………………………………………

Solution:

First let the n people be arranged in order, from No. 1, No. 2, all the way to No. n.

Let No. 1 first select what he considers to be a 1/n share, and then pass this share successively from No. 2 to No. n. When it is passed to a person, he has two choices: 1) if he thinks the share handed to him is less than 1/n, then he does nothing and passes it on to the next person; 2) if he thinks the share is not less than 1/n, then he cuts off the excess as he sees it, and passes on the remainder, which he believes to be exactly 1/n.

When this share finally reaches No. n, suppose the last person to have “cut” it during the whole process is k; then give this piece to k.

At this point, all the people before k and all the people after k will think this piece is less than 1/n; that is, what remains for the other n-1 people to divide in the next step is no less than (n-1)/n, which is satisfactory. And k himself thinks this piece is exactly 1/n, so he also feels it is fair.

The remaining problem then becomes the equal division problem for n-1 people, and by the same method it is reduced step by step to the two-person cake-sharing problem.

September 5, 2006

Latest Comments

• mist

  2006-09-06 10:51:12 

  “Reduction”—it reminds me of an interesting story in What Is the Name of This Book:
  A house catches fire, and there is a hose and a faucet. Then the obvious solution is to attach the hose to the faucet and turn on the faucet to put out the fire.
  Now suppose there is a house that is not on fire, plus a hose and a faucet.
  What would mathematicians do?
  They would first set the house on fire, reduce the situation to the previous one, and then put out the fire~~

Some Fun Problems, IX: A Problem About Game Theory, the Classic Pirate Gold-Division Problem, and Two More Easy Ones
Xing Ding, posted 2006-09-06 00:19:18

A Problem About Game Theory

Countries A and B have been at war for many years. Country A produces two types of fighter planes, A and B; Country B also produces two types of fighter planes, C and D. Statistics over many years show that A beats C with a 60% chance, C beats B with an 80% chance, B beats D with a 70% chance, and D beats A with a 60% chance.

How should A produce its planes? And B?

………………………………………………………………

Solution:

If A produces only one type of fighter, say A; then B will produce only D, which counters A; then A will switch to producing B, which counters D; then B will produce C to counter it…… and so on without end.

But problems of this kind also have proper strategies—the best strategy for A is to produce A and B in a 5:2 ratio; no matter what B does, A can secure a 48% overall win rate. And the best strategy for B is to produce C and D in a 3:4 ratio, which allows B to obtain a 52% win rate.

The Classic Pirate Gold-Division Problem

Ten pirates seized 100 bars of gold hidden in a cellar and planned to divide the spoils. These are pirates who believe in democracy (of course, their own special kind of democracy), and their custom is to divide things in the following way: the most powerful pirate proposes a distribution, and then all the pirates (including the proposer himself) vote on the proposal. If 50% or more of the pirates approve the proposal, it is passed and the spoils are distributed accordingly. Otherwise, the pirate who proposed the plan is thrown into the sea, and then the next most powerful pirate is nominated and the process above is repeated.

All pirates are happy to see one of their comrades thrown into the sea, but if given the choice, they would still rather get some cash. Of course they also do not want themselves to be thrown into the sea. All pirates are rational, and they know that the others are rational too. In addition, no two pirates are equally powerful—they are ranked in a strict order from top to bottom, and everyone knows both his own rank and the ranks of all the others. These gold bars cannot be split further, and multiple pirates are not allowed to share a bar, because no pirate believes his comrades will keep any agreement about sharing a bar. This is a crew in which each man thinks only of himself. What distribution plan should the fiercest pirate propose in order to get the most gold?

………………………………………………………………

Solution copied from the Internet:

We number the pirates: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Before proposing a distribution, Pirate 1 must put himself in the place of the other 9 pirates and analyze their psychology, while also leaving as much benefit as possible for himself. To explain this problem, we must work backward and analyze from the end, starting with Pirate 10.

(1) When the current top 8 pirates have all been thrown into the sea, only 9 and 10 remain. Then 9 naturally gets all 100 bars, and 10 gets nothing, because he himself has 50% of the votes. Pirate 10 knows his own situation very well, so he must support 8.

(2) Pirate 8 of course understands Pirate 10’s psychology, and also knows that 9 will oppose him, so his proposal is: 99 bars for himself, 1 bar for 10, and nothing for 9. He wins 10’s approval with the smallest possible bribe. Pirate 9 knows his own situation very well, so he must support 7.

(3) Pirate 7 also understands the situation—8 opposes him, and 9 supports him. Therefore, if 7’s proposal is: 99 bars for himself, 1 bar for 9, and nothing for 8 or 10, then 7 also gets 50% approval. Similarly, 8 of course supports 6.

(4) Pirate 6 needs to buy off two more pirates in order to secure over 50% approval among the five pirates, so he keeps 98 bars for himself, gives 1 bar each to 8 and 10, and gives nothing to 7 and 9.

(5)．．．．．．

(6) Continuing in this way, after analyzing the psychological state of so many people, Pirate 1’s proposed plan is: 96 bars for himself, 1 each for 3, 5, 7, and 9, and nothing for 2, 4, 6, 8, or 10. In this way he wins all the votes of the odd-numbered pirates, exactly 50%

Two Easy Ones to End With

1. A: “B is lying”; B: “C is lying”; C: “A and B are both lying” — who is lying? … Answer: A and C are lying.

2. A: “One of us is lying”; B: “Two of us are lying”; C: “Three of us are lying”; D: “All of us are lying” — who is lying? … Answer: A, B, and D are lying.

September 6, 2006

Translated from the Chinese original with AI assistance. The original text is authoritative.