714 Number Theory
797.At each cut we add 7 or 11 new pieces. Thus after cuttingxtimes in 8 andytimes
in 12 we have 7x+ 11 y+1 pieces. The problem amounts to showing that the equation
7 x+ 11 y=nhas nonnegative solutions for everyn≥60, but no nonnegative solution
forn=59. This is of course a corollary to Sylvester’s theorem, but let us see how the
proof works for this particular situation.
The numbers 11· 0 , 11 · 1 ,..., 11 ·6 form a complete set of residues modulo 7. This
means that fornequal to one of the numbers 60= 11 · 6 − 6 , 61 = 11 · 6 − 5 ,..., 66 = 11 ·6,
one can find nonnegativexandysuch that 7x+ 11 y=n. Indeed,
60 = 7 · 7 + 11 · 1 ,
61 = 7 · 4 + 11 · 3 ,
62 = 7 · 1 + 11 · 5 ,
63 = 7 · 9 + 11 · 0 ,
64 = 7 · 6 + 11 · 2 ,
65 = 7 · 3 + 11 · 4 ,
66 = 7 · 0 + 11 · 6.Sinceif we are able to cut the sheet of paper intonpieces we are also able to cut it into
n+7, we can prove by induction that the cut is possible for anyn≥61.
Let us now show that the equation 7x+ 11 y =59 has no solution. Rewrite it as
7 x+ 11 (y− 5 )=4. This implies 7x≡ 4 (mod 11). But this meansx≡ 10 (mod 11),
hencex≥10. This is impossible since 7x+ 11 y=59 impliesx≤8. Hence we cannot
obtain 60 pieces, and the problem is solved.
(German Mathematical Olympiad, 1970/71)
798.Multiply the geometric series
1
1 −xa
= 1 +xa+x^2 a+··· and1
1 −xb
= 1 +xb+x^2 b+···.The coefficient ofxnin the product counts the number of ways exponents of the formka
andmbadd up ton. And this iss(n).
799.The numberncan be represented as 4m,4m+1, 4m+2, or 4m+3. The required
solution is provided by one of the following identities:
4 m=( 2 m− 1 )+( 2 m+ 1 ),
4 m+ 1 = 2 m+( 2 m+ 1 ),
4 m+ 2 =( 2 m− 1 )+( 2 m+ 3 ),
4 m+ 3 =( 2 m+ 1 )+( 2 m+ 2 ).The two terms on the right are coprime because either they differ by 1, or they are odd
and differ by 2 or 4.