18.
A34 PROBLEMS #7
77. [1] (a) What is the least number of weights necessary to weigh any
integral number of pounds from 1 lb. to 63 lb. inclusive, if the
weights must be placed on only one of the scale-pans of a balance?
Generalize to any number of pounds.
(b) Same as (a), but from 1 lb. to 40 lb. if the weights can be placed
in either of the scale-pans. Generalize.
(c) A gold chain contains 23 links. What is the least number of links
which need to be cut so a jeweler can sell any number of links
from 1 to 23, inclusive? Generalize.
78. [2.5] A perfect partition of the positive integer n is a finite sequence a1
a2 · · · ak of positive integers ai , such that each integer 1 m n
can be written uniquely (regarding equal ai ’s as indistinguishable) as a
sum of ai ’s. For instance, there are three perfect partitions of 5, viz.,
11111, 221, and 311, since we have the unique representations 1, 1 + 1,
1 + 1 + 1, 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 in the first case; 1, 2, 2 + 1,
2 + 2, 2 + 2 + 1 in the second; and 1, 1 + 1, 3, 3 + 1, 3 + 1 + 1 in the
third. Show that the number of perfect partitions of n is equal to the
number of ordered factorizations of n + 1 into parts greater than one.
For instance, the ordered factorizations of 12 are 12, 6 · 2, 2 · 6, 4 · 3,
3 · 4, 2 · 2 · 3, 2 · 3 · 2, and 3 · 2 · 2, so there are eight perfect partitions
of 11.
79. [1] Here is a proof by induction that all people have the same height.
We prove that for any positive integer n, any group of n people all have
the same height. This is clearly true for n = 1. Now assume it for n,
and suppose we have a group of n + 1 persons, say P1 , P2 , . . . , Pn+1 .
By the induction hypothesis, the n people P1 , P2 , . . . , Pn all have the
same height. Similarly the n people P2 , P3 , . . . , Pn+1 all have the same
height. Both groups of people contain P2 , P3 , . . . , Pn , so P1 and Pn+1
have the same height as P2 , P3 , . . . , Pn . Thus all of P1 , P2 , . . . , Pn+1
have the same height. Hence by induction, for any n any group of n
people have the same height. Letting n be the total number of people
in the world, we conclude that all people have the same height. Is there
a flaw in this argument?
1
80. [1] The following figure consists of three equal squares lined up together,
with three diagonals as shown.
C
A B
Show that angle C is the sum of angles A and B.
81. [1] Let n be a positive integer.
(a) Show that if 2n − 1 is prime, then n is prime.
(b) Show that if 2n + 1 is prime, then n is a power of two.
Hint: The simplest way to show that a number is not prime is to factor
it explicitly.
82. (a) [2.5] A point P in the interior of an equilateral triangle T is at a
distance of 3, 5, and 7 units from the three vertices of T . What
is the length of a side of T ?
3 5
2
(b) [2.5] More generally, let the point P be at distances a, b, c from the
vertices A, B, C of an equilateral triangle of side length d. Find
a (nonzero) polynomial equation f (a, b, c, d) = 0, symmetric in
a, b, c, d.
(c) [2.5] The symmetry of f in a, b, c is obvious, but why also the
“hidden symmetry” in d? Find a noncomputational proof.
(d) [2.8] Generalize to n dimensions, i.e., find a (nonzero) polynomial
equation f (a0 , . . . , an , d) = 0, symmetric in all n + 2 variables,
satisfied by the distances a0 , . . . , an from a point to the vertices of
a regular simplex of side length d.
(e) [5] Give a noncomputational explanation of the hidden symmetry
of the variable d.
83. [3] Into how few pieces can an equilateral triangle be cut and reassem-
bled to form a square?
84. [2] Let n be an integer greater than one. Show that 1 + 21 + 31 + · · · + n1
is not an integer.
85. [2.5]
(a) Persons X and Y have nonnegative integers painted on their fore-
heads which only the other can see. They are told that the sum
of the two numbers is either 100 or 101. A third person P asks X
if he knows the number on his forehead. If X says “no,” then P
asks Y . If Y says “no,” then P asks X again, etc. Assume both
X and Y are perfect logicians. Show that eventually one of them
will answer “yes.” (This may seem paradoxical. For instance, if
X and Y both have 50 then Y knows that X will answer “no” to
the first question, since from Y ’s viewpoint X will see either 50
or 51, and in either case cannot deduce his number. So how does
either person gain information?)
(b) Generalize to more than two persons.
86. [2.5] Let a(n) be the exponent of the largest power of 2 dividing the
Pn 2i
numerator of i=1 i (when written as a fraction in lowest terms).
For instance, a(1) = 1, a(2) = 2, a(3) = 2, a(4) = 5. Show that
limn!1 a(n) = 1.
3
87. [3–] Write the permutation n, n − 1, . . . , 1 as a product of n2 (the
�
minimum possible) adjacent transpositions si = (i, i+1), 1 i n−1.
For instance, 321 = s1 s2 s1 (or s2 s1 s2 ). What is the least number of si ’s
we need to remove from this product in order to get a product equal to
the identity permutation 1, 2, . . . , n? For instance, if we remove s2 from
s1 s2 s1 then we get s21 = 123 (clearly the minimum possible for n = 3).
Does the answer depend on the way in which we write n, n − 1, . . . , 1
as a product of si ’s?
4
MIT OpenCourseWare
https://ocw.mit.edu/
18.A34 Mathematical Problem Solving (Putnam Seminar)
Fall 2018
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms.
