A pair of old tasks in Massachusetts

For some, I am aware of possible solutions. Some occasionally meet at interviews, less often than about the dining philosophers. It was interesting to learn how to have fun in MassTech.

Task 1 *

Issued 12 identical-looking balls of which, as you said, only one differs in weight. Your task is to determine which one is easier or harder. The only tool at your disposal is a two-cup scale. Only balls can be put on the cups. Scales can be used no more than three times.
Authorship is not installed.

Task 2 *

You have two crystal balls. It is necessary to find out the fall from which of the 100 floors of your building the ball still maintains without breaking. Moreover, you need to find a strategy that requires the minimum number of attempts, assuming the results of the attempts are not as supportive as possible for the chosen method and evaluate this number. You can break both balls in a fruitful search.
Formulated by Mark Gorton.

Task 3 *

Let the guy have 1000 bottles of wine. It turns out that one of them is poisoned. Fortunately, he still has 10 mice, which he is willing to donate for experiments. The experiments take a day, that is, the mouse who drank the poisonous wine dies only after 24 hours. Our hero is just planning a large-scale party for tomorrow. How many of the 1000 bottles can be tested on mice and served up to the table if the guy is seven spies in the forehead? For example, he can give each mouse a try out of one of the bottles and thus be sure of at least ten bottles if no animals are richer. In case of death, the guy receives 999 reliable bottles, but as already indicated, the tasks assume an unfriendly scenario for the chosen test method. All mice should be bottled immediately because there are only 24 hours left before the party.
Threw Sanjay Menon.
')

Task 4 *

Four beer mugs are placed on the edges of a square table, some upside down. A robot crawls across the table and executes three teams (a) “flip the corner mug” (b) “flip two diagonal mugs” (c) “flip two adjacent mugs”. However, after each command it is unpredictable in which corner, on which diagonal or side of the table the circles will attract the robot more. Come up with a series of teams urging the robot to bring the circles at least to uniformity.
Share Benjamin Rossman.

Task 5 ***

Issued: a 8x8 chess board and a set of 31 dominoes (do not ask where to buy one) such that the bone covers exactly two adjacent cells on the board. Two diametrically and diagonally opposite cells are cut out (62 cells remain on the board in this way). Your task is to lay the bones on the board in a proper way, that is, to cover all the cells and not to go beyond the edges.
Submitted by Tasho Statev Kaletha.

Task 6 **

In your hands is a computer with an n-bit machine word that supports the standard operation bits: AND, OR, NOT, XOR, LEFT SHIFT, RIGHT SHIFT. How many bit operations will you need to determine the number of bits set to one in a machine word w? You can consider available any desired number of registers and free operation COPY. The result must be obtained in the form of an integer represented by a machine word.
Task David Karger.

Task 7

Estimate how much will be √1 + √2 + · · · + √50 orally (or on a piece of paper, or on two pieces of paper) as accurately as you can.
Authorship is not installed.

Task 8 **

The prisoner is limited to a square pad. At your disposal are 4 dogs that can patrol the perimeter of the fence. Dogs are one and a half times faster than a convict but weaker. Escape is considered successful if at least two dogs do not interfere with the perimeter crossing. The challenge here is to indicate to the convict his place at the beginning and to bring the dogs to the head how they should behave. You are free to provide each dog with separate instructions.
Sam Yagan shared through Chris Coyne.

Task 9 **

(The notorious problem of two envelopes) You are in the game. Here are two sealed envelopes. In each envelope, the positive number and the numbers in the envelopes vary. You are free to select and print one envelope. After reviewing the content you have the right to finish the game. Your catch number is inside the envelope. Or it’s up to you to choose an unknown number inside another unopened envelope. And now the question: What strategy will provide a probability of more than 1/2 to get a larger number? You have absolutely no reason to speculate about the contents of the envelopes.
The task was first sent by Chris Coyne many years ago. Wonderful solution presented Krzysztof Onak.

Task 10 ***

Show that a unit cube cannot be split into a finite number of smaller cubes with pairwise unequal edge lengths. It should be noted, not so with the square.
Sent by Benjamin Rossman.

Task 11 **

Let COL be the coloring of the set 1..2006 in three colors. Show that there are x, y such that COL (x) = COL (y) and | x - y | is a square.
Presented at the 2006 Maryland Mathematical Olympiad. Borrowed from the blog Luca Trevisan.

Task 12 **

A sheet of paper is broken by a regular grid of regular hexagons (honeycombs), some hexagons on the edges of the sheet will be considered incorrect, but at least one of them is completely empty. Imagine now that hexagons are randomly painted black and white. Prove that there is a black path from the top to the bottom of the sheet, or a white path from left to right. To form a path, two hexagons are considered to be adjacent when they have a common edge. The hexagons on the left edge of the sheet can be attributed to those that have a common edge with this, the left edge of the sheet. The same for the top, bottom and right edges.
Share Benjamin Rossman.

Task 13 *

(The riddle of the sum and the product) Let x and y be two integers 1 <x <y and, moreover, x + y≤100. Sally was told only the sum x + y, but to the Field the product xy. Sally and Paul are the most honest guys, everyone knows that, they never lied to each other.
And so they came up with this conversation:
Paul: “I don't know what these numbers are.”
Sally: “Also news. I know you do not know. "
Paul: “Well, I know your amount now.”
Sally: "Yeah, and now I am your work."
What are the numbers?
Borrowed from the Lance Fortnow blog.

Translator's notes.

Original
The author did not bother to clarify * asterisks, left as is.

I met Task 9 in the formulation with the firm assumption that the contents of the envelopes were doubled. However, the original, the author's version.
Problem 13 is translated correctly and has a strict solution known to me. Answer 4 13.

The compiler, Petar Maymounkov, graduated from Harvard, hooked up at MIT, worked for Tumblr. The author of the Kademlia algorithm and the reference implementation. Now runs the project of distributed computing implemented in the programming language Go , which attracted the attention of your humble servant.

From myself would add:

Bride's task

We have a bride for marriage. Grooms come to the bride with enviable regularity. Grooms in the bridegrooms provide a complete and honest report on all questions posed of any kind. The result of the Smotrin can only be marriage or irrevocable refusal. The abandoned suitors leave immediately and permanently. Time plays against the bride. It is necessary to offer a meaningful strategy for the bride.
The problem statement is attributed to BA Berezovsky.