Some of these are very simple, some are not so simple, some are just jokes.
What is the degree of the highest exponent of K when you complete the operation:
(K-A)(K-B)(K-C)...(K-Y)(K-Z)
[solution]
[solution]
n+1
integers
a_{0}, a_{1}, ..., a_{n}
such
that a_{k}=#{j|a_{j}=k}
. I.e.,
a_{0}
is the number of zeros in the sequence,
while a_{20}
in the number of 20-ies in it.
E.g., the sequence of length 4 [1;2;1;0]
satisfies the
condition: these is only one zero there, so
a_{0}=1
, there are two ones, so
a_{1}=2
, there is one two, so
a_{2}=1
, and there are no threes, so
a_{3}=0
. Describe all such sequences.
[solution]
Prove that for any positive integer n, the finite product
prod (1 <= k <= floor(n/2), 3 + 2 cos (2 k pi / n))
is a rational number.
[solution]
I=[0;1]
into
two "uniformly same-size" subsets A
and I-A
,
i.e., so that any subsegment J=[a;b]
of I
would intersect A
and I-A
on sets of the
same Lebesgue measure? (If you don't know what "Lebesgue measure" is,
don't worry - it's just a generalization of the ordinary length to
"bad" sets).
[solution]
[solution]
Prove that for any quadrilateral with sides a
,
b
, c
and d
and area
S
, the following inequality holds: ac+bd >=
S
(when does the inequality turns into equality?)
[solution]
[solution]
[solution]
[solution]
y=x^{2}
was drawn, then the
coordinate axes were erased. Restore the axes with a compass and a
ruler.
This problem was given during the Moscow State University Faculty of Mechanics and Mathematics entrance oral mathematics examination to a Jew, a graduate of my high school, in the Summer 1988 (3 years into "perestrojka"). The guy could not do the problem in the 15-20 minutes allowed, so his two examiners failed him. He went home and consulted a friend of his (a specialist on the matters related to the admission process), and was advised that the problem is unsolvable. So the poor chap went back to appeal his failing grade (one could appeal on the day of the exam only). He found his two tormenters and told them that the problem had no solution. They said it did. He asked them to provide it. They said "this is an appeal hearing, not a consultation" (the usual answer to such a question). He said: "do you know the solution?" They said: "yes, of course." He said: "which one of you does?" They looked at each other and changed his grade from failing to passing, so he was admitted to the University.
More problems with a similar history.
[solution]
[solution]
[solution]
[solution]
[solution]
The obvious solution is for F
to always carry the
flashlight back, i.e., FM+F+FC+F+FG
which means 19
minutes (the notation means: first, F
and M
cross, then F
carries the flashlight back, third,
F
and C
cross together, fourth,
F
carries the flashlight back again, finally,
F
and G
cross). Can you do faster?
It is alleged that this is the standard problem given at an interview at Microsoft.
[solution]
[solution]
[solution]
[solution]
[solution]
A
meets B
where their respective lines
intersect. The same holds for A
and C
,
A
and D
, B
and C
,
B
and D
. Prove that C
and
D
also meet where their lines intersect.
[solution]
Two people are playing heads and tails, one casts n
coins, the other - n+1
. What is the probability that the
second one will have (strictly) more heads than the first one?
[solution]
[solution]
What is acceleration (or, if you prefer, deceleration) of a tennis ball, dropped from a significant height, right after it bounced from the pavement?
[solution]
There are two mathematicians in a room. The product of two
integers >=2
is given to the first mathematician, and
the sum of the same two integers is given to the second one. Hence,
the first mathematician only knows the product and the second only
knows the sum of the two integers. However, both are aware that the
first knows the product and the second knows the sum of the two
integers.
[solution]
[solution]
You have two (2) identical glass balls and a 100-storey building.
If you drop such a ball from the a certain floor, it might break
(obviously, if it breaks when dropped from the i
th floor,
it will also break when dropped from all floors above it.
You have to find such a floor that the balls do not break when dropped
from the floors below it, but do break when dropped from it and floors
above it. You may expend both balls.
What is the minimum number of drops you will have to make?
[solution]
There are 1000 lockers (all locked) and 1000 kids, who lock the unlocked lockers and unlock the locked ones. The first kid touches (i.e., opens) each locker. The second kid touches (i.e., locks) all even lockers. The third kid touches (i.e., opens the locked ones and closes the unlocked ones) all lockers with number divisible by 3. The fourth kid touches the lockers number 4, 8, 12 etc. After the 1000th kid locks (or unlocks, if it was locked already) the locker number 1000, how many lockers are open?
[solution]
3 dark corridors (of the same length) meet in a small room. A cop is trying to catch a bum there. The cop runs with speed 2 meters per secons, while the bum can only make one meter per second. The cop has a weak flashlight - it lights only 1 meter of space. What is the maximum corridor length for which the cop has a winning strategy against the bum? E.g. if all the corridors are just 1 meter, then the cop will stand in the room, light the corridors one after another and catch the bum.
[solution]
For all integers numbers m
,
((m - 1) & (- m - 1)) + 1 == m & -m
[solution]
Let X
and Y
be two independent,
identically distributed random variables with zero mean, which are
more likely to be positive than to be negative. Obviously, their
sum X+Y
also has zero mean, but is it necessarily more
likely to be positive than to be negative?
[solution]
A stupid king decided to eliminate his Academy of Sciences (as a cost-saving measure, after he slashed taxes), and decided to do it as follows: all the scholars are put in one line, one after another, so that the first one sees everyone ahead of him (second through last), while the second sees the third scholar through the last one, and the last one does not see anyone. Then he puts a dunce cap, either red or blue, on each scholar's head, so that the first one knows the cap colors of rest of them, but not his own, the second knows the cap colors of the third through the last one etc. Finally, each scholar, starting with the first one, is asked what color his cap is, and if his guess (which all the other scholars hear) is wrong, he is executed. The scholars may agree in advance on what to do.
What should the scholars do to minimize the casualties?
E.g., they can agree that each odd-numbered scholar will say the cap color of the next one, so that the even-numbered scholars will survive. Can they do better than that?
[solution]
A bum makes 1 cigarette out of 4 cigarette butts. He has 24 cigarette butts. How many cigarettes can he smoke?
[solution]
An ellipse without any markings (no center, no foci, no axes) is drawn. Restore the center, foci and axes and draw the tangent to the ellipse though a given point on (or off) it using a compass and a ruler.
[solution]
An urn contains N
black and white balls, and we do not
know how many balls of each kind there is:
Pr(#white=K)=^{1}/_{(N+1)}
for K=0,...,N
.
The urn was sampled (with replacement) M
times and every
time the ball was while.
What is the posterior probability that all balls in the urn
are white?
[solution]
Placed on a 1 meter long horizontal bar, an ant moving with a speed of 1 m/s, will fall off one end in at most 1 second. When two ants run into each other, they both turn around and keep running with the same speed. Suppose 1000 ants are placed on the bar arbitrarily and start running in arbitrary directions. How long will it take them all to fall off the bar ends? Assume that ants have zero size.
[solution]
This is a ramification of a previous problem.
Suppose there are countably infinitely many scolars, and all of them can see all the others (except for oneself). They are asked all at once, i.e., they do not hear the answers of the others. They win if only finitely many of them are wrong (alternatively: if either all are wrong or all are correct).
Prove that they have a winning strategy.
[solution]
An equilateral triangle is inscribed in a right triangle so that one of its sides is parallel to the hypotenuse. Then everything except for the hypotenuse and the vertexes on it are erased.
Restore the full picture using a compass and a ruler.
[solution]
{2,...,12}
? By
loading the dice we mean assigning probabilities to each side of
the dice. You do not have to "load" both dice the same way.[solution]
A man has 1000 barrels of wine that he wants to use in 1 day. 1 barrel is poisoned. He has 10 plants which will die in 1 day if watered by the poisoned wine. How can he determine which barrel is poisoned?
[solution]
Drop me a note with your favorite puzzle!
If you are too lazy to do the problems yourself, you can read the notes and answers.
Sam Steingold<sds@gnu.org> | created: 1998-01-01 |