03964.com

文档资料库 文档搜索专家

文档资料库 文档搜索专家

The Fifty-Sixth William Lowell Putnam Mathematical Competition Saturday, December 2, 1995

A–1 Let be a set of real numbers which? is closed under multiplication (that is, if ? and ? are in ? , then so is ??? ). ¤ ? Let and be disjoint subsets of whose union is ? . Given that the product of any three (not necessarily distinct) elements of ¤ is in ¤ and that the product of any three elements of ? is in ? , show that at least one of the two subsets ¤§?¨? is closed under multiplication. A–2 For what pairs ???? of positive real numbers does the improper integral

?

different columns independent of each other. Let the row sums ???d?Ve of the resulting matrix be rearranged (if necessary) so that ?WHf?RHfe . Show that for some pfghGhSaS7b , it is at least four times as likely that both ?iY?? $ G and e§Y?? $ i as that ??Y??jY?e . B–1 For a partition k of lEGa?0i??V?e?Amt?b??f??¨n4?Voe?VS?p , let kq? # be the number of elements in the part containing # . Prove that for any two partitions k and k!r , there are two distinct numbers # and s in l7Ga?0i?????Amt?b??Vf??¨n4?o??VS?p such that kq ? ? # 'Ytkq??s? and k!ru? # 'Ytk!rv??s? . [A partition of a set is ? a collection of disjoint subsets (parts) whose union is .] B–2 An ellipse, whose semi-axes have lengths ? and ? , rolls without slipping on the curve swYteyxAzx{?|@}~t . How are ???F?e related, given that the ellipse completes one revolution when it traverses one period of the curve? B–3 To each positive integer with p decimal digits, we associate the determinant of the matrix obtained by writing the digits in order across the rows. For example, for

! " #%$ ?'& " # &

" # & " # &(?0)21 #

converge? A–3 The number 1435176988@8A17B has nine (not necessarily distinct) decimal digits. The number C 3 C 6 88@8AC B is such that each of the nine 9-digit numbers formed by replacing just one of the digits 1ED is 1 3 1 6 8881 B by the corresponding digit CFD ( GIHQPRHTS ) is divisible by 7. The number U 3 U 6 88@8U B is related to C 3 C 6 88@8VC B is the same way: that is, each of the nine numbers formed by replacing one of the C D by the corresponding U D is divisible by 7. Show that, for each P , 1 D &WU D is divisible by 7. [For example, if 1?3¨1E6X8@88V1EB`Y2G@SaSEbdceG@SaS7f , then Chg may be 2 or 9, since G@S7S7bac7idS7Saf and G@S7S7bacaSaS7Saf are multiples of 7.] A–4 Suppose we have a necklace of p beads. Each bead is labeled with an integer and the sum of all these labels is pq&rG . Prove that we can cut the necklace to form a string whose consecutive labels # 3d? # 6d?8@88@? #ts satisfy

6

o?f p?Y?i , to the integer 8617 we associate ???5? )?Y G?n bdc . Find, as a function of p , the sum of all the determi6 nants associated with p -digit integers. (Leading digits are assumed to be nonzero; for example, for ptY?i ,

there are 9000 determinants.)

B–4 Evaluate

?

? iaiacEn?& G

v

u

Dxw 3

# D H?y?&?G

for

y?Y2G7?i??88@8¨?ApX8

8 3 iaidc4ni& 66A?0?5 ??????? ~¨? ?? ? Express your answer in the form ? , where ???F?ed?V1

are integers. B–5 A game starts with four heaps of beans, containing 3,4,5 and 6 beans. The two players move alternately. A move consists of taking either a) one bean from a heap, provided at least two beans are left behind in that heap, or b) a complete heap of two or three beans. The player who takes the last heap wins. To win the game, do you want to move ?rst or second? Give a winning strategy. B–6 For a positive real number ? , de?ne

A–5 Let # 3 ? # 6 ?88@85? # s be differentiable (real-valued) functions of a single variable U which satisfy

1 # 3 17? 1 # 6 17? 1 # s 17?

33# 3 $ ? A 3 6 # 6 $r?@??h$ ? 3 s # s Y?? 63# 3 $ ? 6 6 # 6 $r?@??h$ ? 6 s # s Y?? ¨

. . . . . .

Y?? s 3 # 3 $ ? s 6 # 6 $????F$ ? sds4#s

for some constants ?4D?????c . Suppose that for all P , # D???A???c as ????? . Are the functions # 3 ? # 6 ?8@88@? # s necessarily linearly dependent? A–6 Suppose that each of p people writes down the numbers 1,2,3 in random order in one column of a ?%?Rp matrix, with all orders equally likely and with the orders for

?

?u??9Y2l???p!?!???dp?Y?Ga?i??V?e?88@80p78

Prove that lEGa?0i??V?e?8@880p cannot be ? ? expressed ? as the disjoint union of three sets ?u??5? ??? and ???! . [As usual, ? # ? is the greatest integer H # .]

Solutions to the Fifty-Sixth William Lowell Putnam Mathematical Competition Saturday, December 2, 1995

Kiran Kedlaya

A–1 Suppose on the contrary that there exist with ????§?¨ ?¤? ?¨ ? ?¨ and with . Then ????§?! ? ?"¨# ???$?§? ? ?%&¨ while , contradiction.

56? easiest A–2 The integral converges iff '(0) . The?1" 243 ??proof ? ? ( uses “big-O” notation and the fact that 1?2387@9A2BAC3 3 1 BAG3 for D DFE 3 ? . (Here means bounded by a constant times .) So H H 3I2 'FP 3 ( ( 3 3 ??5?? ?Q §1R2 ' 1R2 ??5?? 7¤3 1 ' P ? 7 9@3S2TBAC3VU ?W? @

???¤???§??¨

A–5 Everyone (presumably) knows that the set of solutions of a system of linear ?rst-order differential equations v with constant coef?cients is -dimensional, with ba? ??¤} sis vectors of the form ? ~ ? (i.e. a function times } a constant vector), where the ~ ? 3h are linearly indepen} ?? dent. In particular, our solution can be written as w ?V? ? ??¤}~ ? . ? ? ???

? ~ w but nots 3 to Choose a 3? vector to ~ ? orthogonal } ???? ????? } } ~} ? . Since as , the same is true of ? ; ? } s ~ } ? ? ? ? ? ?? . In other words, if but that is simply ? ? ?? ? , then ? must also go to 0. ???( } } ?@?%h?h?h%?c}

hence X

H

H 3I2 'YP H 3 P Pe)f( 3 3 ( 3

??5?`

§1R2 '

7bac3S2dBAG3 U

?

and similarly X

H 3

??5?`

?1&2 )

7bag3F2dBAG3 U

?

$h

Hence the integral we’re looking at is

iTp 3 q 3 ??5?` BAG3 U ? ??5?` ? 'SPr) 7bag3S2TBAC3 U ? ts 3 h

However, it is easy to exhibit a solution which does not go of the matrix to 0. The sum of the eigenvalues ? ? ( ' ??? , also known as the trace of , being the sum ? ? of the diagonal entries of , is nonnegative, so has an eigenvalue ? with nonnegative real part, and a cor} } responding eigenvector ~ . Then ?¤??? ~ is a solution that does not go to 0. (If ? is not real, add this solution to its complex conjugate to get a real solution, which still doesn’t go to 0.) Hence one ? of the ? ? , say 3? } ?? s ? } ? ( for all .

? ?

, is zero, in which case

The term is bounded by a constant times 3 Uvu 5?` , whose integral converges. Thus we only have to ? 5 ` 3 Uvw 7¤a 3 U8w 5?` decide whether converges. But 'xPd) has divergent integral, so we get convergence if and only if 'I(y) (in which case the integral telescopes anyway). A–3 Let ? and ? be the numbers and ? , re1!? ? U ? ? 2 ? s spectively. We are given that ?b??P ? ??? ? G?A????? ?? 1!? U ? 2 ?dC?A???d? and ?tP??b? ?? for ef( 1 ??h%h?hW?6g 1 ?%h?h%hW??g . Sum the ?rst relation over eh( and we 2 g ?kC?A???d? 2 ?mG?A???d? ?j? ?l? , or ? . get ?iP?? Now add the ?rst and second relations for any particu? n? 1!? U ? 2 2 ? s ? ?o? lar value ? G?A?? ??? of e and we get 2 ? P ? is divisible by 7, and 10 . But we know ? ? ?kG?A???d? s is coprime to 7, so ?pP ?p? .

qbr?( r?Put P , so that q!wA(yq%xy( A–4 Let ? . These form a cyclic sequence that doesn’t change when you rotate the necklace, except that the entire sequence gets translated 3 by a constant. In particular, it makes sense to3 choose ? for which q!? is maximum and ? w ; this way q!?hz make that one for all e , which gives 3 ? 24s%s?s@2{3 Gv 1 7bv , but the right side may be ?&z| P 1 e replaced by epP since the left side is an integer. 3 ? 2?s%s?s?2x3 Gv 1 7¤v s ? h?h%h?s?? ? h%h?h ?

A–6 View ?n?g? this as a random walk/Markov process with states e t the triples of integers with sum 0, corresponding to the difference between the ?rst, second and third rows with their average (twice the number of columns). Adding a new§1 column adds on a random permutation 1 ? ? ? of the vector . I prefer to identify the triple P ? ?n?g? ?? 2e ? ?? 2e ?? in e t with the point etP Pt tfP?e ? the plane, where is a cube root of unity. Then adding a new column corresponds to moving to one of the six neighbors of the current position in a triangular lattice. What we’d like to argue is that for large enough , the ratio of the probabilities of being in any two particular states goes to 1. Then in fact, we’ll see that eventually, 1 ? about six times as many matrices have '?(?)fP )F( 1 ? than '(?)"( ? . This is a pain to prove, though, P and in fact is way more than we actually need. Let ?Rw and w be the probability that we are at the origin, or at a particular point? adjacent to the origin, ? ? w . (In fact, ? w@? respectively. Then ? wc? is ( 1b7@? times the sum of the probabilities of being at ?each v neighbor of the origin at time , but these are all w .)

? v

w So the desired result, which is that 7 ?R v ? ? ? w?? some large , is equivalent to w@?

7 ?

wm? 9?7¤?

9g7@?

for

.

Suppose on the contrary that this is not the case; then v ? ? ?9g7@? w w for some constant . However, if E v ?@? ( , the probability that we chose of the six ? ??@? each $? 7?? ? ? ? ? ????? types of moves times is already , which by Stirling’s approximation is asymptotic to a 6 5 ? ? U8¤ . This term alone is bigger than constant times ? ? 9 ¤ 7 ? 9?7¤ ? ? ? 7 ? w ? w@? wm? , so we must have for some v 1 ? ? 7 ? wm? Pm? for any . (In ? fact, we must have wc? ?f? .) B–1 For a given § , no more than three different values of G3 § are possible (four would require one part each of size at least 1,2,3,4, and that’s already more than 9 el3 ??¨ G3 $? G3 ? § V § ? ements). If no such exist, each pair 3 occurs for at most 1 element of , and since there are ???S? only possible pairs, each must occur exactly once. G3 In particular, each value of § must C3 occur 3 times. G3 However, clearly any given value of § occurs t?§ times, where t is the number of distinct partitions of G3 that size. Thus § can occur 3 times only if it equals 1 or 3, but we have three distinct values for which it occurs, contradiction. B–2 For those who haven’t taken enough physics, “rolling without slipping” means that the perimeter of the ellipse and the curve pass at the same rate, so all we’re saying is that the perimeter of the ellipse equals the length of one period of the sine curve. So set up the integrals:

i x ?6? Q P?'R?????f° i ( ? 24 ???c? )8± Q ? ? ??° s ° '&± ? ? 387 ' ? s 3 h

B–4 The in?nite continued fraction as 9c9c??? ? is de?ned 9g9@?? ? the1b7 limit ? ??w@? ( P ??w . of the sequence ??xT( Notice that the sequence is strictly decreasing (by induction) and thus indeed has a limit ? , which satis?es ? 9c9c??? 1¤7 9c9@??? 2y1 ? . ?y( P ? , or rewriting, ? P ? ( Moreover, we want the greater of the two roots. Now how to compute the eighth root of1 ? ? Notice that 3 3 ? 32? ? if satis?es the quadratic Pd' ( , then we have

? ( ( ? 3I2|1 G3 2 3I2|1 P·' ' ` ? ? 3 9 3 2 1 h | P ' P G3 ?

Clearly, of 3 ? 3Ithen, 241 the positive square roots 3 ? ? the 2kquadratic 9 ??56? 3A2 Pe) satisfy the quadratic ?? P 56? ) 1 ? ( ??5?` ? .3 ? Thus compute is the greater a??bwe 3#2? 1 ? that ? of P ( root , ??? 5?? is the greater root H 3 ?b3d21 ? ? P ( ? of , and is the greater root of 3 ?c3S2?1 ? C?y2 ? 7c9 P ( , otherwise known as . B–5 This problem is dumb if you know the SpragueGrundy theory of normal impartial games (see Conway, Berlekamp and Guy, Winning Ways, for details). I’ll describe how it applies here. To each position you assign a nim-value as follows. A position with no moves (in which case the person to move has just lost) takes value 0. Any other position is assigned the smallest number not assigned to a valid move from that position. For a single pile, one sees that an empty pile has value 0, a pile of 2 has value 1, a pile of 3 has value 2, a pile of 4 has value 0, a pile of 5 has value 1, and a pile of 6 has value 0. You add piles just like in standard Nim: the nim-value of the composite of two games (where at every turn you pick a game and make a move there) is the “base 2 addition without carries” (i.e. exclusive OR) of the nimvalues of the constituents. So our9? starting position, ?T????1R ?T? ? with ( . piles of 3, 4, 5, 6, has nim-value A position is a win for the player to move if and only if it has a nonzero value, in which case the winning strategy is to always move to a 0 position. (This is always possible from a nonzero position and never from a zero position, which is precisely the condition that de?nes the set of winning positions.) In this case, the winning move is to reduce the pile of 3 down to 2, and you can easily describe the entire strategy if you so desire. B–6 Obviously ? have to be greater than 1, and no two can both be rational, so without loss of3Vgenerality as? 3 3t? ? sume that ? and are irrational. Let ? ( P?? 3 ? ¨e? ? denote ?h the fractional . Then if and G?d 7 &¨ §1 part 1b7 of? 1 ?? ?t? ? P ? ? only if . In particular, this 1 ?%h?h%hW? vh? Gv?2·1 7 1 ? g? ? ?v V?hP means that ? contains ? elements, and similarly. Hence for every integer ,

v v?2|1 (?? ? 2 ? ? ? ? vu2|1 2 ? ? ? vu2|1 P ? h ???????

1R2| ? 7

x 3?7 Let? °l 2 ( ? ? ' in the second integral and write 1 ????? ° ± ? ° and you get ?6? i ? ? ? ? ? Q 2 s ' ????? ° ) ± ? ° ° X x ??? i ? ? 24 ? 2 ? ? ? ? s h ( ' ????? ° ' ± ? ° ° x

as

? ? Since the left side is increasing as? a function of ) , we 2 ? have equality if and only if ) (|' .

B–3 For ( we obviously get 45, while for ( the answer is 0 because it both changes sign (because determinants are alternating) and remains unchanged (by symmetry) when you switch v 9 any two rows other than the ?rst one. So only ( is left. By the multilinearity of the determinant, the answer is the determinant of the matrix whose ?rst (resp. second) row is the sum of all possible ?rst (resp. second) G rows. There are 90 a??c? ? ag?g? ?rst rows whose sum is theGa? vector , and 100 ?c? ? a??@? second rows whose sum is a??S??a??@.? Thus the answer a??c?S?a??c? a??@?I??a??g? 9c?g9g?@? h is P ( ( 2

v

1

v

?

Dividing through by 1b7 2| 1b7 ? shows that v ? that for all ,

? vx2?1 P ? 2 ? ? P

v

v 2 and | 1b7 taking 1 the limit as ? ( . That in turn vA2|1 ? ? 2 ? P ? ? vx2|1 (

???

implies

9 h

? q of points ? is dense (and in fact equidistributed) in the unit square. In particular, our claim def7 2 7 ? ? for some integers initely holds unless ' ? ) ( ? ? ? . ' )

v ? ? ?

v

?

Our desired contradiction is equivalent to showing that v the left side actually takes the value 1 for some . Since the left side is an integer, it suf?ces to show that Gvu2?1 7 ?&2 Cvu2|1 7 ? ? 1 v ?gP ? ?gP E for some . A result in ergodic theory (the two-dimensional version 1 ???¤? of the Weil equidistribution theorem) states that if q are linearly independent over the rationals, then the set

On the other hand, suppose that such a relation ? does hold. Since ? and are irrational, by the one-dimensional Weil theorem, the setG3 of points v?7 ? ? v?7 ? ? ??¨t is 3A dense in the set of in the ??P ? ??P 2 ¨ unit square such that ' is an integer. It is simple ) C3 ??¨??¨ enough to show that this set meets the region ? ? ? ? 1 ? ?Y? 3A2 ¨ 1@? 2 unless E ' ) is an integer, and that 1b7 2?1¤7 ? would imply that ? , a quantity between 0 and 1, is an integer. We have our desired contradiction.

3

The Fifty-Seventh William Lowell Putnam Mathematical Competition Saturday, December 7, 1996

A–1 Find the least number such that for any ? two squares of combined area 1, a rectangle of area exists such that the two squares can be packed in the rectangle (without interior overlap). You may assume that the sides of the squares are parallel to the sides of the rectangle. A–2 Let ??? and ??¤ be circles whose centers are 10 units apart, and whose radii are 1 and 3. Find, with proof, the locus of all points ? for which there exists points § on ? ? and ¨ on ? ¤ such that ? is the midpoint of the line segment §?¨ . A–3 Suppose that each of 20 students has made a choice of anywhere from 0 to 6 courses from a total of 6 courses offered. Prove or disprove: there are 5 students and 2 courses such that all 5 have chosen both courses or all 5 have chosen neither course. A–4 Let be the set of ordered triples ? elements of a ?nite set . Suppose that 1.

?

minimal sel?sh sets, that is, sel?sh sets none of whose proper subsets is sel?sh. B–2 Show that for every positive integer y ,

V W W Y W? ' Q y X ?%??? ?4? x Q'y?? X????'? ?4? 9 a T a???a"a"a % Q'y?? ? ! 9 ? ? W B–3 Given that vDr ? ?r ¤ Dx"xDx8?r3?8??H?v Q("xDx"xS?y?? , ?nd, with proof, the largest possible value, as a function of y (with yh??Q ), of r ? r ¤ Y r ¤ rd YbaDa"a'Y r?fe ? r3? Y r?(r ? x W

B–4 For any square matrix usual power series:

V

?

, we can de?ne

g hji ?

by the

"!

of distinct

"!?#$ if and only if %&' (!?#$ ; ) ; 2. "!?#$ if and only if ' (!0#$ 3. "! and 1 23 (! are both in if and only if %' '&24! and 23 5! are both in . ? Prove that there exists a one-to-one function 6 from to 7 such 7 that 68(!@9A68%5!B9C68D! implies &&"!@#E . Note: is the set of real numbers.

A–5 If F is a prime number greater than 3 and V V V prove that the sum

W n ? Y ! ? W ? ¤ ?1t ? x g hki ? Hml ?Q'r ? !s R ?po8q y ? Prove or disprove: there exists a QvuwQ matrix V real entries such that WxWDyzyp{ W X ? g?hki H d x

with

G$HPI%QRFS)1T'U

,

FX G ¤ of binomial coef?cients is divisible by F . A–6 Let Cced be a constant. Give a complete description, with of the of f all continuous functions fhg 7p f sset iq7 proof, ¤ Y "! for all such that S r t ! H r ru# 7 . 7 Note that denotes the set of real numbers.

B–1 De?ne a sel?sh set to be a set which has its own cardiW element. Find, with nality (number of elements) as an proof, the number of subsets of v &Qw"xDx"xS?y?? which are

F W5X`Y

FE X YbaDa"a'Y Q

B–5 Given } %~! a ?nite string of symbols § and | , weW write for the number of } § ’s in minus the number of | ’s. For example, s§u|0|§u|0|§h!?He? . We ? of (concall a string balanced if every substring } s??!??? secutive symbols of) has ??QE? Q . Thus, §u|0|§u|0|§ is not balanced, since it contains the substring |0|§u|0| . Find, with proof, the number of balanced strings of length y . B–6 Let % ? ? !R? ¤ & ¤ !R"xDx"x??f?S&5?w! be the vertices of a convex polygon which contains the origin in its interior. Prove that there exist positive real numbers r and ? such that

? & ? ? ! r? ? ?w? ? Y % ¤ & ¤ !?rS? ? ?w? ? Y?a"a"a Y %f?S&R?(!?r ? ? ? Hxd? dz!5x ? ?

Solutions to the Fifty-Eighth William Lowell Putnam Mathematical Competition Saturday, December 7, 1996

Manjul Bhargava and Kiran Kedlaya

A-1 If ? and ? are the sides of two squares with combined area 1, then ????¤ ? ?§??¨ . Suppose without loss of generality that ? ? . Then the shorter side of a rectangle containing both squares without overlap must be at least ? , and the longer side must be at least ?¤ ? . Hence the desired value of is the maximum of ??¤ ? . To ?nd this maximum, we let ? ?"!$#&%(') ? ?0%21435' with '7698 @)BACEDGF . Then we are to maximize

? is a set of two courses of which ? is taking either both or none. On the other hand, if a student ? is taking ? courses, then he/she occurs in ? ? ? w??? ? ¤ w x$? ? ? ? such pairs ??T)? . As ? ? is minimized for ? ? v , it follows u u that every student occurs in at least ? ? Q w ? ? ¤ w ? Q ? such ? T ? ) ? ¨ ? @ C ? @ stupairs . Hence there can be at most ?

dents, with equality only if each student takes 3 courses, and for each set of two courses, there are exactly 4 students who take both and exactly 4 who take neither. Since there are only 4 ways to complete a given pair of courses to a set of 3, and only 4 ways to choose 3 courses not containing the given pair, the only way for there to be 20 students (under our hypotheses) is if all sets of 3 courses are in fact taken. This is the desired conclusion.

!$#&% ? 'H¤I%B1435'P!$#&%('? ? d

¨ ¨?¤R!S#T% Q 'U¤I%21V3 Q ' Q B Q ¨ Q Q ¤XW Q !$#T%Y 'a`bACcD Q ¨?¤ W ) Q

with equality for 'e?fACEg . Hence this value is the desired value of . A-2 Let hai and h ? be the centers of pqi and p ? , respectively. (We are assuming p i has radius 1 and p ? has radius 3.) Then the desired locus is an annulus centered at the midpoint of h i h ? , with inner radius 1 and outer radius 2. For a ?xed point r on p ? , the locus of the midpoints of the segments str for s lying on p i is the image of p i ¨cC Q , which under a homothety centered at of radius r Q is a circle of radius ¨EC . As r varies, the center Q of this smaller circle traces out a circle p?u of radius v C (again by homothety). By considering the two positions of r on the line of centers of the circles, one sees that p u is centered at the midpoint of haiYh ? , and the locus is now clearly the speci?ed annulus.

However, Robin Chapman has pointed out that the solution is not unique in the problem as stated, because a given selection of courses may be made by more than one student. One alternate solution is to identify the 6 courses with pairs of antipodal vertices of an icosahedron, and have each student pick a different face and choose the three vertices touching that face. In this example, each of 10 selections is made by a pair of students. A-4 In fact, we will show that such a function ? exists with the property that ???)??c)2? 6d? if and only if ? e bf ? ?g hfi? ?j for some cyclic permutation e?)2g&) ?j of ?k)l?E)2? . We proceed by induction on the number of elements in . If ?nmc??)??c)2?Eo and ??k)l?c)l? 6"? , then choose ? with ? ? 5fp? ?? Ufq? ?? , otherwise choose ? with ? ?? srI? ?? srt? ?? .

Q @ ways to choose A-3 The claim is false. There are wyxu?? ?

3 of the 6 courses; have each student choose a different set of 3 courses. Then each pair of courses is chosen by 4 students (corresponding to the four ways to complete this pair to a set of 3 courses) and is not chosen by 4 students (corresponding to the 3-element subsets of the remaining 4 courses). Note: Assuming that no two students choose the same courses, the above counterexample is unique (up to permuting students). This may be seen as follows: Given a group of students, suppose that for any pair of courses (among the six) there are at most 4 students taking both, and at most 4 taking neither. Then there are at most ¨ Q @????D§¤9D Gw x pairs ??T)? , where ? is a student, and ??

Now let u be an element of and v ? `Xm u o . w wS)l?&x be the elements of v labeled such that Let ? i )SwSY ? ? ? i 5fp? ? ? Uf?ySyYyzfp? ???x . We claim that there exists a unique { 6|mT¨})YwSwYw$)B~o such that ???B) u )l???V? i 6?? , where hereafter ??xG? ??? . We show existence ?rst. Suppose no such { exists; then C ? . for all { ) ? 6dm&¨})YwSwSwS)B~o , we have ???4? ) u )l??? 6X ? ? ? ¨ This holds by property 1 for ? and by induction on ? in general, noting that

?

?

) ? ?4? ) u )l? ? 6h? Y ? ?? 4 6 ? ? ? )l? ? ?V? ? i ) u? )Y u )l? ? )2? 4 ?? ? ? ? ? ?? ?4? ? i ) u )l? ? 6??w ? 6 ? , Applying this when ? ??~ , we get ??? i ) u )2??? " ?

? ?4? ? i ) u ) ? ?4? ? ? ?

contradicting the fact that ? ? ) u )l? ? i$ 6b? . Hence ex? istence follows. Now we show uniqueness. Suppose ?? ? ) u )l? ?4? i? 6 ? ; then for any ? ? ? { `?¨T) { ) { ? ¤ ¨ , we have ????)l?&?4? i )2?}? )??}?})2?}?2? i )2??? 6? by the assumption on ? . Therefore

argument gives

?? ? ) u )2? 4 6 ? ?? $ i )Y?? ?4? i )2? ? )2? ? e ??&?2) u )2?}? ? ) ?}?})2?}?2? i 2 ) ??? e 6 ? ? C ? . The case ? ? so ?? ? ) u )l? ?2? i$ 6? ? ? ) u )l? 4 ?? S ? ? i )2? 4 ? ? ? )2? ? 6?? ? i )Y?? V

and the case ? ?

?

? ? l ) ? ? ) u? ? 6 ? u )2?}?})l?G?2? i ) { ¤I¨ is ruled out by u )2? 4 ? ? i )l? V ? ? ? 6??

?l? ? u `?¨ x ? ? ? ~ x}? i ??? ? u ? ? xG? i ??? ? i ? xG? i u?? ? ? xG? ? ?

i ??? i ¨ ¤ Q ? ~ xG? i Q ~ ? ¨ u?? ¨ ` ¤ ~ ~5? xG? ¨ ?

? ? @e??#(??? w P ~ ? ? ? `|~ ? ? d

? ¨ ¨ ¤ ~ p ¤ ?H`|~5? ?}? ??? ?

? ?

` ¨ is similar. { p Finally, we put ? u? in ? ??x )?¤?? if { ??~ , and ? ??? ) ? ???V? i 2 otherwise; an analysis similar to that above shows that ? has the desired property. d A-5 (due to Lenny Ng) For ¨ and ? ¨ ? ? ? ~ d ?e`"¨ , ? divides y w x? ?

¨cCcD ; we shall show in A-6 We ?rst consider the case ? this case ? must be constant. The relation ? ? ? ?? ? ¤R? ? ? BB`5? ? ¤R? ? ? B`5? ? d proves that ? is an even function. Let ? i ? ? be the ? ? p ¤ 5 ? ` ? roots of , both of which are real. If ? r?? ? , de?ne ????f? and ?kxG? i ? W ?kx7`b? for each positive integer ? . By induction on ~ , ? ? f ??xG? i f ??x for all ~ , so the sequence mY? x o tends to a limit ¤ which is a root of ?k?T¤??5?0? not less than ? ? . Of course this means ¤ ? ? ? . Since ? ?? ? ? ? x for all ~ and ? x9? ? ? , we conclude ? ? ? ? ? ? , so ? is constant on ?h ? ? . If ? i f ? f0? ? and ??x is de?ned as before, then by induction, ??x f ?kxG? i f§? ? . Note that the sequence can be de?ned because ? i r ? ; the latter follows by noting that the polynomial ?k?5Q `b?¤I? is positive at ?¨??? and has its minimum at ¨cC r ? , so both roots are greater ?? than ? .d In any d case, we deduce that ? is also constant ? ? ?. on ?ci Finally, suppose ? f§? i . Now de?ne ?z?7????)2??xG? i ? ???x ¤b? . Given that ??x ft? i , we have ?kxG? i r ??x . Thus if we had ?kx fp? i for all ~ , by the same argument as in the ?rst case we deduce ? x?? ?ci and so ? ? ? ? ?Ei$ . Actually, this doesn’t happen; eventually we have ? x r ?ci , in which case ? ? ? ? ?? x ? ? ?Ei$ by what we have already shown. We conclude that ? is a constant

Now suppose ? r ¨cCcD . Then the sequence ?kx de?ned by ? ? ?n@ and ? xG? i ???kx? ¤?? is strictly increasing and has no limit point. Thus if we de?ne ? on 8 ? ? )B? i F as any continuous function with equal values on the endpoints, and extend the de?nition from 8 ? x )2? xG? i F to 8 ?kxG? i )B?kxG? ? F by the relation ? ?? ? ? ?? ? ¤?? , and extend the de?nition further to ? f @ by the relation ? ?? ? ? ?`5? , the resulting function has the desired property. Moreover, any function with that property clearly has this form. B-1 Let 8 ~?F denote the set mT¨T) )YwSwYwk)2~o , and let ? x denote the number of minimal sel?sh subsets of 8 ~?F . Then the number of minimal sel?sh subsets of 8 ~?F not containing 2 function. (Thanks to Marshall Buck for catching an inaccuracy in a previous version of this solution.)

¨ ??`p¨ ? ? ` Q ??`b~?¤"¨ Q ySyYy ~ `p¨ ~ ? j ~ ¨ B`?¨ x ? i ? 7 ? #(?? ) ~

where the congruence ? ? ? ??#(?? means that ?` ? is a rational number whose numerator, in reduced form, is divisible by ? . Hence it suf?ces to show that

x ? ? ?`?¨ ? i ? @h??#(?? w ~ xG? i

We distinguish two cases based on ?R??#(? ?T . First suppose ? ? ?G? ¤0¨ , so that ? ?qD ? . Then

??? B`?¨ x ? i ? ~ x ? i G ??? ¨ ? ? x}? i ~ ?? ? ? ? x}? i ? ?u ? x}? ? ? ?

since ? ?

xG? i Q ~ ? ¨ u? ¨ ¨ ¨ ? ` ¤ ¤ ~ ~5? ~ ? ¤ ¨q`b~5? x ? ??? i G ?G? ? ? @e??#(?? ) ~P???`b~ i

` Q

? ??

¨

?}? ¤?¨ . Now suppose ? ? ?G? ¤|? , so that ? ??D ? ¤ v . A similar

Q

~ is equal to ? x i . On the other hand, for any mini? mal sel?sh subset of 8 ~?F containing ~ , by subtracting 1

from each element, and then taking away the element ~?`?¨ from the set, we obtain a minimal sel?sh subset Q of 8 ~h` F (since ¨ and ~ cannot both occur in a sel?sh Q set). Conversely, any minimal sel?sh subset of 8 ~?` F 8 ? ~ F gives rise to a minimal sel?sh subset of containing ~ by the inverse procedure. Hence the number of minimal sel?sh subsets of 8 ~?F containing ~ is ? x ? . Thus ? we obtain ? x ? ? x i ¤ ? x ? . Since ?}i ? ? ? ?X¨ , we ? ? have ? x ?°? x , where ? x denotes the ~ th term of the Fibonacci sequence. B-2 By estimating the area under the graph of ± 35? using upper and lower rectangles of width 2, we get

? x ? , we deduce ? x u r ? x ? . Continuing in this ? ? ? x r ? ? x iIr?yYySy?r ? i and fashion, we prove that Q ? so ? ? ? for ? ??¨T) )YwSwYw?)B~ , i.e. that the optimal ar? rangement is as claimed. In particular, the maximum

value of the sum is

Q DH¤ Q ¨ yQ ? ¤ ~e`t¨ ?y ~?¤0¨ ? y v ¤ y ySyYy ¤"?~e` ?y ~ ? Q ¤R~ ? `|~?¤"?¨ ? `t¨ ¤ Y y ySy ¤"8V~e`t¨ ? `p¨$F ~ `p¨ ~P Q ~ `p¨ ?q~ ? `b~?¤ Q `q?~e`t¨ ¤ ? Q ~ u ¤ ~??q`p¨}¨Y~?¤?¨Yg v ? w ?

Alternate solution: We prove by induction that the value given above is an upper bound; it is clearly a lower bound because of the arrangement given above. Assume this is the case for ~s`¨ . The optimal arrangement for ~ is obtained from some arrangement for ~?`0¨ by inserting ~ between some pair ?) ? of adjacent terms. This operation increases the sum by ~j??¤p~ ? `I? ? ? ~??`|~`?? ~` ? , which is an increasing function of both ? and ? . In particular, this difference is maximal Q when ? and ? equal ~h`q¨ and ~h` . Fortunately, this yields precisely the difference between the claimed upper bound for ~ and the assumed upper bound for ~a` ¨ , completing the induction. B-4 Suppose such a matrix exists. If the eigenvalues of (over the complex numbers) are distinct, then there i exists a complex matrix p such that v ? p?Hp ? is 2 % 4 1 3 diagonal. Consequently, v is diagonal. But then %B143 ? p ? i ?%B143 v?2p must be diagonalizable, a contradiction. Hence the eigenvalues of are the same, i and has a conjugate v ? p?ap ? over the complex numbers of the form

? ?x i ? 35?§eT? d Q 3? ± ± vT i x ? i ? ?G d u Since ??± 35?§eT?¨?0? ± 35??` ??¤

¤ ySyYy ¤ ± 3? Q ~¨`t¨ B ± 35?§eT??w

p , we have, upon exponentiating and taking square roots, ? Q ~ p ` ¨ Q ~ `p¨ g ? x}? i g ?¨???G? ?&· f ? ?G? ?&· Q? d ¨ ~ `p¨ yYU v ySySy ¨ g ? xG? i d Q ~?¤?¨ v ul? ? ? ? ? ? & ? · ? Q ~?¤?¨ ? ) f g ? ???Y? ??·

? i )SwYwSwY)B??x as an arrangement of the numbers B-3 View ¨}) Q )SwYwSw?)B~ on a circle. We prove that the optimal arrangement is wSwYwS)2~ `bDz)2~ ` Q )2~?)B~?`p¨})2~ ` v )YwSwYw To show this, note that if ?k)l? is a pair of adjacent numbers and ?E)le is another pair (read in the same order around the circle) with ? f e and ? r ? , then the segment from ? to ? can be reversed, increasing the sum

by

using the fact that ¨ f g fpv .

? ?

? @X? ? w ?y !S#T%(? %21V35? ? w

A direct computation shows that

%21V3 v ?

? %21V3q? @

???P¤I?$e?`b?(??`9?$e7??et`9? ? ?s`b? sr @w

Now relabel the numbers so they appear in order as follows:

Since %21V3 and %21V3 v are conjugate, their eigenvalues must be the same, and so we must have %21V3q?¨??¨ . This implies !$#&%(??X@ , so that %B143 v is the identity matrix, as must be %21V3 , a contradiction. Thus cannot exist. Alternate solution (due to Craig Helfgott and Alex Popa): De?ne both %21V3 and !S#T% by the usual power series. Since commutes with itself, the power series identity

wSwSwS)2??x ? )2??x ? )2??x??0~?)l??x i )2??x u )SwYwSw ? ? ? ? where without loss of generality we assume ? x iqr ? ?&x ? . By considering the pairs ??x ? )2??x and ?&x ? i )l??x u and using the trivial fact ??x r ? ??x i , we ? ? ? deduce ??x ? r ??x u . We then compare the pairs ?&x ? )l??x ? ? and ??x ? i )l?&x u , and using that ??x i r ? ? ? ? ?

3

%B143 ? ¤R!S#T% ? ?0?

holds. But if %2143 is the given ? matrix, Q then by the above identity, !$#T%l? must equal

@d` @

¨ ?T? ? y Y @ ? which is

!$#T% a nilpotent matrix. Thus Q??9Q is also nilpotent. However, the square of any nilpotent matrix must be zero (e.g., by the Cayley-Hamilton theorem). This is a contradiction. ~ checkerboard, in which we write an B-5 Consider a ¨ ~ -letter string, one letter per square. If the string is balanced, we can cover each pair of ?q adjacent squares Q containing the same letter with a ¨ domino, and these will not overlap (because no three in a row can be the same). Moreover, any domino is separated from the next by an even number of squares, since they must cover opposite letters, and the sequence must alternate in between. Conversely, any arrangement of dominoes where adjacent dominoes are separated by an even number of squares corresponds to a unique balanced string, once we choose whether the string starts with ? or h . In other words, the number of balanced strings is twice the number of acceptable domino arrangements. We count these arrangements by numbering the squares @)S¨T)SwYwSw?)B~q`¨ and distinguishing whether the dominoes start on even or odd numbers. Once this is decided, one simply chooses whether or not to x ? ?2? a domino in each Q?? put eligible position. Q Thus we have arrangements in x ??? iB? ? ?2? the ?rst case and in the second, but note that ? the case of no dominoes has been counted twice. Hence the number of balanced strings is Q ??? xG? ? ? ? B i??2 ? ? ¤ Q ??? xG? ? ?? ` Q w

B-6 We will prove the claim assuming only that the convex hull of the points ? ? )l? ? contains the origin in its interior. (Thanks to Marshall Buck for pointing out that the last three words are necessary in the previous sentence!) Let ? ? ± #}?P?)B?b? ± #T? ? so that the left-hand side of the given equation is

Now note that (1) is the gradient of the function

?

) ? ?"gY?T??? i?? ¤t? i ? ? B yYySy ¤Ig??}???

? I ¤ gY?T??? ? ? ¤t? ? ? ¤ ¤ ?x ? ) x ? t

and so it suf?ces to show ? has a critical point. We will in fact show ? has a global minimum. Clearly we have

) ? ?S?(??? ? ? ? ? ? ??&? ? ¤t????? ?? w ? ? B ? ?@)l@ : Note that this maximum is positive for ? )B? ??d ? X ¤ ? ? @ ? ? f if we had ? for all { , then the subset ??? ¤??(? f @ of the ? ? -plane would be a half-plane containing all of the points ? ? )?? ? , whose convex hull would then not contain the origin, a contradiction.

The function ??? ? ?2??? ? ¤p????? is clearly continuous on the unit circle ? ??¤b???H??¨ , which is compact. Hence it has a global minimum ??r @ , and so for all ? )B? ,

???? ? ? ??? ? ¤t????? ??? ? ? ¤R? ? w ~?¤?¨ on the disk of radius In particular, ? ~?¤0¨ C ? . Since ? ?@)l@ ??~ , the in?mum of ? ? is the same over the entire ? ? -plane as over this disk, which again is compact. Hence ? attains its in?mal value at some point in the disk, which is the desired global minimum.

Noam Elkies has suggested an alternate solution as follows: for ?|r @ , draw the loop traced by (1) as ? )2? travels counterclockwise around the circle ? ??¤a???§? ? ? . For ? ?X@ , this of course has winding number 0 about any point, but for ? large, one can show this loop has winding number 1 about the origin, so somewhere in between the loop must pass through the origin. (Proving this latter fact is a little tricky.)

?? i l )?S ? ? ¤ ? i ? ¤b?? ? l ) ? ? ??S??? ? ? ? e ¤ ??? ¤ i ??$?(? ? i? e ? ¤ ? ? ? ) ? ? t ¤ ? ? w (1) x x x x yYySy ??S??? ?

4

The Fifty-Eighth William Lowell Putnam Mathematical Competition Saturday, December 6, 1997

, has sides and A–1 A rectangle, . A triangle has as the intersection of the altitudes, the center of the circumscribed circle, the midpoint of , and the foot of the altitude from . What is the length of ? each has a single penny. Player 1 passes a penny to player 2, who then passes two pennies to player 3. Player 3 then passes one penny to Player 4, who passes two pennies to Player 5, and so on, players alternately passing one penny or two to the next player who still has some pennies. A player who runs out of pennies drops out of the game and leaves the table. Find an in?nite set of numbers for which some player ends up with all pennies.

???¤??? ???¨§¨?? ?¤?§ ? ? ? ? ?!"$#%'&(&'&)10 are seated around a table, and A–2 Players

B–1 Let denote the distance between the real number and the nearest integer. For each positive integer , evaluate

7

n 7po

0

(Here

0 0 A–3 Evaluate 243 @ FE 7AHD G 8 FEH7AG¤ I E(PQB E'E(E1R 5 6"798 7ACB ? G U E'P B E(E'EVRXW 7 & 6 B 7ASS B S 7AE(T G S B S E(7A S S A–4 Let Y be a group with identity ` and acbdYfegY a function such that aihqpsr't1aihqp t1aihqp t § auhwvxr(t1aihwv t1aihyv t S § ` @ § v r v v . Prove S @ that there whenever p r p p S @ ????Y suchS that @ ?h 7 t § ?"aih 7 t exists an element § ?Fh 7 tV?h ? t for all is a homomorphism (i.e. ?h 7%? t ). ? ? Y 7 ? 0 -tuples of posiA–5 Let ?? denote the number of ordered ?? ' ( & ' & ? & h?? ? r ? ????t such that 5 ? ? r B ??? ? B tive &'&'& B integers ??? ? ? §? S S . Determine whether ??r is even or odd. 0 A–6 For a positive integer§ed and any number ? d , de?ne §?? ,real 5 recursively by , and for fhg , r 7x? 7 7 0 § ? r h f?t & 7 ?ji S 7)?ji 8 f B ? 8 7)? 0 and then take ? to be the largest value for which Fix §k d 0 ?¤l lm0 7 ? i r . Find 7 ? in terms of and f , f .

? h7 t B ) ? ? ? ??h 7 t § 8d7 p?h 7 t$?)??h 7 t where ? p h 7 t4g d for all real 7 . Prove that ? ??h 7 t'? is bounded. 0 ? ??? the sum ? sut r B–3 For each positive integer , write ~ ? ? ? | in the form ? ? ? , where ? ? and 0 ? are relatively prime positive ? integers. Determine all such that 5 does not divide ? . ? B–4 Let ? ? s? ? denotes the coef?cient of 7 in the expansion d of h B 7 B 7AS t . Prove that for all [integers] fhg , ? ?? ? ? ? d?lC?1r ? ?w? h ? t ? q ? lk?& t5 8 ? 0 B–5 Prove that for g , 0 terms 0 ? terms 8 ? ?H? ? ? ?j? ? h 0 t& SH? ? ? ??? S'? ? ? ? vx?"?

B–6 The dissection of the 3–4–5 triangle shown below (into four congruent right triangles similar to the original) has diameter . Find the least diameter of a dissection of this triangle into four parts. (The diameter of a dissection is the least upper bound of the distances between pairs of points belonging to the same part.)

B–2 Let be a twice-differentiable real-valued function satisfying

?

vxw?y

? ? § U r ?"q r h{n}P~ n# & 0 0 | | t o o sut ruvxwzy hy? ?? t denotes the minimum of ? and ? .)

?~

Solutions to the Fifty-Eighth William Lowell Putnam Mathematical Competition Saturday, December 6, 1997

Manjul Bhargava, Kiran Kedlaya, and Lenny Ng

A–1 The centroid ? (Euler line), way from ? to the from ? ?way and ? ??

of the triangle is collinear with ? and and the centroid lies two-thirds of the ¤ . Therefore ? is also two-thirds of to ? , so ???¨§? . Since the triangles are similar (they’re right triangles and ? §!#"% $'& (§ )??? ), we have ??"0??1§ ?? "2? , or ?435?6§7 ??839???@§7 A% . Now ?? ?Q ?W ) ? B ¨ § C E ? F D ? H G I B P § C R & ? S G T B V D U 3X? , but

?

and so by induction,

??d r e ? B ?0f#? g ??ijlk B m ?n§o$VrnUsrt3?3?3urE$ q vd r x § h gq e $?y ?

Thus the desired integral is simply

$%$

?!&Q?§

, so

¤YD`¤?!&aCb¤P!&c¤?Gd§e$%¤?§

P§Pf $%$ DgU32A0§ih A2p%UR§i$%pTq B

?w % A–4 In order to have zC{??G|§o}?~C{??G for all ? , we must in particular have this for ??§ g , and so we take }s§i~C g G ?5? .

We ?rst note that

A–2 We show more precisely that the game terminates with one player holding all of the pennies if and only if r §s$0t(DP? or r §s$0t(Di$ for some u . First suppose we are in the following situation for some vQwP$ . (Note: for us, a “move” consists of two turns, starting with a one-penny pass.) – Except for the player to move, each player has pennies;

note that

~ CX?TGS~C g Gl~CX? ?5? Gd§i~C g Gl~CX?TGS~CX? ?5? G and so ~C???G commutes with ~C g G for all ? . Next, we

v

– The player to move has at least v pennies.

We claim then that the game terminates if and only if the number of players is a power of 2. First suppose the number of players is even; then after u complete rounds, every other player, starting with the player who moved ?rst, will have u more pennies than initially, and the others will all have 0. Thus we are reduced to the situation with half as many players; by this process, we eventually reduce to the case where the number of players is odd. However, if there is more than one player, after two complete rounds everyone has as many pennies as they did before (here we need uxwy$ ), so the game fails to terminate. This veri?es the claim. Returning to the original game, note that after one complete round, ?????5? players remain, each with 2 pennies B(? to move, who has either 3 or 4 penexcept for the player nies. Thus by the above argument, the game terminates if and only if ? ???5? is a power of 2, that is, if and only B r ? §i$0t?D?$ for some u . if r §e$0t?D?? or A–3 Note that the series on the left is simply ????????CH&???B"%$%G . By integration by parts,

~C???Gl~C??TGS~C?? ?p? ? ?5? Gd§e~#C g S G ~C??u??Gl~C?? ?5? ? ?p? G and using the commutativity of ~C g G , we deduce ~C g G ?5? ~#C{??Gl~#C g G ?5? ~C{??Gd§e~C g G ?p? ~C{???TG or zC{???TG|§ozC??9G?zIC??TG , as desired. A–5 We may discard any solutions for which } §?} , since ?R? B those come in pairs; so assume } §} . Similarly, we B ? may assume that }???§i}?? , }???§i}?? , }???§o}?? , }??§o} e . ? Thus we get the equation $?"2} ? ? D $?"2}??|D?$?"2}??|D?$h"2}??dD?$h"2}???§??%q Again, we may assume } §i}?? and }???§i}?? , so we get ? } §i}?? , so p?"2} D$h"2}???§ U?"0} ? DIU?"0}???D$h"0}???§?? ; and ? . This implies that Cb} ? &?p?G?C{? }??&?$%G?§y?? ,? which by counting has 5 solutions. Thus ? e is odd. ? is a polynomial in ? of degree r , so it sufA–6 Clearly ? ?0f#? ?ces to identify r values of ? for which ? ?%f#? §P? . We claim these are ??§ r &s??&R$0? for ?§i?T???h??q?q?qq? r &s? ; in this case, ?9? is the coef?cient of ? ? ?5? in the polynomial ? C??SGI §yCS?&g? ?SGS?%CS??D??SG ???5?q? ? . This can be veri?ed by noticing that satis?es the differential equation ?9? C{?SG r &???&?? ? ? C{?SG § ??Da? & ??&t ?

(by logarithmic differentiation) or equivalently,

??d ? d a r B ? B m 0 ? # f ? ? h g ? ? i l j k ? n ? o § $ e e ? B ???p?qgh??ijlk B?m ?

? CH??&t? B G ? ? C ?SG?§ ?? { C ?SG???C r ? & ??&t?0G?CH?&??SG&t??CH??Da?SG?¤ § { C ?SG???C r ? & ??&g$2?0G'&!C r &??G???¤

CbvDo?GH??? f B &?C?vV&??§G??9?)§ Cr ? & ??&g$2?0GH??? f#? &!C r &??§G?????q ?5? In particular, the largest such ? is r &s? , and ? ? §?¨ ?? ? ?p ?q? for vs§P?h??$T??q?q?qq? r . Greg Kuperberg has suggested an alternate approach to show directly that ??§ r &a? is the largest root, without computing the others. Note that the condition ? ?0f#? §o? states that C?? ??q?q?q??S? G is an eigenvector of the matrix ? ? ± ? ? ? § ? D?? ????I§°? r & ?P? § ? &?? ? otherwise with eigenvalue ? . By the Perron-Frobenius theorem, ? has a unique eigenvector with positive entries, whose

eigenvalue has modulus greater than or equal to that of any other eigenvalue, which proves the claim. B–1 It is trivial to check that ? t §?? ? t ·?? ? r ? u ? $ r r , that ??& ? t ? ? §7? ? t ?y ·?? $ r ? u ?Yr ? , that ? t ? &???§?? ? t ?y d ? and that $?& ? t §?? ? t ·e? ? ? ·n ?U r ? u u ? ? U r . ,Therefore ? the desired sum is

and then taking the coef?cient of ?

?

on both sides:

CH??& u r G ? t ?w B ? v ???5? $I& ? u r?? § r q t w ? ?R? ? B–2 It suf?ces to show that ? C??9G?? is bounded for ? ? ?¨w1? , since CS&???G satis?es the same equation as C{??G . But m ? ?? § $ ? ? C{??G?C ? C??9G#D ? ? ? C??9GSG m ? ¨lC C???GlG B DoC C{??GSG B ? o ? §&?$0?T?5C???G?C ? C??9GSG B ? ??? ? so that C C??9GSGHB C ? C{??GSGHB|DiC ? ? Cb?hGSGSB for ?Ww!? . ? B–3 The only such r are the numbers 1–4, 20–24, 100–104,

and 120–124. For the proof let then

?

B v ???5? u ?r D ? v ???p? t u w#? D C r &??GpD ? t w ? ?

?

? v ???5?

? ?t ' ? ? t ??y·· ? ? t ?'· ? ?t ? ·

vo§?v5C r G denotes the largest integer such that ? r ? . We wish to determine those r such that the above sum has nonnegative 5–valuation. (By the 5– valuation of a number } we mean the largest integer ? such that }?"%0? is an integer.) If ? r "0 ? then the last term in the above sum ? ??? , &? has 5–valuation v , since ? ? , ? B , ? ? each have valuation 0; on the other hand, all other terms must have 5–valuation strictly larger than &?v . It follows that ? ? has 5–valuation exactly &?v ; in particular, ? has non? negative 5–valuation in this case if and only if vg§?? , i.e., r §?? , 2, or 3. ? §?U . Then we must also Suppose now that ? r "% ? r ? U . The former condition imhave $%? ? "0 ?5? ? ? $2 ? ? plies that the last term of the above sum is ?2"% ? § ?§"TCH?$3§ ? ? B G , which has 5–valuation &Cbv?&g$%G . ? ? ? It is clear that e ? (mod 25); hence if B ? ? the second–to–last term ? r "% ? ?p? ? equals 20 or 24,B then

where

for for for for

? ? § ? § ? v

v? t w? u

? ? u q

§?U and ? r "0 ?5? ? §?$T? , 22, Finally, suppose ? r "0 ? or 23. Then as before, the ?rst condition implies that the last term of the sum in (*) has valuation &C?vs&?$%G , while the second condition implies that the second–to– last term in the same sum has valuation &C?vp&??G . Hence all terms in the sum (*) have 5–valuation strictly higher than &CbvV&??G , except for the second–to–last term, and therefore ? 5–valuation &C?vV&!?G in this case. In ? has particular, ? is integral (mod 5) in this case if and only ? gives the additional values r §($?? , 22, if v ? , which ? and 23.

B–4 Let

of the above sum (if it exists) has valuation at least &Cbvt& ? G ? . The term (if it exists) is of ? ? B third–to–last 0 " the form , so that the sum of? the last term and ? ? the third to last term takes the form C Di?2"??$hGl"% ? B . ? ? Since congruent only to 0,1, or -1 (mod 5), ? can be and ?§"??$ (mod 5), we conclude that the sum of the ? last term and? third–to–last term has valuation &Cbv?&n$%G , while all other terms have valuation strictly higher. nonnegative 5–valuation in this case only Hence ? ? has when v , leading to the values r §U (arising from $ ? (arising from v?§¨? and ? r "% ? ?p? §($%? v?§(? ), 20,24 ? from and 24 resp.), 101, 102, 103, and 104 (arising ? r v?§?$ , ? "% ?p? §?$0? ) and ? 120, 121, 122, 123, and 124 (arising from? vs§e$ , ? r "0 ?5? §e$2U ).

?

?

?

and introduce the auxiliary function

??? t ??????? t ? ??? w#? ? It is immediate (e.g., by induction) that ? ?%??&?h???h?l?T??? (mod ) for r ? ?h??$T? ? ?lU??? (mod ? 5) respectively, and moreover, we have the equality v ? ? ??? ? ? § e t ?%k ???y? ? t w

2

? ? §4? ? CS&?G ? } ? ?5?q? ? be the given sum? (note that } ? ?5?q? ? is nonzero precisely for ? §i?T??q?q?q???? B ? ? G . Since } t f#?q? ? §o} t ? ? D?} t ? ???p? Da} t ? ??? B ? ? ? &`? ? ?p? ? D ??f B v § C &?G ? C{} ??? ? ? ? Da} ? S ? ? ? ? ? f#? D?} ??? ? ? ? f B G ? v § C &?G ? } ??? ? f#?q? ? f B o S § ?§? f ?hq ?

we have

B–5 De?ne the sequence ? §?$ , ? §?$ i?2??? for r? ? . ? ? r It suf?ces to show that for every , ? ? t f#? ? 3?3?3 t by ? induction on Cr ?àFá?? r r G for some u?? r . We do this , with §e$ being obvious. Write r that ? t

By computing ? e §??h??? §??h??? §1? , we may easB ? ily verify by induction that ? ?S? §6? ?H? f? §×? and so???S? f B §????S? f ?e§x? for all ? w?? . (Alternate lution suggested by John Rickert: write ? ? { C ? ? l ? ? ? ? G § ? G ? , and note note that ?§? is the ? ?d w e C{?FDo????B o D u ? ? B ? coef?cient of ? ? in ??CH&?%?l?TG'§¨CH??Da?TGl"TCH??&t? ? G .)

B–6 The answer is $%?"?? . Place the triangle on the carte? vertices are at ?§YCb?T???hGq????§ sian plane so that its C{??? G?? §¨C?Uu?l?hG . It is easy to check that the ?ve points ?? ? ??I??é?§PC?$0??"?? ? ??$0U?"?? ? G?? and ê?§?C?$hA%"?? ? ?l?hG are all in the triangle and have distance at least $hh"?? apart ? disfrom each other (note that é?ê¨§o$hh"?? ); thus any ? section of the triangle into four parts must have diameter at least $hh"?? .

§?$%?2? , where ? is odd. It suf?ces to show 3?3?3 modulo $ ? and modulo ? , for some uè? r . ? For the former, we only need ? ???5? w?} , r by induction w but clearly ? on r . For the lat???p? ? 3?3?3nC{àFá??W??G as long as ter, note that ? t á?f# ?n ? t ?5??? ? t ? t 3?3??3WC?àF ?E ~? C???GSG , where ~C r G is the Euler totient function. By hypothesis, this occurs for some u???~#C???G|D¨? ? r . (Thanks to Anoop Kulkarni for

catching a lethal typo in an earlier version.)

We now exhibit a dissection with least diameter $hh"?? . ? (Some variations of this dissection are possible.) Put ? ? § CS?h"?? ? ??????"?? ? G , § CS?h"?? ? ?l?hG , ? § C{????????"?? ? G , ìQ§?C ? $h"??T????"?? ? G , and divide into êFì ? , ? ? the convex polygonal regions ? ? é ? ? , ? , é?? ? êFì ; each region has diameter $%?"?? ? , as can be veri?ed by checking the distance between each pair of vertices of each polygon. (One need only check for the pentagon: note that ?é??? and êFì are contained in circular sectors centered at ? and , respectively, of ra? ? dius $hh"?? and angle less than #" , and that ? is ? with diagonal )????$%? h"?? .) a rectangle

?

?

3

The 59th William Lowell Putnam Mathematical Competition Saturday, December 5, 1998

A–1 A right circular cone has base of radius 1 and height 3. A cube is inscribed in the cone so that one face of the cube is contained in the base of the cone. What is the side-length of the cube? A–2 Let s be any arc of the unit circle lying entirely in the ?rst quadrant. Let A be the area of the region lying below s and above the x-axis and let B be the area of the region lying to the right of the y -axis and to the left of s. Prove that A + B depends only on the arc length, and not on the position, of s. A–3 Let f be a real function on the real line with continuous third derivative. Prove that there exists a point a such that f (a) · f ′ (a) · f ′′ (a) · f ′′′ (a) ≥ 0. A–4 Let A1 = 0 and A2 = 1. For n > 2, the number An is de?ned by concatenating the decimal expansions of An?1 and An?2 from left to right. For example A3 = A2 A1 = 10, A4 = A3 A2 = 101, A5 = A4 A3 = 10110, and so forth. Determine all n such that 11 divides An . A–5 Let F be a ?nite collection of open discs in R2 whose union contains a set E ? R2 . Show that there is a pairwise disjoint subcollection D1 , . . . , Dn in F such that E ? ∪n j =1 3Dj . Here, if D is the disc of radius r and center P , then 3D is the disc of radius 3r and center P . A–6 Let A, B, C denote distinct points with integer coordinates in R2 . Prove that if (|AB | + |BC |)2 < 8 · [ABC ] + 1 then A, B, C are three vertices of a square. Here |XY | is the length of segment XY and [ABC ] is the area of triangle ABC . B–1 Find the minimum value of (x + 1/x)6 ? (x6 + 1/x6 ) ? 2 (x + 1/x)3 + (x3 + 1/x3 ) for x > 0. B–2 Given a point (a, b) with 0 < b < a, determine the minimum perimeter of a triangle with one vertex at (a, b), one on the x-axis, and one on the line y = x. You may assume that a triangle of minimum perimeter exists. B–3 let H be the unit hemisphere {(x, y, z ) : x2 + y 2 + z 2 = 1, z ≥ 0}, C the unit circle {(x, y, 0) : x2 + y 2 = 1}, and P the regular pentagon inscribed in C . Determine the surface area of that portion of H lying over the planar region inside P , and write your answer in the form A sin α + B cos β , where A, B, α, β are real numbers. B–4 Find necessary and suf?cient conditions on positive integers m and n so that

mn?1 i=0

(?1)?i/m?+?i/n? = 0.

B–5 Let N be the positive integer with 1998 decimal digits, all of them 1; that is, N = 1111 · · · 11. Find the thousandth digit after the decimal point of √ N.

B–6 Prove that, for any integers √ a, b, c, there exists a positive integer n such that n3 + an2 + bn + c is not an integer.

Solutions to the 59th William Lowell Putnam Mathematical Competition Saturday, December 5, 1998

Manjul Bhargava, Kiran Kedlaya, and Lenny Ng

A–1 Consider the plane containing both the axis of the cone and two opposite vertices of the cube’s bottom face. The cross section of the cone and the cube in this plane consists of a rectangle of sides ? and ??? ? inscribed in an isosceles triangle of base ? and height ¤ , where ? is the side-length of the cube. (The ??? ? side of the rectangle lies on the base of the triangle.) Similar triangles yield ??? ¤§??¨ ??? ???? , or ? ?¨ ? ? "! #?$&% A–2 First solution: to ?x notation, let ' be the area of region (0)§132 , and 4 be the area of (0)657 ; further let 8 denote the area of sector 9@(0) , which only depends on the arc length of ? . If A BDCFEHG denotes the area of tri8RQ angle A BICF E G , then we have P ' ? A @ 9 § ) 2SGTRA 9@(01SG 8VQ A 9@(07WGXYA 9@)§5`G . But clearly A 9@)§2S and 4U? Q 8 Ga? A 9@)§5G and A 9@(01SGb??A 9@(07cG , and so ' 4d? ? .

e and ? . By letting Q ? increase in the latter inequality, ? must be positive for suf?ciently we see that ??? ¨ve large ? ; it follows that ??? ¨ve ???? for all e . Similarly, ??? ¨ve 6?? and ??? ??¨?e §?? imply that ??¨?e 3?? for all e . Therefore ??¨ve ??? ¨ve ??????¨?e ????? ??¨?e x??? for all e , and we are done.

H I O

D E F G

A-4 The number of digits in the decimal expansion of 'xd is the Fibonacci number 1ed , where 1 ?f , 1hgc?i , Q u and 1hdj?f1hd 1hd g for k ?l? . It follows that sbu s the sequence mn' dpo , modulo 11, satis?es the recursion Q ? q ` r s t ' d ??¨?3 ' d ' d g . (Notice that the recursbu s sion for ' d depends only on the value of 1 d g modulo s 2.) Using these recursions, we ?nd that 'xu"v ? and 'yw§vx modulo 11, and that 1 u vU and 1hw§vx modulo 2. It follows that 'ydUvy'xd`zt{ (mod 11) for all k}|~ . We ?nd that among ' 'yg 'y? 'y? 'x? , and u? vanishesQ modulo 11. Thus 11 divides 'xd 'y{ , only ' u if and only if kR??!?? for some nonnegative integer ? . A–5 De?ne the sequence (?? by the following greedy algorithm: let ( be the disc of largest radius (breaking ties u arbitrarily), let ( g be the disc of largest radius not meeting ( , let ( ? be the disc of largest radius not meeting u ( or ( g , and so on, up to some ?nal disc ( d . To see u d? that )l?x? ?# ¤( ? , consider a point in ) ; if it lies in u one of the (?? , we are done. Otherwise, it lies in a disc ( of radius ? , which meets one of the (?? having radius ? |f? (this is the only reason a disc can be skipped in our Q algorithm). Thus the centers lie at a distance ?W? ? than ? ? , and so every point at distance less Q ?? ? ¤ ? from the center of ( lies at distance at most ? from the center of the corresponding ( ? . 8 g 8 g Q ? 4 8 ? | ? ? 'y4???? 4 ? A–6 Recall the inequalities ? 8 'x4?? ??| ? A 'y4 G (Law of Sines). (AM-GM) and ? 'y4???? 4 Also recall that the area of a triangle with integer coordinates is half an integer (if its vertices lie at ¨v? ?T , the area is ? ? ? ¨ ? ? ¨?? ??? ?`? ), and that #? ? if ' and 4 have integer coordinates, then ? 'y4?? g is an integer (Pythagoras). Now observe that 8 8 g Q?? 8 ? g Q A 'x4 Ga?? 'y4?? ?4 ? A 'x4 G 8 g Q ? 8 g Q ?? 'y4?? ?4 ? ? 'x4???? 4 ? 8 Q ? ? A 'y4 G and that the ?rst and second expressions are both 8 8 inte? g Q g Q gers. We conclude that A 'y4 G???? 'y4?? ?4 ?

Second solution: We may parametrize a point in ? by any of e , f , or gh?piq`rtsbu?¨vf ? e . Then ' and 4 are just the integrals Q of fHwe and exwf over the appropriate intervals; thus ' 4 is the integral of eywfS?f?we (minus because the limits of integration are reversed). But Q wg6??eywf6IfHwe , and so ' 4d???Fg is precisely the radian measure of ? . (Of course, one can perfectly well do this problem by computing the two integrals separately. But what’s the fun in that?) A-3 If at least one of ??¨v? , ????¨v? , ??? ? ¨ ? , or ??? ? ??¨v? vanishes at some point ? , then we are done. Hence we may assume each of ??¨ve , ????¨?e , ??? ??¨?e , and ??? ? ??¨?e is either strictly positive or strictly negative on the real line. By replacing ??¨?e by y??¨?e if necessary, we may assume ??? ??¨ve ???? ; by replacing ??¨?e by ??¨?e if necessary, we may assume ??? ? ??¨?e 3??? . (Notice that these substitutions do not change the sign of ??¨?e ??? ¨ve ????? ¨ve ????? ??¨?e .) Now ??? ??¨?e 6??? implies that that ? ? ¨?e ? ? ¨?e is increasing, andQ ? ? ? ? ¨?e 3?? implies Q 3 ? is convex, so that ??? ¨ve ? ??? ¨ve ????? ??¨ve for all

8 8 g 8 g Q ?4 ? ? ? ? 'x4???? 4 ?? ? A 'y4 8 G , and so ? 'y4?? 8? A 'y4 G ; that is, 4 is a right angle and 'y4??~4 , as desired.

?

Piecing our various cases together, we easily deduce that ?¨v? k ? ? if and only if the highest powers of 2 dividing ? and k are different.

? . Then B–5 Write ????¨ ? u?? w ? ? ??? ? ? # ? ?? ? w × ? b s u?? ¤ ? ?#?? w Q s u??? ¨?y ? ? t ¤

B–1 Notice that

{ { Q ¨e ? ? e Y¨?e Q Q Q ? ? ? ¨?e e ¨ve Q ? ? Q ? ¨ve ? e Y¨?e ? e

Q

? e { ? ? ? e ? ?P¤?¨?e Q ? e

(difference of squares). The latter is easily seen (e.g., by AM-GM) to have minimum value 6 (achieved at e?? ). B–2 Consider a triangle as la8 described by the problem; bel its vertices ' 8 4 so that 'l??¨ ? , 4 lies on ? the e -axis, and lies on the line f???e . Further let (???¨ ? be the re?ection of ' in the e -axis, ? and let )??¤¨ ? be the re?ection 8 of ' 8 in the line ?T f??e . Then 'y4?8 ?y(04 and ' ? 8 ) , and so Q 8?QV the of 'y4 is (04 4 )?|(0)?? ? perimeter Q Q g Q ? g . It is clear that ¨ ?§ g ¨v? ? ? ? ? g 8 ? ? ? this lower bound can be achieved; just set 4 (resp. ) to be the intersection between the segment (0) and the e -axis (resp. line ?f ); thus the minimum perimeter Q eI ? g . is in fact ? ? ? g ? B–3 We use the well-known result Q that the surface area of g Q g ??e g the “sphere cap” m?¨ve f f ?? | o § § ¨§ §n? . (This is simply ??? ¨?X result is easily veri?ed using §n? calculus; we omit the derivation here.) Now the desired surface area is just ??? minus the surface areas of ?ve identical halves of sphere caps; these caps, up to isometry, correspond to being the distance from the center §?? ??????±° ? . of the pentagon to any of its sides, i.e., § ? ??? ? ??? ¨" Thus the desired area is ? ? ? ?±° ? #? ? 6 g ? ? ? ? e ? ? ? ). ???? ° ? ?¤ (i.e., 4d? ? Q ? B–4 For convenience, de?ne ???x· d?¨?? ??? ?F? ? db? , so that ?Hd the given sum is ?¨?? k ??? ? ? stu ¨3 ???? r?? ??? . If ? and k are both odd, then ??¨?? k ? is the sum of an odd number of ?F ’s, and thus cannot be zero. Now ? and k have opposite parconsider the case where ? Q ??z ? ?? ity. Note that ? ? ? ? u ? ????? for all Q ? ?Hd ? integers ? ? ? . Thus ? ? ? ? ? s sbu ? ??kV} ? Q ?Hd ? s d stu ? ????? ? and ? d ? Q ; this implies that Q ???x· dp¨v? ???x· dp¨v??k@???? ?Y? k@ ? is odd, and so ??? ?Hd ? ? ¨?3 #????? r?? ?§¨3 #????? r?? s stu for all ? . It follows ? if ? and k have opposite parity. that ?¨?? k ? ??? ? ? and kV? ?`? are both even. Now suppose that ? g g? z Then ? g? ? ?f? g#? u ? for all ? , so ? can be computed as twice the sum over only even indices: g?? ??? stu Q ??zt? ?% ?? ? ? ? ??? ? ? ? ? ?¨ ? ? ¨3 ?P?¨?? ?? ¨ ¨?3 ? ? ? ? ` ? ? ? ThusQ ??¨ ? vanishes if and only if ?¨?? ?? vanishes ??zt? (if ¨?3 ? ? , then ? and ? have opposite parity ? and so ?¨ ? also vanishes). 2

?

? g ? s ??? . Now the digits after the deciwhere ? ? mal point of ?#?? ? ¤ are given by % ¤¤¤¤ %?%?% , while the digits after the decimal point of {u ? sp??? are given by % ?????%?%?% ?!!!!!! %?%?% . It follows that the ?rst 1000 digits of ? ? are given by % ¤¤¤¤¤ %?%?% ¤¤¤¨ ; in particular, the thousandth digit is . Qh? ? Q g Q B–6 First solution: Write . Note ?e¨?k ??k ??k k Q ? ? have the same parity, and recall that ?e¨vk and ?e¨vk

that any perfect square congruent to 0 or 1 (mod 4). Q is ? are perfect squares, they are Thus if ?e¨vk and ?e¨vk Q ? g Q ? congruent mod 4. But ?e¨?k ??e¨vk v ? k (mod ? 4), which is not divisible by 4 if k and have opposite ? parity.

Second solution: We prove more generally that for any polynomial ??¨ with integer coef?cients which is not § a perfect square, there exists a positive integer k such that ??¨?k is not a perfect square. Of course it suf?ces to assume ??¨ has no repeated factors, which is to say § ??¨ and its derivative ?3??¨ are relatively prime. § § In particular, if we carry out the Euclidean algorithm on ??¨ and ?3? ¨ without dividing, we get an in§ § teger ( (the discriminant of ? ) such that the greatest common divisor of ??¨vk and ?3??¨?k divides ( for any k . Now there exist in?nitely many primes ? such that ? divides ??¨?k for some k : if there were %?%?% ? ? , then for any k dionly ?nitely many, say, ? u ? ????¨ ? ? g?????? ? ? , we have ??¨?k v visible by ? u ? ? ??¨ ¨v???&??? , that is, ??¨?k ? ??¨ ? is not divisible %?%?% ?p? , so must be ?F , but then ? takes some by ? uT value in?nitely many times, contradiction. In particular, we can choose some such ? not dividingQ ( , and choose ? divides ??¨vk . Then ??¨?k ??? v Q k such that ??¨?k ?T?p?3? ¨vk ¨v??????? (write out the Taylor series of the left side); in particular, since ? does Q not divide ?3? ¨vk , we can ?nd some ? such that ??¨vk ??? is dig visible by ? but not by ? , and so is not a perfect square. Third solution: (from David Rusin, David Savitt, and ? Q g Q k ? ? k Richard Stanley independently) Assume that QY? is a square for all k ?? . For suf?ciently large k ? k ,

¨?k ??àg Q àg g ? ? k u ? ? ? k ? ¨vk ? Q ??k g Q ? k Qh? gá

?àg Q

àg Q ? k u ? ?

? Q thusQ if k QS is a large even perfect square, we have k ? Q g ??àg àg g ?k k ?¨?k . We conclude this is an gu ??k u ? equality of polynomials, but the right-hand side is not a perfect square for k an even non-square, contradiction. (The reader might try generalizing this approach to arbitrary polynomials. AQ related due to Greg Q argument, Qh? Kuperberg: write ? k ? ??k g k as k ?àg times a ? power series in ? k and take two ?nite differences to

get an expression which tends to 0 as kh??? , contradiction.) Q?? ? Q g Q ??k k has no repeated facNote: in case k ? tors, it is a square for only ?nitely many k , by a theorem of Siegel; work of Baker gives an explicit (but large) bound on such k . (I don’t know whether the graders will accept this as a solution, though.)

3

The 60th William Lowell Putnam Mathematical Competition Saturday, December 4, 1999

A-1 Find polynomials ? such that for all ,

???¤??? ¤ ? ??? ,§ ,

and

¨

?¤???

, if they exist, if $#10 ? if ?&5 2 if .

$# ! ?????? ?¤??? ?¤??? " ' ? ) ( § ¨ 4( ? ) ( ?¤???

?&% $#

032

B-1 Right triangle ?4??r has right angle at r and ???? ??r ? ; the point ? is chosen on ? ? ? so that ? ? r ?4? d? # ; the point ? is chosen on ??r so that ??r1??? . ? ? r ? ? ? ? e The perpendicular to at meets at . Evalu ate fhghikjml b ?ne . B-2 Let qk?¤??o ?

A-2 Let 6 ? be a polynomial that is nonnegative for all real . Prove ?89?¤???A@BCBCBD@E?FG?¤? that for some 7 , there are polynomials ) such that

F H ?¤??? ? ? I ?¤???S?UTVB R 6 IP 8 Q #

distinct roots. B-3 Let ?

? ??? ?¤???p be ?¤?? ? a polynomial qk?¤??? of degree f such that o is a quadratic and ???o$ ? rsr , where ?¤??polynomial ? o$r ?¤r ??? is the second derivative of o . Show that if o has at least two distinct roots then it must have f utv??w@Swx??y 2z0 ?w@Qw{% #}| ?W??w@Qw~?? ?? ??? ?? T H

. For

??w@Qw~?W ?

, let

A-3 Consider the power series expansion

H #WX( ? ? T `Y a ? a B a Pcbed 2 Prove that, for each integer fhg , there is an integer i

such that

? q

w a @ ? @ ?

d

A-4 Sum the series

T a HY d

T 8 ap

dGq

B ?

where the sum ranges over all pairs i f of positive integers satisfying the indicated inequalities. Evaluate

???? ??? l ? 8 fhgh? i8 ???s???? ??????

? #? ??w T ??? #W ? T wx?S?W??w@Qw~??B

HY q

T B i f ? ' ' ' ? i a P 8 aP 8 q f q

A-5 Prove that there is a constant r such that, if 6 polynomial of degree 1999, then

?¤???

is a

A-6

8 ? 2 ? G0 ?¤??? Uv ?wB 6 rts 8 6 u ? a ? aGx 8 8y # @ T The is de?ned by ( @ sequence ? (?? @ d d and,d for f?g , dG? T 8 a X? a u 8 Ta T B a ?? d a u d u ? d u a u T a ud d d d ? Show that, for all n, a is an integer multiple of f . d

B-4 Let be a real with ???¤function ???A@m? ????A @m? ?a ??continuous ??@E? ???? third derivative? such that r s r r ? ?¤??? 0 ???¤??? rsr r are ? positive for r s r r . Suppose that for all . Show that all ( ? ?????% ?????? ? for all . r B-5 For an integer f?g , let f . Evaluate the determinant of the f??)f matrix ? ? ? ? F ,? where ? is I has entries the f??f identity matrix and ? d I F ??C?V?C?h?V? 7 ?v? for all ?V@ 7 .

'

?u

(????

d

B-6 Let be a ?nite set of integers, each greater than ?1. ? f ? Suppose that for each integer there is some # ?¤?? @ ?? ?C¤w? @ ?? such that ? @Q§? &f ? or ? ?¤?? ? @S f §S? ? . Show that there exist ? such that ? ? is prime.

?

Solutions to the 60th William Lowell Putnam Mathematical Competition Saturday, December 4, 1999

Manjul Bhargava, Kiran Kedlaya, and Lenny Ng

A–1 Note that if r(x) and s(x) are any two functions, then max(r, s) = (r + s + |r ? s|)/2. Therefore, if F (x) is the given function, we have F (x) = max{?3x ? 3, 0} ? max{5x, 0} + 3x + 2 = (?3x ? 3 + |3x + 3|)/2 ? (5x + |5x|)/2 + 3x + 2 1 = |(3x + 3)/2| ? |5x/2| ? x + , 2 so we may set f (x) = (3x + 3)/2, g (x) = 5x/2, and h(x) = ?x + 1 2. A–2 First solution: First factor p(x) = q (x)r(x), where q has all real roots and r has all complex roots. Notice that each root of q has even multiplicity, otherwise p would have a sign change at that root. Thus q (x) has a square root s(x). Now write r(x) = j =1 (x ? aj )(x ? aj ) (possible because r has roots in complex conjugate pairs). Write k j =1 (x ? aj ) = t(x) + iu(x) with t, x having real coef?cients. Then for x real,

k

a2 n , b2n+1 = an (an?1 + an+1 ). Then

2 2b2n+1 + b2n = 2an an+1 + 2an?1 an + a2 n?1 + an

= 2an an+1 + an?1 an+1 + a2 n

2 = a2 n+1 + an = b2n+2 ,

and similarly 2b2n + b2n?1 = b2n+1 , so that {bn } satis?es the same recurrence as {an }. Since further b0 = 1, b1 = 2 (where we use the recurrence for {an } to calculate a?1 = 0), we deduce that bn = an for all 2 n. In particular, a2 n + an+1 = b2n+2 = a2n+2 . Second solution: Note that 1 1 ? 2x ? x2

1 = √ 2 2

√ √ 2+1 2?1 √ √ + 1 ? (1 + 2)x 1 ? (1 ? 2)x

and that √ 1 √ = (1 ± 2)n xn , 1 + (1 ± 2)x n=0 so that

∞

p(x) = q (x)r(x) = s(x)2 (t(x) + iu(x))(t(x) + iu(x)) = (s(x)t(x)) + (s(x)u(x)) . (Alternatively, one can factor r(x) as a product of quadratic polynomials with real coef?cients, write each as a sum of squares, then multiply together to get a sum of many squares.) Second solution: We proceed by induction on the degree of p, with base case where p has degree 0. As in the ?rst solution, we may reduce to a smaller degree in case p has any real roots, so assume it has none. Then p(x) > 0 for all real x, and since p(x) → ∞ for x → ±∞, p has a minimum value c. Now p(x) ? c has real roots, so as above, we deduce that p(x) ? c is a√ sum of squares. Now add one more square, namely ( c)2 , to get p(x) as a sum of squares. A–3 First solution: Computing the coef?cient of xn+1 in the ∞ identity (1 ? 2x ? x2 ) m=0 am xm = 1 yields the recurrence an+1 = 2an + an?1 ; the sequence {an } is then characterized by this recurrence and the initial conditions a0 = 1, a1 = 2. De?ne the sequence {bn } by b2n = a2 n?1 +

2 2

√ √ 1 an = √ ( 2 + 1)n+1 ? (1 ? 2)n+1 . 2 2 A simple computation (omitted here) now shows that 2 a2 n + an+1 = a2n+2 . Third solution (by Richard Stanley): Let A be the ma0 1 . A simple induction argument shows that trix 1 2 An+2 = an an+1 . an+1 an+2

The desired result now follows from comparing the top left corner entries of the equality An+2 An+2 = A2n+4 . A–4 Denote the series by S , and let an = 3n /n. Note that

∞ ∞

S=

m=1 n=1 ∞ ∞

1 am (am + an ) 1 an (am + an ) ,

=

m=1 n=1

2 where the second equality follows by interchanging m and n. Thus 2S =

m n

largest positive real number such that R(x) ? kx ≥ 0 on [0, 1]; then

1 ?1 1

1 am (am + an ) 1 am an

2

+

1 an (am + an )

|P (x)| dx = >

?1 1 ?1

|Q(x)R(x)| dx |Q(x)(R(x) ? kx)| dx,

=

m ∞ n

= But

n n 3 n=1

.

3 n = n 3 4 n=1 since, e.g., it’s f (1), where f (x) = xn 3 = , n 3 3 ? x n=0

∞

∞

and Q(x)(R(x) ? kx) has more roots in [0, 1] than does P (and has the same value at 0). Repeating this argu1 ment shows that 0 |P (x)| dx is greater than the corresponding integral for some polynomial with all of its roots in [0, 1]. Under this assumption, we have

1999

P (x) = c

i=1

(x ? ri )

for some ri ∈ (0, 1]. Since P (0) = ?c we have |c| ≥

?1 |ri | ≥ 1.

ri = 1,

and we conclude that S = 9/32. A–5 First solution: (by Reid Barton) Let r1 , . . . , r1999 be the roots of P . Draw a disc of radius around each ri , where < 1/3998; this disc covers a subinterval of [?1/2, 1/2] of length at most 2 , and so of the 2000 (or fewer) uncovered intervals in [?1/2, 1/2], one, which we call I , has length at least δ = (1 ? 3998 )/2000 > 0. We will exhibit an explicit lower bound for the integral of |P (x)|/P (0) over this interval, which will yield such a bound for the entire integral. Note that |P (x)| = |P (0)|

1999 i=1

|x ? ri | . |ri |

Thus it suf?ces to prove that if Q(x) is a monic polynomial of degree 1999 with all of its roots in [0, 1], then 1 0 |Q(x)| dx ≥ D for some constant D > 0. But the 1 1999 integral of 0 i=1 |x ? ri | dx is a continuous function for ri ∈ [0, 1]. The product of all of these intervals is compact, so the integral achieves a minimum value for some ri . This minimum is the desired D. Third solution (by Abe Kunin): It suf?ces to prove the stronger inequality

1 x∈[?1,1]

Also note that by construction, |x ? ri | ≥ for each ri | x ∈ I . If |ri | ≤ 1, then we have |x|? ri | ≥ . If |ri | > 1, then |x ? ri | = |1 ? x/ri | ≥ 1 ? |x/ri | ≥= 1/2 > . |ri | We conclude that dent of P .

I

sup |P (x)| ≤ C

?1

|P (x)| dx

|P (x)/P (0)| dx ≥ δ , indepen-

Second solution: It will be a bit more convenient to assume P (0) = 1 (which we may achieve by rescaling unless P (0) = 0, in which case there is nothing to prove) and to prove that there exists D > 0 such that 1 1 |P (x)| dx ≥ D, or even such that 0 |P (x)| dx ≥ ?1 D. We ?rst reduce to the case where P has all of its roots in [0, 1]. If this is not the case, we can factor P (x) as Q(x)R(x), where Q has all roots in the interval and R has none. Then R is either always positive or always negative on [0, 1]; assume the former. Let k be the

holds for some C . But this follows immediately from the following standard fact: any two norms on a ?nitedimensional vector space (here the polynomials of degree at most 1999) are equivalent. (The proof of this statement is also a compactness argument: C can be taken to be the maximum of the L1-norm divided by the sup norm over the set of polynomials with L1-norm 1.) Note: combining the ?rst two approaches gives a constructive solution with a constant that is better than that given by the ?rst solution, but is still far from optimal. I don’t know offhand whether it is even known what the optimal constant and/or the polynomials achieving that constant are. A–6 Rearranging the given equation yields the much more tractable equation an?1 an?2 an =6 ?8 . an?1 an?2 an?3

3 Let bn = an /an?1 ; with the initial conditions b2 = 2, b3 = 12, one easily obtains bn = 2n?1 (2n?2 ? 1), and so

n?1

and if z has negative real part, so does 1/(z ? ri ) for i = 1, . . . , n, so the sum is nonzero. The above argument also carries through if z lies on the imaginary axis, provided that z is not equal to a root of P . Thus we also have that no roots of P lie on the sides of the convex hull of P , unless they are also roots of P . From this we conclude that if r is a root of P which is a vertex of the convex hull of the roots, and which is not also a root of P , then f has a single pole at r (as r cannot be a root of P ). On the other hand, if r is a root of P which is also a root of P , it is a multiple root, and then f has a double pole at r. If P has roots not all equal, the convex hull of its roots has at least two vertices. B–3 We ?rst note that xm y n =

m,n>0

an = 2n(n?1)/2

i=1

(2i ? 1).

B–1 The answer is 1/3. Let G be the point obtained by reθ ?ecting C about the line AB . Since ∠ADC = π? 2 , π ?θ we ?nd that ∠BDE = π ? θ ? ∠ADC = 2 = ∠ADC = π ? ∠BDC = π ? ∠BDG, so that E, D, G are collinear. Hence |BE | sin(θ/2) |BE | = = , |EF | = |BC | |BG| sin(3θ/2)

To see that n divides an , factor n as 2k m, with m odd. Then note that k ≤ n ≤ n(n ? 1)/2, and that there exists i ≤ m ? 1 such that m divides 2i ? 1, namely i = φ(m) (Euler’s totient function: the number of integers in {1, . . . , m} relatively prime to m).

xy . (1 ? x)(1 ? y )

where we have used the law of sines in l’H? opital’s Rule, lim

BDG. But by

Subtracting S from this gives two sums, one of which is xm y n =

m≥2n+1 n

sin(θ/2) cos(θ/2) = lim = 1/3. θ →0 sin(3θ/2) θ →0 3 cos(3θ/2) B–2 First solution: Suppose that P does not have n distinct roots; then it has a root of multiplicity at least 2, which we may assume is x = 0 without loss of generality. Let xk be the greatest power of x dividing P (x), so that P (x) = xk R(x) with R(0) = 0; a simple computation yields P (x) = (k 2 ? k )xk?2 R(x) + 2kxk?1 R (x) + xk R (x). Since R(0) = 0 and k ≥ 2, we conclude that the greatest power of x dividing P (x) is xk?2 . But P (x) = Q(x)P (x), and so x2 divides Q(x). We deduce (since Q is quadratic) that Q(x) is a constant C times x2 ; in fact, C = 1/(n(n ? 1)) by inspection of the leadingdegree terms of P (x) and P (x). Now if P (x) = j =0 aj xj , then the relation P (x) = Cx2 P (x) implies that aj = Cj (j ? 1)aj for all j ; hence aj = 0 for j ≤ n ? 1, and we conclude that P (x) = an xn , which has all identical roots.

n

yn

x3 y x2n+1 = 1?x (1 ? x)(1 ? x2 y )

and the other of which sums to xy 3 /[(1 ? y )(1 ? xy 2)]. Therefore S (x, y ) = x3 y xy 3 xy ? ? 2 (1 ? x)(1 ? y ) (1 ? x)(1 ? x y ) (1 ? y )(1 ? xy 2 ) xy (1 + x + y + xy ? x2 y 2 ) = (1 ? x2 y )(1 ? xy 2 )

and the desired limit is lim(x,y)→(1,1) xy (1 + x + y + xy ? x2 y 2 ) = 3. B–4 (based on work by Daniel Stronger) We make repeated use of the following fact: if f is a differentiable function on all of R, limx→?∞ f (x) ≥ 0, and f (x) > 0 for all x ∈ R, then f (x) > 0 for all x ∈ R. (Proof: if f (y ) < 0 for some x, then f (x) < f (y ) for all x < y since f > 0, but then limx→?∞ f (x) ≤ f (y ) < 0.) From the inequality f (x) ≤ f (x) we obtain f f (x) ≤ f (x)f (x) < f (x)f (x) + f (x)2 since f (x) is positive. Applying the fact to the difference between the right and left sides, we get 1 (f (x))2 < f (x)f (x). 2 (1)

Second solution (by Greg Kuperberg): Let f (x) = P (x)/P (x) = 1/Q(x). By hypothesis, f has at most two poles (counting multiplicity). Recall that for any complex polynomial P , the roots of P lie within the convex hull of P . To show this, it suf?ces to show that if the roots of P lie on one side of a line, say on the positive side of the imaginary axis, then P has no roots on the other side. That follows because if r1 , . . . , rn are the roots of P , P (z ) = P (z )

n i=1

1 z ? ri

On the other hand, since f (x) and f (x) are both positive for all x, we have 2f (x)f (x) < 2f (x)f (x) + 2f (x)f (x).

4 Applying the fact to the difference between the sides yields f (x)2 ≤ 2f (x)f (x). Combining (1) and (2), we obtain 1 2 f (x)2 2f (x)

2

(2)

1 (f (x))2 2 < f (x)f (x), <

Since k=1 eik θ = 0 for integer unless n | , we conclude that Av (m) = 0 for m = 0 or for 2 ≤ m ≤ ?ijθ n ? 1. In addition, we ?nd that (Av (1) )j = n = 2e n n n (n?1) (n?1) ijθ (1) ( v ) and ( Av ) = e = ( v ) j j j, 2 2 2 (1) (n?1) so that A(v (1) ± v (n?1) ) = ± n ( v ± v ). 2 (0) (2) (3) (n?2) (1) (n?1) (1) Thus {v , v , v , . . . , v ,v +v ,v ? v (n?1) } is a basis for Cn of eigenvectors of A with the claimed eigenvalues.

n

or (f (x))3 < f (x)3 . We conclude f (x) < 2f (x), as desired. Note: one can actually prove the result with a smaller constant in place of 2, as follows. Adding 1 2 f (x)f (x) to both sides of (1) and again invoking the original bound f (x) ≤ f (x), we get 1 1 [f (x)f (x) + (f (x))2 ] < f (x)f (x) + f (x)f (x) 2 2 3 ≤ f (x)f (x). 2 Applying the fact again, we get 1 3 f (x)f (x) < f (x)2 . 2 4 Multiplying both sides by f (x) and applying the fact once more, we get 1 1 (f (x))3 < f (x)3 . 6 4 From this we deduce f (x) < (3/2)1/3 f (x) < 2f (x), as desired. I don’t know what the best constant is, except that it is not less than 1 (because f (x) = ex satis?es the given conditions). B–5 We claim that the eigenvalues of A are 0 with multiplicity n ? 2, and n/2 and ?n/2, each with multiplicity 1. To prove this claim, de?ne vectors v (m) , 0 ≤ m ≤ n ? 1, componentwise by (v (m) )k = eikmθ , and note that the v (m) form a basis for Cn . (If we arrange the v (m) into an n × n matrix, then the determinant of this matrix is a Vandermonde product which is nonzero.) Now note that

n

Finally, the determinant of I +A is the product of (1+λ) over all eigenvalues λ of A; in this case, det(I + A) = (1 + n/2)(1 ? n/2) = 1 ? n2 /4.

B–6 First solution: Choose a sequence p1 , p2 , . . . of primes as follows. Let p1 be any prime dividing an element of S . To de?ne pj +1 given p1 , . . . , pj , choose an integer Nj ∈ S relatively prime to p1 · · · pj and let pj +1 be a prime divisor of Nj , or stop if no such Nj exists. Since S is ?nite, the above algorithm eventually terminates in a ?nite sequence p1 , . . . , pk . Let m be the smallest integer such that p1 · · · pm has a divisor in S . (By the assumption on S with n = p1 · · · pk , m = k has this property, so m is well-de?ned.) If m = 1, then p1 ∈ S , and we are done, so assume m ≥ 2. Any divisor d of p1 · · · pm in S must be a multiple of pm , or else it would also be a divisor of p1 · · · pm?1 , contradicting the choice of m. But now gcd(d, Nm?1 ) = pm , as desired. Second solution (from sci.math): Let n be the smallest integer such that gcd(s, n) > 1 for all s in n; note that n obviously has no repeated prime factors. By the condition on S , there exists s ∈ S which divides n. On the other hand, if p is a prime divisor of s, then by the choice of n, n/p is relatively prime to some element t of S . Since n cannot be relatively prime to t, t is divisible by p, but not by any other prime divisor of n (as those primes divide n/p). Thus gcd(s, t) = p, as desired.

(Av (m) )j =

k=1

cos(jθ + kθ)eikmθ eijθ 2

n

=

eik(m+1)θ +

k=1

e?ijθ 2

n

eik(m?1)θ .

k=1

The 61st William Lowell Putnam Mathematical Competition Saturday, December 2, 2000

A-1 Let A be a positive real number. What are the possible ∞ values of j =0 x2 j , given that x0 , x1 , . . . are positive ∞ numbers for which j =0 xj = A? A-2 Prove that there exist in?nitely many integers n such that n, n + 1, n + 2 are each the sum of the squares of two integers. [Example: 0 = 02 + 02 , 1 = 02 + 12 , 2 = 12 + 12 .] A-3 The octagon P1 P2 P3 P4 P5 P6 P7 P8 is inscribed in a circle, with the vertices around the circumference in the given order. Given that the polygon P1 P3 P5 P7 is a square of area 5, and the polygon P2 P4 P6 P8 is a rectangle of area 4, ?nd the maximum possible area of the octagon. A-4 Show that the improper integral

B B →∞

exist integers r, s, t such that raj + sbj + tcj is odd for at least 4N/7 values of j , 1 ≤ j ≤ N . B-2 Prove that the expression gcd(m, n) n n m is an integer for all pairs of integers n ≥ m ≥ 1. B-3 Let f (t) = j =1 aj sin(2πjt), where each aj is real and aN is not equal to 0. Let Nk denote the number of k f zeroes (including multiplicities) of d . Prove that dtk N0 ≤ N1 ≤ N2 ≤ · · · and lim Nk = 2N.

k→∞ N

lim

sin(x) sin(x2 ) dx

0

[Editorial clari?cation: only zeroes in [0, 1) should be counted.] B-4 Let f (x) be a continuous function such that f (2x2 ? 1) = 2xf (x) for all x. Show that f (x) = 0 for ?1 ≤ x ≤ 1. B-5 Let S0 be a ?nite set of positive integers. We de?ne ?nite sets S1 , S2 , . . . of positive integers as follows: the integer a is in Sn+1 if and only if exactly one of a ? 1 or a is in Sn . Show that there exist in?nitely many integers N for which SN = S0 ∪ {N + a : a ∈ S0 }. B-6 Let B be a set of more than 2n+1 /n distinct points with coordinates of the form (±1, ±1, . . . , ±1) in ndimensional space with n ≥ 3. Show that there are three distinct points in B which are the vertices of an equilateral triangle.

converges. A-5 Three distinct points with integer coordinates lie in the plane on a circle of radius r > 0. Show that two of these points are separated by a distance of at least r1/3 . A-6 Let f (x) be a polynomial with integer coef?cients. De?ne a sequence a0 , a1 , . . . of integers such that a0 = 0 and an+1 = f (an ) for all n ≥ 0. Prove that if there exists a positive integer m for which am = 0 then either a1 = 0 or a2 = 0. B-1 Let aj , bj , cj be integers for 1 ≤ j ≤ N . Assume for each j , at least one of aj , bj , cj is odd. Show that there

Solutions to the 61st William Lowell Putnam Mathematical Competition Saturday, December 2, 2000

Manjul Bhargava, Kiran Kedlaya, and Lenny Ng

A–1 The possible values comprise the interval (0, A2 ). To see that the values must lie in this interval, note that ? ?

j =0 m

?2 xj ? =

m

x2 j +

j =0 0≤j<k≤m

2xj xk ,

We deduce from the area of P1 P3 P5 P7 that the radius of the circle is 5/2. An easy calculation using the Pythagorean Theorem shows that the rectangle √ then√ P2 P4 P6 P8 has sides 2 and 2 2. For notational ease, denote the area of a polygon by putting brackets around the name of the polygon. By symmetry, the area of the octagon can be expressed as [P2 P4 P6 P8 ] + 2[P2 P3 P4 ] + 2[P4 P5 P6 ]. √ Note that [P2 P3 P4 ] is 2 times the distance from P3 to P2 P4 , which is maximized when P3 lies √ on the midpoint of arc P2 P4 ; similarly, [P4 P5 P6 ] is 2/2 times the distance from P5 to P4 P6 , which is maximized when P5 lies on the midpoint of arc P4 P6 . Thus the area of the octagon is maximized when P3 is the midpoint of arc P2 P4 and P5 is the midpoint of arc P4 P6 . In √ 5?1 this case, it is easy to calculate that [ P P P ] = 2 3 4 √ and [P4 P5 P ] = 5 / 2 ? 1 , and so the area of the oc√6 tagon is 3 5. A–4 We use integration by parts:

B B

so

m 2 j =0 xj ∞ 2 j =0 xj ≤

≤ A2 ? 2x0 x1 . Letting m → ∞, we have A2 ? 2x0 x1 < A2 .

To show that all values in (0, A2 ) can be obtained, we use geometric progressions with x1 /x0 = x2 /x1 = ∞ · · · = d for variable d. Then j =0 xj = x0 /(1 ? d) and ? ?2 ∞ ∞ 2 x0 1?d? x2 = xj ? . j = 2 1 ? d 1 + d j =0 j =0 As d increases from 0 to 1, (1 ? d)/(1 + d) decreases from 1 to 0. Thus if we take geometric progressions ∞ ∞ 2 with j =0 xj = A, j =0 x2 j ranges from 0 to A . Thus the possible values are indeed those in the interval (0, A2 ), as claimed. A–2 First solution: Let a be an even integer such that a + 1 is not prime. (For example, choose a ≡ 2 (mod 5), so that a2 + 1 is divisible by 5.) Then we can write a2 + 1 as a difference of squares x2 ? b2 , by factoring a2 + 1 as rs with r ≥ s > 1, and setting x = (r + s)/2, b = (r ? s)/2. Finally, put n = x2 ? 1, so that n = a2 + b2 , n + 1 = x2 , n + 2 = x2 + 1.

2

sin x sin x2 dx =

0 0

sin x sin x2 (2x dx) 2x

B 0

=? +

0

sin x cos x2 2x

B

Second solution: It is well-known that the equation x2 ? 2y 2 = 1 has in?nitely many solutions (the socalled “Pell” equation). Thus setting n = 2y 2 (so that n = y 2 + y 2 , n + 1 = x2 + 02 , n + 2 = x2 + 12 ) yields in?nitely many n with the desired property. Third solution: As in the ?rst solution, it suf?ces to exhibit x such that n x2 ? 1 is the sum of two squares. We 2 will take x = 3 , and show that x2 n ? 1 is the sum of two squares by induction on n: if 32 ? 1 = a2 + b2 , then (32

n+1

cos x sin x ? 2x 2x2

cos x2 dx.

x 2 Now sin 2x cos x tends to 0 as B → ∞, and the integral sin x 2 of 2x2 cos x converges absolutely by comparison with 1/x2 . Thus it suf?ces to note that B 0

? 1) = (32 ? 1)(32 + 1) = (32

n?1

n

n

a + b)2 + (a ? 32

n?1

b)2 .

cos x cos x cos x2 dx = cos x2 (2x dx) 2x 4x2 B cos x = sin x2 2 4x 0 B 2x cos x ? sin x ? sin x2 dx, 4x3 0

√ A–3 The maximum area is 3 5.

and that the ?nal integral converges absolutely by comparison to 1/x3 .

An alternate approach is to ?rst rewrite sin x sin x2 as 1 2 2 2 (cos(x ? x) ? cos(x + x). Then

B

cos(x2 + x) dx = ?

0

2x + 1 sin(x2 + x)

B

B 0

?

0

2 sin(x2 + x) dx (2x + 1)2

. Recall Rolle’s theorem: if f (t) is difB–3 Put fk (t) = df dtk ferentiable, then between any two zeroes of f (t) there exists a zero of f (t). This also applies when the zeroes are not all distinct: if f has a zero of multiplicity m at t = x, then f has a zero of multiplicity at least m ? 1 there. Therefore, if 0 ≤ a0 ≤ a1 ≤ · · · ≤ ar < 1 are the roots of fk in [0, 1), then fk+1 has a root in each of the intervals (a0 , a1 ), (a1 , a2 ), . . . , (ar?1 , ar ), so long as we adopt the convention that the empty interval (t, t) actually contains the point t itself. There is also a root in the “wraparound” interval (ar , a0 ). Thus Nk+1 ≥ Nk . Next, note that if we set z = e2πit ; then f4k (t) = 1 2i

N

k

converges absolutely, and similarly.

B 0

cos(x2 ? x) can be treated

A–5 Let a, b, c be the distances between the points. Then the area of the triangle with the three points as vertices is abc/4r. On the other hand, the area of a triangle whose vertices have integer coordinates is at least 1/2 (for example, by Pick’s Theorem). Thus abc/4r ≥ 1/2, and so max{a, b, c} ≥ (abc)1/3 ≥ (2r)1/3 > r1/3 . A–6 Recall that if f (x) is a polynomial with integer coef?cients, then m ? n divides f (m) ? f (n) for any integers m and n. In particular, if we put bn = an+1 ? an , then bn divides bn+1 for all n. On the other hand, we are given that a0 = am = 0, which implies that a1 = am+1 and so b0 = bm . If b0 = 0, then a0 = a1 = · · · = am and we are done. Otherwise, |b0 | = |b1 | = |b2 | = · · · , so bn = ±b0 for all n. Now b0 + · · · + bm?1 = am ? a0 = 0, so half of the integers b0 , . . . , bm?1 are positive and half are negative. In particular, there exists an integer 0 < k < m such that bk?1 = ?bk , which is to say, ak?1 = ak+1 . From this it follows that an = an+2 for all n ≥ k ? 1; in particular, for m = n, we have a0 = am = am+2 = f (f (a0 )) = a2 . B–1 Consider the seven triples (a, b, c) with a, b, c ∈ {0, 1} not all zero. Notice that if rj , sj , tj are not all even, then four of the sums arj + bsj + ctj with a, b, c ∈ {0, 1} are even and four are odd. Of course the sum with a = b = c = 0 is even, so at least four of the seven triples with a, b, c not all zero yield an odd sum. In other words, at least 4N of the tuples (a, b, c, j ) yield odd sums. By the pigeonhole principle, there is a triple (a, b, c) for which at least 4N/7 of the sums are odd. B–2 Since gcd(m, n) is an integer linear combination of m and n, it follows that gcd(m, n) n n m is an integer linear combination of the integers m n n m = n?1 n n and m?1 n m = n m

j 4k aj (z j ? z ?j )

j =1

is equal to z ?N times a polynomial of degree 2N . Hence as a function of z , it has at most 2N roots; therefore fk (t) has at most 2N roots in [0, 1]. That is, Nk ≤ 2N for all N . To establish that Nk → 2N , we make precise the observation that

N

fk (t) =

j =1

j 4k aj sin(2πjt)

is dominated by the term with j = N . At the points t = (2i + 1)/(2N ) for i = 0, 1, . . . , N ? 1, we have N 4k aN sin(2πN t) = ±N 4k aN . If k is chosen large enough so that |aN |N 4k > |a1 |14k + · · · + |aN ?1 |(N ? 1)4k , then fk ((2i + 1)/2N ) has the same sign as aN sin(2πN at), which is to say, the sequence fk (1/2N ), fk (3/2N ), . . . alternates in sign. Thus between these points (again including the “wraparound” interval) we ?nd 2N sign changes of fk . Therefore limk→∞ Nk = 2N .

t) B–4 For t real and not a multiple of π , write g (t) = f (cos sin t . Then g (t + π ) = g (t); furthermore, the given equation implies that

g (2t) =

f (2 cos2 t ? 1) 2(cos t)f (cos t) = = g (t). sin(2t) sin(2t)

In particular, for any integer n and k , we have g (1 + nπ/2k ) = g (2k + nπ ) = g (2k ) = g (1). Since f is continuous, g is continuous where it is de?ned; but the set {1 + nπ/2k |n, k ∈ Z} is dense in the reals, and so g must be constant on its domain. Since g (?t) = ?g (t) for all t, we must have g (t) = 0 when t is not a multiple of π . Hence f (x) = 0 for x ∈ (?1, 1). Finally, setting x = 0 and x = 1 in the given equation yields f (?1) = f (1) = 0. 2

and hence is itself an integer.

B–5 We claim that all integers N of the form 2k , with k a positive integer and N > max{S0 }, satisfy the desired conditions. It follows from the de?nition of Sn , and induction on n, that xj ≡ (1 + x)

j ∈Sn j ∈Sn?1

max{S0 }, then ≡ (1 + xN )

j ∈Sn j ∈S0

xj

and SN = S0 ∪ {N + a : a ∈ S0 }, as desired. B–6 For each point P in B , let SP be the set of points with all coordinates equal to ±1 which differ from P in exactly one coordinate. Since there are more than 2n+1 /n points in B , and each SP has n elements, the cardinalities of the sets SP add up to more than 2n+1 , which is to say, more than twice the total number of points. By the pigeonhole principle, there must be a point in three of the sets, say SP , SQ , SR . But then any two of P, Q, R differ in exactly two coordinates, so P QR is an equilateral triangle, as desired.

xj xj

j ∈S0

≡ (1 + x)

n

(mod 2).

2 From the identity (x + y )2 ≡ x + y 2n (mod 2) and inn 2n duction on n, we have (x + y ) ≡ x2 + y 2 (mod 2). Hence if we choose N to be a power of 2 greater than

3

The 62nd William Lowell Putnam Mathematical Competition Saturday, December 1, 2001

A-2 You have coins "$# ? "&% ?(')'('?? "10 . For each 2 , "13 is biased so that, when tossed, it has probability 4(56?8792@A4 of fallings heads. If the B coins are tossed, what is the probability that the number of heads is odd? Express the answers as a rational function of B .

A-1 Consider a set and a binary operation ? , i.e., for each ?¤???¨§ ? , ? ? ?¨§ ? . Assume ? ? ? ? ? ?? for all ? ?¤???§ . Prove that ? ?? ? ? ?? for all ? ?!?§ ? .

?

B-2 Find all pairs of real numbers ?TG ???i satisfying the system of equations

4 ? G % @?? ? T 7 ? 4 4 P ? 76? ? I P?G G 7 G @

4

% ?8?iG % @ ? % I ?'

A-3 For each integer C , consider the polynomial

A-5 Prove that there are unique positive integers ? , B such 0fV# PA? ? @g4 0 7ih9hp4 . that ? A-6 Can an arc of a parabola inside a circle of radius 1 have a length greater than 4?

A-4 Triangle W$XY" has an area 1. Points ` ??a&??b lie, respecX a tively, on sides XY" , "cW , WcX such that ? Wc` bisects a b b at point d , X bisects " at point , and " ? bisects W$` at point e . Find the area of the triangle d e .

constant polynomials with integer coef?cients?

?8G H G6I&PA?879CQ@SR G % @?TCUPS7 % ' DVE ?8G the product of two nonFor what values of C is

DFE

B-3 For any positive integer B , let ??B?? denote the closest integer to ? B . Evaluate

7i? 0? @w7??? 0?? ' 7 0 0??V# ?

B-4 Let ? denote the set of rational different from ? gi? numbers ? h PY4 ? h ? 4d? . De?ne eUf by eF?TG GjPQ4(59G .

?

?

Prove or disprove that

k

?

0?V#

? Ap6? eml 0?n ? o

B-1 Let B be an even positive integer. Write the numbers 4 ? 7 ?)'(')'q? B % in the squares of an BsrtB grid so that the 2 -th row, from left to right, is

where e l 0n denotes e composed with itself B times. B-5 Let ? and ? be real numbers in the interval ?Th ? 4(5i7 , and let q be a continuous real-valued function such that q??rqs?TG ytu? qs?TG @ ? G for all real G . Prove that qs?TG gv G for some constant v . B-6 Assume that ? ? 0 06wF# is an increasing sequence of positive real numbers such that xryrz ? 0p59B h . Must there exist in?nitely many positive integers B such that ? 0 @ ? 0?f 7 ? 0 for } 4 ? 7 ?(')')'q? BuPA4 ?

?T2uPv4 ?8B @A4 ? ?T2YPw4 Bx@w7 ?)')'('y? ?T2YPw4 B?@SB '

Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility). Prove that for each coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

? {

{|

Solutions to the 62nd William Lowell Putnam Mathematical Competition Saturday, December 1, 2001

Manjul Bhargava, Kiran Kedlaya, and Lenny Ng

A–1 The hypothesis implies ? !?#"%$ ? ?&¤'? for all (by replacing by ??1¤0?? ),¨5and hence ?¤(???)¤0??¨12? ? !?3"4$ ¤0?67 ? for all (using ). A–2 Let 859 denote A the desired probability. Then and, for G#H ,

8 9 PI PI Q G Q GSR Q G Q GSR YaA A?T 8 9VUW@ R A?T 8 9VUW@ R I A Q ? G R A Q S G R Cgf Acb iEFCFp AXT ??A`Y 80@ BADCFE

??????¤§??¨¤?¨¤??¤??¨?

,

8 9VUW@

¨

Note: a more sophisticated interpretation of this argument can be given using Galois theory. Namely, if ? is neither a square nor twice a square, then the number lm? ? ¨ lm? ¨ d Q are distinct quadratic ?elds, ?elds and d so their compositum is a number ?eld of degree 4, f whose Galois group acts transitively on ? d ?a? d Q?i . Thus 8 ? is irreducible. A–4 Choose so that q?r n nws?r r s p r?s , and let w xy?z6{ denote the area of triangle u u|t Then w sq&{ x?yz . w q&{ since the triangles have the same altitude and base. t Also u }? C ¨ u PA&Y w s?q|{ sq s?r w s?r|{ n , and w~q?r { ? C ¨? t`C u|¨ u ??A&Yo?¨ (e.g., by the qr s?r r r w s?r&{ n law of sines). Adding this all up yields

A` u t t s?q&{XRaw s {kRaw~q?r { ??A6Y ¨ ??A6Y?oD¨) Y Y Q Q n R?n n w n R?n u o ¨1?A !og?p !tu2eo u?!v

Q The recurrence yields 8ed , 85h , and by a simple induction, one then checks that for general G one CX? AD¨ Q GSR has 8 9 G . Note: Richard Stanley points out the following nonin??r ¨1ts 9uwv ??r ¨?CX? AD¨ QFx R ductive argument. Put q r?y ; R QFx @ ?r?¨ then the coef?cient of in q is the probability of getting exactly ? heads. Thus the desired number is ? ??AD¨?Y ??Y?AD¨?¨?C Q , and both values of q can be comq q ??AD¨1?A puted directly: q , and q ??Y?AD¨6 A E E?? f????D???g? Q G Q GSR YA A A Q GSR A b r d

A–3 By the quadratic formula, if 8?? , then ??? Qgd Q ? Q , and hence the four roots of 8 ? are R $egf ? ?h? d Q?i given by . If 85? factors into two d nonconstant polynomials over the integers, then some $ subset of consisting of one or two elements form the roots of a polynomial with integer coef?cients. First suppose this subset has a single element, say ?j? d Q ; this element must be a rational number. d ? ¨ Q R ?i? Qgd Q ? Then d ?h? d Q d is an integer, d ? Q G . But then so ? is twice a perfect square, say ? A ?? d Q ?? ? AD¨ d Q G is only rational if G , i.e., d Q . if ? Next, suppose that the subset contains two elements; f f then we can take it to be one of d ?B? d Qki , d Q ? f ? ¨ ? i or ? d ? R d Q i . In all cases, the sum and the d product of the elements of the subset must be a ratio"?l , nal number. In the ?rst case, this means Q d ? ? so is a perfect square. In the second case, we have "%l Q d Q , ¨ contradiction. In the third case, ? ? "7l we have d "el R d Q , or ? R Q R Qgd Q ? , which d means that ? is twice a perfect square. ??r ¨ We conclude that 8 ? factors into two nonconstant polynomials over the integers if and only if ? is either a square or twice a square.

?r?¨???

? !?¨?? V ?X??¨ given by Let q? ?? w CX??A w ??r ¨? ? A? r?¨ ? be ? the ? ¨?¨?function ¨m q R q q q n n . However, ; then ??r ¨ r ? ?r?¨?¨ is strictly decreasing in , so q q is increasq ? ? ??r ¨?¨?¨ ing and is decreasing. Thus there is at most q q q r ? ? ??r ¨?¨?¨(2r one such that q q q ; in fact, since the equa???g¨12? ????Y'A fF¨?C Q , we tion q has a positive root R d 2o(p)?? must have n . u t ???u|t`Cu ¨ u ?? We now compute , w s { r w s?r&{ u ? C t?¨ u t ?FC Q , analogously w s??3{ s?? s w s { $ u(? ??FC $W? ?? u Y Q , and w~? w~s?r { w~r { { w s?r&{ u Y $ Y u&? ??B??A1Y?EF?gC ?Di? U h?? ? ? Q . w s??3{ w~s?r { w~r { ??A o?¨??A Note: the key relation n can also be deR

or n

??A R

oD¨1?A

. Similarly

og??A R

p!¨1pD??A

.

rived by computing using homogeneous coordinates or vectors.

? 9??5@

A–5 Suppose ? ???

tiple of 3 and the other is not, so their difference cannot ? 9??5@ ??A????????EF¨ be divisible by 3. Now , so we must ??? A?¨ 9 ??A?????????EF¨ have R , which forces G to be even, and in particular at least 2. If is even, then Since G is even,

?

YP??? A?¨ 9 ?F?VA Q that R ? A ¨ ? Y A ? . Notice ? 9??5@ 9 Raw R { is a multiple of ; thus divides ?g? p AgA A E ? Q Q Q ? ? ? . ?g?XA ?h??A Q Since is divisible by? 3, we must have ????????EF¨ ??? A ¨ 9 D 9??5@ , otherwise one of and R is a mul-

? 9??5@ Y???? AD¨ 9 ??Y???? AD¨ 9 ??????????¨ . R R Y???? AD¨ 9 ??Y?A???????????¨ R . Since

,ADthis is impossible. Thus is odd, ?g?XAmPp AFA A?E ? ? and so must divide . Moreover, ? 9??5@ Y??? AD¨ 9 ?2???????????¨ ????A¤??????????¨ , so . R

Q ? Of the divisors of ? , those congruent to 1 mod 3 are precisely those not divisible by 11 (since 7p and A? 13 ? E ? are both congruent to . ??? A??????????? ¨ 1 mod 3). Thus divides ? ADE Now is only possible if divides . p AgA ADE

?F?VA??iA¤??????????¨

?

every row contains exactly elements of s , ?

G q ??o?¨0

C Q ?

elements of

? ??o?¨ q b

and

G

C Q

?????

???w?

We cannot have , since for any G . Thus the only possibility is . One eas?a?ADEV Q is a solution; all that G ily checks that G A? remains is to check that no ?g other works. In A?E 9??5 ?XA??? ?????????F ¨ fact, @ ? Q , then Q G¨H . But if ADE 9??5@ ??A?E?????????g¨ G is even, contradiction. since ?SeA?EX Q is the unique solution. Thus G Note: once one has that ?F? ?? AY%?? to rule out cases.

Q Q 9??5@ R R G

?¤jA

A&Y

?F?VA 92 ? Q Q ?B§A?E

Similarly, because every column contains exactly C Q G elements of ? and elements of s , ? ?

G ? ??o?¨0 ???w? ? ?oD¨ R A( ???w? q ??o?¨ G?R?? ??o?¨ R ? ??o?¨ b

C Q

???w? ? It follows that q ??o?¨ G§R??

is even, one can use that AD¨ 9 ? A is divisible by R

AF

???w?

A–6 The answer is yes. Consider the arc of the parabola r d ? ? Y7AD¨ d jA ? ?u|r d inside the circle R , where u A?C Q . This intersects the we initially assume that H uYaA?C?u?D? u?Y ???X??F¨ ? ? Q d Q circle in three points, and AD¨?Cu|¨ u . We claim that for suf?ciently ?large, the ?X??F¨ ? length of the parabolic arc between and ? uYADCuS?? u¤Y?AD¨?Cu|¨ Q d Q is greater than Q , which implies the desired result by symmetry. We express ? using the usual formula for arclength:

? Q ?? ? A u ? ? A Q R Q u·? ? ? ? d?° U5@?± ° A ? d ? d?° U5@ A ? R ? ? R ? Q u|r ¨ dc? r r d ? r A R r d Y?r?¨ ? rY Y3r

as desired. Note: Richard Stanley points out a theorem of Ryser (see Ryser, Combinatorial Mathematics , Theorem 3.1) u ?&YaA that can also be applied. Namely, if and s are matrices with the same row and column sums, then there is a sequence of operations on Q ? Q matrices of the form

I ?hA A7? T ? I A2? ??A T u

d ? d?° UW@

Q??

or vice versa, which transforms into s . If we identify 0 and 1 with red and black, then the given coloring and the checkerboard coloring both satisfy the sum condition. Since the desired result is clearly true for the checkerboard coloring, and performing the matrix operations does not affect this, the desired result follows in general. B–2 By adding and subtracting the two given equations, we obtain the equivalent pair of equations

Q CFr?7r ? ADC ? 7fgr ? R R r A??Fr d ? d AD?gr d ? d R R f ? ? ? ? b

where we have arti?cially introduced r??a? grand in the last step. Now, for ,

A ? R r d Y3r? d A ?? ?? R A R A r d R r AD¨?¨ H Q d A

into the inte? Q A ??r R AD¨??

A R r d

since

u ?? ?? ??H ? d

C ? ? ? r ? r X Q R r d Y?r ¨ ? r ? ? d ? d?° U5@ ? d

diverges, so does . Hence, for suf?ciently large

A R r d Yr ¨ ? r H Q

, we have Q .

, and hence

Note: a numerical computation shows that one must u Ew? p b to obtain ?H Q , and that the maximum take H ? ?g? p u7?7??? A b . value of ? is about b Q , achieved for B–1 Let ? (resp. s ) denote the set of red (resp. black) o2" squares in such a coloring, and for ???s , let ?oD¨ ??o?¨ A o q G0R? R denote the number written in square , ??? ?oD¨ ??o?¨&? YA where . Then it is clear that the q ? G ?oD¨ o value of q ?oD¨ depends only on the row of , while the o value of ? depends only on the column of . Since 2

Multiplying the former by and the latter by ? , then adding and subtracting the two resulting equations, we obtain another pair of equations equivalent to the given ones,

E|???r R ? ¨ ? AD¨?C A(???r?Y ? ¨ ? b ??E @?± YaAD¨?C Q

? ? Q and ? It follows that R is the unique solution satisfying the given equations.

r???E @?±

B–3 Since

x d R x

? x

R

Y7ADC ¨ d Q A?Cw?

x

d Y x

, we have that

R

A?Cw? ??Gc?

and

x

? x

if and only if

R

ADC Q

¨ d

x? ? 9 v

d Y

x R Qg? 9?? R

A&? G U Q ?

? x 9??

d

R?

x

. Hence ?

Qg? 9?? R u Q R ?5@ u U Q 9 u ? U Q ? Q U Q 9 Q U ? 9??

@

Q 9

? u v ? v u 9 ? 9? ? @ X ?? ?? u ? u ? ? u?v v u ? u ? @ 9 U u ? ? Q R Q u?v ? @ ug??u ? U ? U Q u?v ? @ uF??u ? U U Q u?v @ ?E b

u

injective. Since ? is also continuous, ? is either strictly increasing or strictly decreasing. Moreover, ? cannot r#? ? tend to a ?nite limit , or else we’d have ? as R ? ?r?¨?¨1Y? ??r ¨`B??r , with the left side bounded and ? ? ? the right side unbounded. Similarly, ? cannot tend to a r???Y(? ?nite limit as . Together with monotonicity, this yields that ? is also surjective.

Y Q U u ? U u ¨ 9 for all G Pick ? arbitrary, and?rde?ne recurr ¨ ? r ? 9 sively by 9??5@ for G?H , and 9XUW@ ? r ¨ ? ? ? ? ? ? ? ? ? ? ? ¨ C U5@ d Q ? 9 R d R for Gjà . Let n?@ ????4Y ? d ????¨?C d Q and n d be the roots of n d R and r d Y???r?Ye???? A ? , so that n @ H H Há ? ? ? ? "gnD ? d and nw@ H n d . Then there exist ??@ ? d such that r "?? 9 9 9 . ? @ n @ R??dDn d for all G r r "e?

¨?

u

d?? Y ? d!? Y Q

U

ug??u

? d?? ¨ uF??u U

? u v ? h

Q

U d??

the sum as ? . Note that ??Gc? ? d ? ? for some . R ? if and only if G Y Thus G§Ra??Gc? and G ??Gc? each increase by 1 except at ? d ? , where the former skips from ? d R Q ? to G R ? d ? ? d . Thus R Q R Q and the latter repeats the value the sums are ? ? ? ?

9? ??G?R v @ AQ U 9?? ? 9?? ? R 9? v @ Q U 9XU ? 9?? ? ? 9 v @ Q U?9 Y ? ? v @ Q U?? ? R 9 ? v ? CF? Q U?9 R ? ? v @ Q U?? ? Q R A(aE b

? Alternate ?

solution: ?

? rewrite

Suppose ? r is strictly increasing. If ?Dd for some r 9 choice of ? , then 9 is dominated by n d for G suf?r r G suf?ciently negative. But taking 9 and 9?? d for ? r à 9a à ciently negative of the right parity, we get r ??r ¨ ??r ¨ 9 H7? 9?? d , contradiction. Thus ? d 9?? d but ? ? r r ??r ¨( r ? ??@ and @ ??@!nw@ , we have ? n?@ ; since r for e all? . Analogously, if ? is strictly decreasing, then r 9 or else 9 is r dominated by n @ for G suf?ciently ??d r positive. But taking 9 and 9?? d ? for G r suf?ciently posr 9?? d?à 9 but itive of the right parity, we get à ?r ¨ ??r ¨ 9?? d 9 , contradiction. Thus in that case, ? à?? r ?r?¨? r for all . ? nDd B–6 Yes, there must exist in?nitely many such G . Let ?% be ? !? ¨ ? 9 the convex hull $ of the set of points G for G . Geometrically, is the intersection of all convex sets ? ?? ¨ 9 ; G (or even all halfplanes) containing the $ ??r5points ? ¨ algebraically, ? is ? the set of points which can u ? u ?? ? ¨ ¨ 9?? for some be written as ? @ G @ 9X? R ?D??? R?? G u ??@ b?bDb ? which are nonnegative of sum 1.

9 We prove that for in?nitely many G , G is a vertex $ on the upper boundary of , and that ? these G satisfy the ?? ¨ 9 given condition. The condition that G is a vertex $ to the exison the upper boundary of is equivalent ? !? ¨ 9 tence of a line passing through G with all other $ ? points of below it. That is, there should exist ? H such that ? u à ? 9 R ? ? x Y G ¨ ? x ?eA b ? ?? ¨ $

? ? ?

× B–4 For a rational number expressed in? ?X lowest terms, ? ? ? ? CF?w¨ × R ? × de?ne CFits height to be . Then for ?j"$ any expressed in lowest terms, we have × ? ? CF?w¨?¨??? ? d Y ? ?X? d ? ? q × × R × ; ? since by assumption ? ? B ? ? ?X? , we have × and are nonzero integers with × ? ? q ? × Cg?w¨?¨)Y ? ? × Cg?w¨?%? ? d Y ?E ? ?X?Y?? ? Y? ?X? d ? × R × × ? X ? ?Ya? ??Ya? ?X? R × × ???? ??YAD¨???? ?X?YA?¨ ? Q b × R Q

It follows that q ? consists solely of numbers of height strictly larger than Q G?R Q , and hence

? 9? v ? @ q 9 ? ?$?¨02? b

?

9

??$?¨

(1)

Note: many choices for the height function are possible: ? CF?w¨B???w?|? ??w? ?X? ? CF?w¨ one can take ? × × , or ? × ? equal to the total number of prime factors of × and , and so on. The key properties of the height function are that on one hand, there are only ?nitely many rationals with height below any ?nite bound, and on the other hand, the height function is a suf?ciently “algebraic” function Cg? of its ? argument that one can relate the heights of × CF?w¨ and q × . B–5 Note that ? and hence

??r ¨` r ? ? implies that ? ? ? ? from the given equation. That is, ? is ? ? ? ¨ ? ??r ¨?¨` ? ? ¨?¨

G We ?rst show that satis?es (1). The condition ? u C ??? ??? ??? u Y?? ¨?CX? YmAD¨1? x x x @ as implies that ? f??? u YS? ¨?CV? Y?AD¨ x i has an upper @ as well. Thus the set ? u ?a? ? ? x YAD¨ @ R bound ? , and now , as desired.

?A

Next, we show that given one G satisfying (1), there exists a? larger one? also satisfying (1). Again, the conu C ? ? ? ?? u Y x x dition as implies that ? ¨?CX? Y ¨?? ? ? ? x 9 G as x . Thus the sequence f??? u Y?? ¨?CX? Y ¨ uFè x i 9 9 has a maximum element; supG n is the largest value of x that achieves this pose x h??gé3Y?? ¨?CX? Y ¨ 9 maximum, and put ? n G . Then the ? !??éD¨ ? !? u ¨ ? x line through n of slope lies strictly above ? !? u ¨ for x HBn and passes through or lies above x for 3

x ?

àhn Y?ê

. Thus (1) holds for ê for suitably small H

G

?

.

n

with

?

replaced by

for ?

By induction, we have that (1) holds for in?nitely many ? ? such that G . For any such G there exists H

?AF YhA ? Y ?? bDb?b G ? ? , the points G ? ! !? ¨ ? G&Rm? 9?? y lie below the line through G 9 ? ? ? ? ? 9 R . That means 9?? y à ? and 9VU y à ? ? adding these together gives 9XU y R 9?? y à Q ?

¨ ?

9VU y

sired.

and ofY slope ? 9 ?; 9 , as de-

¨

4

The 63rd William Lowell Putnam Mathematical Competition Saturday, December 7, 2002

A1 Let k be a ?xed positive integer. The n-th derivative of Pn (x) 1 has the form (xk where Pn (x) is a polynoxk ?1 ?1)n+1 mial. Find Pn (1). A2 Given any ?ve points on a sphere, show that some four of them must lie on a closed hemisphere. A3 Let n ≥ 2 be an integer and Tn be the number of nonempty subsets S of {1, 2, 3, . . . , n} with the property that the average of the elements of S is an integer. Prove that Tn ? n is always even. A4 In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3 × 3 matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 3 × 3 matrix is completed with ?ve 1’s and four 0’s. Player 0 wins if the determinant is 0 and player 1 wins otherwise. Assuming both players pursue optimal strategies, who will win and how? A5 De?ne a sequence by a0 = 1, together with the rules a2n+1 = an and a2n+2 = an + an+1 for each integer n ≥ 0. Prove that every positive rational number appears in the set an?1 :n≥1 an = 1 1 2 1 3 , , , , ,... 1 2 1 3 2 .

Each player, in turn, signs his or her name on a previously unsigned face. The winner is the player who ?rst succeeds in signing three faces that share a common vertex. Show that the player who signs ?rst will always win by playing as well as possible. B3 Show that, for all integers n > 1, 1 1 1 < ? 1? 2ne e n

n

<

1 . ne

B4 An integer n, unknown to you, has been randomly chosen in the interval [1, 2002] with uniform probability. Your objective is to select n in an odd number of guesses. After each incorrect guess, you are informed whether n is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than 2/3. B5 A palindrome in base b is a positive integer whose baseb digits read the same backwards and forwards; for example, 2002 is a 4-digit palindrome in base 10. Note that 200 is not a palindrome in base 10, but it is the 3digit palindrome 242 in base 9, and 404 in base 7. Prove that there is an integer which is a 3-digit palindrome in base b for at least 2002 different values of b. B6 Let p be a prime number. Prove that the determinant of the matrix ? ? x y z ? xp y p z p ? 2 2 2 xp y p z p is congruent modulo p to a product of polynomials of the form ax + by + cz , where a, b, c are integers. (We say two integer polynomials are congruent modulo p if corresponding coef?cients are congruent modulo p.)

A6 Fix an integer b ≥ 2. Let f (1) = 1, f (2) = 2, and for each n ≥ 3, de?ne f (n) = nf (d), where d is the number of base-b digits of n. For which values of b does 1 f (n) n=1 converge? B1 Shanille O’Keal shoots free throws on a basketball court. She hits the ?rst and misses the second, and thereafter the probability that she hits the next shot is equal to the proportion of shots she has hit so far. What is the probability she hits exactly 50 of her ?rst 100 shots? B2 Consider a polyhedron with at least ?ve faces such that exactly three edges emerge from each of its vertices. Two players play the following game:

∞

Solutions to the 63rd William Lowell Putnam Mathematical Competition Saturday, December 7, 2002

Kiran Kedlaya and Lenny Ng

A1 By differentiating Pn (x)/(xk ? 1)n+1 , we ?nd that Pn+1 (x) = (xk ? 1)Pn (x) ? (n + 1)kxk?1 Pn (x); substituting x = 1 yields Pn+1 (1) = ?(n + 1)kPn (1). Since P0 (1) = 1, an easy induction gives Pn (1) = (?k )n n! for all n ≥ 0. Note: one can also argue by expanding in Taylor series around 1. Namely, we have 1 1 1 = = (x ? 1)?1 + · · · , xk ? 1 k (x ? 1) + · · · k so dn 1 (?1)n n! = n k dx x ? 1 k (x ? 1)?n?1 and Pn (x) = (xk ? 1)n+1 dn 1 dxn xk ? 1 = (k (x ? 1) + · · · )n+1 (?1)n n! (x ? 1)?n?1 + · · · k = (?k )n n! + · · · . A2 Draw a great circle through two of the points. There are two closed hemispheres with this great circle as boundary, and each of the other three points lies in one of them. By the pigeonhole principle, two of those three points lie in the same hemisphere, and that hemisphere thus contains four of the ?ve given points. Note: by a similar argument, one can prove that among any n +3 points on an n-dimensional sphere, some n +2 of them lie on a closed hemisphere. (One cannot get by with only n + 2 points: put them at the vertices of a regular simplex.) Namely, any n of the points lie on a great sphere, which forms the boundary of two hemispheres; of the remaining three points, some two lie in the same hemisphere. A3 Note that each of the sets {1}, {2}, . . . , {n} has the desired property. Moreover, for each set S with integer average m that does not contain m, S ∪ {m} also has average m, while for each set T of more than one element with integer average m that contains m, T \{m} also has average m. Thus the subsets other than {1}, {2}, . . . , {n} can be grouped in pairs, so Tn ? n is even.

A4 (partly due to David Savitt) Player 0 wins with optimal play. In fact, we prove that Player 1 cannot prevent Player 0 from creating a row of all zeroes, a column of all zeroes, or a 2 × 2 submatrix of all zeroes. Each of these forces the determinant of the matrix to be zero. For i, j = 1, 2, 3, let Aij denote the position in row i and column j . Without loss of generality, we may assume that Player 1’s ?rst move is at A11 . Player 0 then plays at A22 : ? ? 1 ? ? ?? 0 ?? ? ? ? After Player 1’s second move, at least one of A23 and A32 remains vacant. Without loss of generality, assume A23 remains vacant; Player 0 then plays there. After Player 1’s third move, Player 0 wins by playing at A21 if that position is unoccupied. So assume instead that Player 1 has played there. Thus of Player 1’s three moves so far, two are at A11 and A21 . Hence for i equal to one of 1 or 3, and for j equal to one of 2 or 3, the following are both true: (a) The 2 × 2 submatrix formed by rows 2 and i and by columns 2 and 3 contains two zeroes and two empty positions. (b) Column j contains one zero and two empty positions. Player 0 next plays at Aij . To prevent a zero column, Player 1 must play in column j , upon which Player 0 completes the 2 × 2 submatrix in (a) for the win. Note: one can also solve this problem directly by making a tree of possible play sequences. This tree can be considerably collapsed using symmetries: the symmetry between rows and columns, the invariance of the outcome under reordering of rows or columns, and the fact that the scenario after a sequence of moves does not depend on the order of the moves (sometimes called “transposition invariance”). Note (due to Paul Cheng): one can reduce Determinant Tic-Tac-Toe to a variant of ordinary tic-tac-toe. Namely, consider a tic-tac-toe grid labeled as follows: A11 A22 A33 A23 A31 A12 A32 A13 A21

Then each term in the expansion of the determinant occurs in a row or column of the grid. Suppose Player 1 ?rst plays in the top left. Player 0 wins by playing ?rst in the top row, and second in the left column. Then there are only one row and column left for Player 1 to threaten, and Player 1 cannot already threaten both on the third move, so Player 0 has time to block both. A5 It suf?ces to prove that for any relatively prime positive integers r, s, there exists an integer n with an = r and an+1 = s. We prove this by induction on r + s, the case r + s = 2 following from the fact that a0 = a1 = 1. Given r and s not both 1 with gcd(r, s) = 1, we must have r = s. If r > s, then by the induction hypothesis we have an = r ? s and an+1 = s for some n; then a2n+2 = r and a2n+3 = s. If r < s, then we have an = r and an+1 = s ? r for some n; then a2n+1 = r and a2n+2 = s. Note: a related problem is as follows. Starting with the sequence 0 1 , , 1 0 repeat the following operation: insert between each pair a c a+c b and d the pair b+d . Prove that each positive rational number eventually appears.

c Observe that by induction, if a b and d are consecutive terms in the sequence, then bc ? ad = 1. The same holds for consecutive terms of the n-th Farey sequence, the sequence of rational numbers in [0, 1] with denominator (in lowest terms) at most n.

For b = 2, we have a slightly different identity because f (2) = 2f (2). Instead, for any positive integer i, we have

2i ?1

n=1

1 1 1 =1+ + + f (n) 2 6

i

d=3

1 f (d)

2d ?1

n=2d?1

1 . (2) n

Again comparing an integral to a Riemann sum, we see that for d ≥ 3,

2d ?1

n=2d?1

1 1 1 < d?1 ? d + n 2 2 =

2d 2d?1

dx x

1 + log 2 2d 1 ≤ + log 2 < 0.125 + 0.7 < 1. 8 Put c =

1 8 1 +log 2 and L = 1+ 1 2 + 6(1?c) . Then we can 2i ?1

prove that n=1 f (1 n) < L for all i ≥ 2 by induction on i. The case i = 2 is clear. For the induction, note that by (2),

2i ?1

n=1

1 1 1 <1+ + +c f (n) 2 6

i

d=3

1 f (d)

1 1 1 <1+ + +c 2 6 6(1 ? c) 1 1 = L, =1+ + 2 6(1 ? c) as desired. We conclude that limit less than or equal to L.

∞ 1 n=1 f (n)

A6 The sum converges for b = 2 and diverges for b ≥ 3. We ?rst consider b ≥ 3. Suppose the sum converges; then the fact that f (n) = nf (d) whenever bd?1 ≤ n ≤ bd ? 1 yields 1 = f (n) n=1

∞ ∞

converges to a

d=1

1 f (d)

bd ?1

n=bd?1

1 . n

(1)

However, by comparing the integral of 1/x with a Riemann sum, we see that

bd ?1

Note: the above argument proves that the sum for b = 2 is at most L < 2.417. One can also obtain a lower 1 bound by the same technique, namely 1 + 1 2 + 6(1?c ) with c = log 2. This bound exceeds 2.043. (By contrast, summing the ?rst 100000 terms of the series only yields a lower bound of 1.906.) Repeating the same arguments with d ≥ 4 as the cutoff yields the upper bound 2.185 and the lower bound 2.079. B1 The probability is 1/99. In fact, we show by induction on n that after n shots, the probability of having made any number of shots from 1 to n ? 1 is equal to 1/(n ? 1). This is evident for n = 2. Given the result for n, we see that the probability of making i shots after n + 1 attempts is i?1 1 i + 1? n n?1 n 1 (i ? 1) + (n ? i) = n?1 n(n ? 1) 1 = , n

n=bd?1

1 > n

bd bd?1

dx x

= log(bd ) ? log(bd?1 ) = log b, where log denotes the natural logarithm. Thus (1) yields 1 1 > (log b) , f ( n ) f ( n) n=1 n=1 a contradiction since log b > 1 for b ≥ 3. Therefore the sum diverges. 2

∞ ∞

as claimed.

B2 (Note: the problem statement assumes that all polyhedra are connected and that no two edges share more than one face, so we will do likewise. In particular, these are true for all convex polyhedra.) We show that in fact the ?rst player can win on the third move. Suppose the polyhedron has a face A with at least four edges. If the ?rst player plays there ?rst, after the second player’s ?rst move there will be three consecutive faces B, C, D adjacent to A which are all unoccupied. The ?rst player wins by playing in C ; after the second player’s second move, at least one of B and D remains unoccupied, and either is a winning move for the ?rst player. It remains to show that the polyhedron has a face with at least four edges. (Thanks to Russ Mann for suggesting the following argument.) Suppose on the contrary that each face has only three edges. Starting with any face F1 with vertices v1 , v2 , v3 , let v4 be the other endpoint of the third edge out of v1 . Then the faces adjacent to F1 must have vertices v1 , v2 , v4 ; v1 , v3 , v4 ; and v2 , v3 , v4 . Thus v1 , v2 , v3 , v4 form a polyhedron by themselves, contradicting the fact that the given polyhedron is connected and has at least ?ve vertices. (One can also deduce this using Euler’s formula V ? E + F = 2 ? 2g , where V, E, F are the numbers of vertices, edges and faces, respectively, and g is the genus of the polyhedron. For a convex polyhedron, g = 0 and you get the “usual” Euler’s formula.) Note: Walter Stromquist points out the following counterexample if one relaxes the assumption that a pair of faces may not share multiple edges. Take a tetrahedron and remove a smaller tetrahedron from the center of an edge; this creates two small triangular faces and turns two of the original faces into hexagons. Then the second player can draw by signing one of the hexagons, one of the large triangles, and one of the small triangles. (He does this by “mirroring”: wherever the ?rst player signs, the second player signs the other face of the same type.) B3 The desired inequalities can be rewritten as 1? 1 1 < exp 1 + n log 1 ? n n <1? 1 . 2n

which is evident because the inequalities hold term by term. Note: David Savitt points out that the upper bound can be improved from 1/(ne) to 2/(3ne) with a slightly more complicated argument. (In fact, for any c > 1/2, one has an upper bound of c/(ne), but only for n above a certain bound depending on c.) B4 Use the following strategy: guess 1, 3, 4, 6, 7, 9, . . . until the target number n is revealed to be equal to or lower than one of these guesses. If n ≡ 1 (mod 3), it will be guessed on an odd turn. If n ≡ 0 (mod 3), it will be guessed on an even turn. If n ≡ 2 (mod 3), then n + 1 will be guessed on an even turn, forcing a guess of n on the next turn. Thus the probability of success with this strategy is 1335/2002 > 2/3. Note: for any positive integer m, this strategy wins when the number is being guessed from [1, m] with 1 2m+1 probability m . We can prove that this is best 3 possible as follows. Let am denote m times the probability of winning when playing optimally. Also, let bm denote m times the corresponding probability of winning if the objective is to select the number in an even number of guesses instead. (For de?niteness, extend the de?nitions to incorporate a0 = 0 and b0 = 0.) We ?rst claim that am = 1+max1≤k≤m {bk?1 + bm?k } and bm = max1≤k≤m {ak?1 + am?k } for m ≥ 1. To establish the ?rst recursive identity, suppose that our ?rst guess is some integer k . We automatically win if n = k , with probability 1/m. If n < k , with probability (k ? 1)/m, then we wish to guess an integer in [1, k ? 1] in an even number of guesses; the probability of success when playing optimally is bk?1 /(k ? 1), by assumption. Similarly, if n < k , with probability (m ? k )/m, then the subsequent probability of winning is bm?k /(m ? k ). In sum, the overall probability of winning if k is our ?rst guess is (1 + bk?1 + bm?k )/m. For optimal strategy, we choose k such that this quantity is maximized. (Note that this argument still holds if k = 1 or k = m, by our de?nitions of a0 and b0 .) The ?rst recursion follows, and the second recursion is established similarly. We now prove by induction that am = (2m + 1)/3 and bm = 2m/3 for m ≥ 0. The inductive step relies on the inequality x + y ≤ x + y , with equality when one of x, y is an integer. Now suppose that ai = (2i + 1)/3 and bi = 2i/3 for i < m. Then 1 + bk?1 + bm?k = 1 + ≤ 2m 3 2(k ? 1) 2(m ? k ) + 3 3

By taking logarithms, we can rewrite the desired inequalities as ? log 1 ? 1 2n < ?1 ? n log 1 ? < ? log 1 ? 1 n . 1 n

Rewriting these in terms of the Taylor expansion of ? log(1 ? x), we see that the desired result is also equivalent to

∞

i=1

1 < i2i ni

∞

i=1

1 < (i + 1)ni

∞

i=1

1 , ini 3

and similarly ak?1 + am?k ≤ (2m + 1)/3 , with equality in both cases attained, e.g., when k = 1. The inductive formula for am and bm follows.

B5 (due to Dan Bernstein) Put N = 2002!. Then for d = 1, . . . , 2002, the number N 2 written in base b = N/d ? 1 has digits d2 , 2d2 , d2 . (Note that these really are digits because 2(2002)2 < (2002!)2 /2002 ? 1.) Note: one can also produce an integer N which has base b digits 1, ?, 1 for n different values of b, as follows. Choose c with 0 < c < 21/n . For m a large positive integer, put N = 1 + (m + 1) · · · (m + n) cm n?2 . For m suf?ciently large, the bases b= N ?1 = (m + i)mn?2 (m + j )

j =i

side. Moreover, both sides have the same leading coef?cient. Since they both have degree only p, they must then coincide. We thus have

p?1 p?1

x

i=0

(y + ix)

i,j =0

(z + ix + jy )

p?1

≡ x(y p ? xp?1 y )

j =0 p?1

((z + jy )p ? xp?1 (z + jy ))

≡ (xy p ? xp y )

j =0 p p

(z p ? xp?1 z + jy p ? jxp?1 y )

for i = 1, . . . , n will have the properties that N ≡ 1 (mod b) and b2 < N < 2b2 for m suf?ciently large. Note (due to Russ Mann): one can also give a “nonconstructive” argument. Let N be a large positive integer. For b ∈ (N 2 , N 3 ), the number of 3-digit base-b palindromes in the range [b2 , N 6 ? 1] is at least N 6 ? b2 N6 ? 1 ≥ 2 ? b ? 2, b b since there is a palindrome in each interval [kb, (k + 1)b ? 1] for k = b, . . . , b2 ? 1. Thus the average number of bases for which a number in [1, N 6 ? 1] is at least 1 N6

N 3 ?1

≡ (xy ? x y )((z p ? xp?1 z )p ? (y p ? xp?1 y )p?1 (z p ? xp?1 z )) ≡ (xy p ? xp y )(z p ? xp ? x(y ? x

2 2 2 2

?p p

z ) y z + xp yz p

2 2 2

p

p?1

y ) (z ? xp?1 z )

p p

2 2

≡ xy p z p ? xp yz p ? xp ? xy p z p + xp

2 2 2 2

?p+1 p p

?p+1 p p

y z + xp y p z ? xp y p z

2 2

≡ xy p z p + yz p xp + zxp y p

2

? xz p y p ? yxp z p ? zy p xp , which is precisely the desired determinant. Note: a simpler conceptual proof is as follows. (Everything in this paragraph will be modulo p.) Note that for any integers a, b, c, the column vector [ax + 2 by + cz, (ax + by + cz )p , (ax + by + cz )p ] is a linear combination of the columns of the given matrix. Thus ax + by + cz divides the determinant. In particular, all of the factors of (3) divide the determinant; since both (3) and the determinant have degree p2 + p + 1, they agree up to a scalar multiple. Moreover, they have the same 2 coef?cient of z p y p x (since this term only appears in the expansion of (3) when you choose the ?rst term in each factor). Thus the determinant is congruent to (3), as desired. Either argument can be used to generalize to a corresponding n × n determinant, called a Moore determinant; we leave the precise formulation to the reader. Note the similarity with the classical Vandermonde determinant: if A is the n × n matrix with Aij = xj i for i, j = 0, . . . , n ? 1, then det(A) =

1≤i<j ≤n

b=N 2 +1

N6 ?b?2 b

≥ log(N ) ? c

for some constant c > 0. Take N so that the right side exceeds 2002; then at least one number in [1, N 6 ? 1] is a base-b palindrome for at least 2002 values of b. B6 We prove that the determinant is congruent modulo p to

p?1 p?1

x

i=0

(y + ix)

i,j =0

(z + ix + jy ).

(3)

We ?rst check that

p?1

(y + ix) ≡ y p ? xp?1 y

i=0

(mod p).

(4)

Since both sides are homogeneous as polynomials in x and y , it suf?ces to check (4) for x = 1, as a congruence between polynomials. Now note that the right side has 0, 1, . . . , p ? 1 as roots modulo p, as does the left

(xj ? xi ).

4

The 64th William Lowell Putnam Mathematical Competition Saturday, December 6, 2003

A1 Let be a ?xed positive integer. How many ways are there to write as a sum of positive integers, , with an arbitrary positive integer and ? For example, with there are four ways: 4, 2+2, 1+1+2, 1+1+1+1.

? ? ?? ??? ??¤§?¨? ?¤!??? ?" ? ? ¤ ?%$ ? # ?&?%' A2 Let ?(¤0)1??2)333)4?65 and 7 ¤0) 7 ?8)333) 7 5 be nonnegative real numbers. Show that 9 ? ¤ ? ? 4? 5(@ ¤BA45 ? 9 7 ¤ 7 ? 7 5(@ ¤BA45 DC 9 ? ¤ ? 7 ¤E@ 9 ? ? ? 7 ?@ 9 ? 5 ? 7 5(@GF ¤1A45 3 A3 Find the minimum value of HPI1QSRUT ?WVX I?T ?Y4` RaT ?WVX8Y T ? I1b V T ?¨V I V TcH T for real numbers . r t A4 Suppose that ?d) 7 )1ef)4gh)4ip)4q are real numbers, ?s?u v g w ? r t and ? ? that H ?, Tsuch 7 T T ?We H H g T ? ?Wi T ?xq H for all real numbers . Show that H 7 ?ay '??e H H i ?Uy '?g?q H 3 9 A5 A Dyck ? -path is a lattice path of ? upsteps $2)$ @ and ? y 9 downsteps $2) T $ @ that starts at the origin ? and never dips below the -axis. A return is a maximal sequence T of contiguous downsteps that terminates on the -axis.

For example, the Dyck 5-path illustrated has two returns, of length 3 and 1 respectively.

B1 Do there exist polynomials that

? 9?T @ ) 7 9?T @ )4e 9?? @ )4d 9?? @ such T ? ? T ? ? ? ?w? 9?T @ e 9?? @ ? 7 9?T @ d 9?? @ $e? f

B2 Let

integer. Starting with the y sequence $2g ) ?¤ ?) g¤ be $ entries )33a3positive ) 5?4¤ 5, jkform a new sequence of ? ¤ h )U¤Pi ? )333) ?45lS5jm¤Pn by taking the averages of two consecutive entries in the ?rst sequence. Repeat the averaging of neighbors on second sequence to obtain a ypthe o entries, third sequence of ? and continue until T the ?nal sequence produced consists of a single number 5 . 6 o r T ?. Show that 5?q

holds identically?

O

Show that there is a one-to-one correspondence between the Dyck -paths with no return of even length and the Dyck -paths. A6 For a set of nonnegative integers, let denote such that , the number of ordered pairs , , and . Is it possible to partition the nonnegative integers into two sets and in such a way that for all ?

f? ? 9 ? @ ? ? ? 9 ? ? f ¤ ) ? ¤?? @ ? ??? ? ? ? ¤ ? r ? ? ? ¤?? ? ????? g 9 9 i ? ? ? ? @ @ ?? ?? ?

9 ? ?y $ @

5 u ?ts6? vxw ¤(y Vz|{6$2) o )333})~? r0????? 3 ? T ~ (Here VEz denotes the least common multiple, and T .) y denotes the greatest integer B4 Let ? 9?? @ ?w? ? h y? 7 ? g ?¨y e ? ? ?Wd ?y ?¨? y ?w? 9?? ? ¤ @ 9?? ? ? @ 9?? ? g @ 9?? ? h @ where ?d) 7 )4ef)1d?)1? are integers, ?u?? Show that if ¤? ?? ? ¤ ? ? is a rational number and ? r ¤?? t .? ?p ?r ? g ? ? h , then ? ? is a rational number. B5 Let gh)1i , and q be equidistant points on the circumference of a circle of unit radius centered at ? , and let ? be any point in the circle’s interior. Let ?d) 7 )4e be the distance from ? to g?)1i?)4q , respectively. Show that there is a triangle with side lengths ?d) 7 )1e , and that the area of ? depends only on the distance from ? to ? . this triangle 9?T @ be a continuous real-valued function de?ned B6 Let on the interval C t()$ F . Show that ? ¤ ? ¤ H ? 9?T @ ? ? 9?? @ H d T d ??? ? ¤ H ? 9?T @ H d T 3 ? ? ?

B3 Show that for each positive integer n,

Solutions to the 64th William Lowell Putnam Mathematical Competition Saturday, December 6, 2003

Manjul Bhargava, Kiran Kedlaya, and Lenny Ng

A1 There are n such sums. More precisely, there is exactly one such sum with k terms for each of k = 1, . . . , n (and clearly no others). To see this, note that if n = a1 + a2 + · · · + ak with a1 ≤ a2 ≤ · · · ≤ ak ≤ a1 + 1, then ka1 = a1 + a1 + · · · + a1 ≤ n ≤ a1 + (a1 + 1) + · · · + (a1 + 1) = ka1 + k ? 1. However, there is a unique integer a1 satisfying these inequalities, namely a1 = n/k . Moreover, once a1 is ?xed, there are k different possibilities for the sum a1 + a2 + · · · + ak : if i is the last integer such that ai = a1 , then the sum equals ka1 +(i ? 1). The possible values of i are 1, . . . , k , and exactly one of these sums comes out equal to n, proving our claim. Note: In summary, there is a unique partition of n with k terms that is “as equally spaced as possible”. One can also obtain essentially the same construction inductively: except for the all-ones sum, each partition of n is obtained by “augmenting” a unique partition of n ? 1. A2 First solution: Assume without loss of generality that ai + bi > 0 for each i (otherwise both sides of the desired inequality are zero). Then the AM-GM inequality gives a1 · · · an (a1 + b1 ) · · · (an + bn ) a1 an 1 + ··· + ≤ n a1 + b1 an + bn

1/n

positive (the general case follows by taking limits as some of the ai tend to zero). Put ri = bi /ai ; then the given inequality is equivalent to (1 + r1 )1/n · · · (1 + rn )1/n ≥ 1 + (r1 · · · rn )1/n . In terms of the function f (x) = log(1 + ex ) and the quantities si = log ri , we can rewrite the desired inequality as 1 (f (s1 ) + · · · + f (sn )) ≥ f n s1 + · · · + sn n .

This will follow from Jensen’s inequality if we can verify that f is a convex function; it is enough to check that f (x) > 0 for all x. In fact, f ( x) = ex 1 =1? x 1+e 1 + ex

is an increasing function of x, so f (x) > 0 and Jensen’s inequality thus yields the desired result. (As long as the ai are all positive, equality holds when s1 = · · · = sn , i.e., when the vectors (a1 , . . . , an ) and (b1 , . . . , bn ). Of course other equality cases crop up if some of the ai vanish, i.e., if a1 = b1 = 0.) Fourth solution: We apply induction on n, the case n = 1 being evident. First we verify the auxiliary inequality (an + bn )(cn + dn )n?1 ≥ (acn?1 + bdn?1 )n for a, b, c, d ≥ 0. The left side can be written as an cn(n?1) + bn dn(n?1)

n?1

,

and likewise with the roles of a and b reversed. Adding these two inequalities and clearing denominators yields the desired result. Second solution: Write the desired inequality in the form (a1 + b1 ) · · · (an + bn ) ≥ [(a1 · · · an )1/n + (b1 · · · bn )1/n ]n , expand both sides, and compare the terms on both sides in which k of the terms are among the ai . On the left, one has the product of each k element subset of {1, . . . , n}; on the right, one has n k/n · · · (b1 . . . bn )(n?k)/n , which is prek (a1 · · · an ) n cisely k times the geometric mean of the terms on the left. Thus AM-GM shows that the terms under consideration on the left exceed those on the right; adding these inequalities over all k yields the desired result. Third solution: Since both sides are continuous in each ai , it is suf?cient to prove the claim with a1 , . . . , an all

+

i=1 n?1

n ? 1 n ni n(n?1?i) b c d i n ? 1 n n(i?1) n(n?i) a c d . i?1

+

i=1

Applying the weighted AM-GM inequality between matching terms in the two sums yields (an + bn )(cn + dn )n?1 ≥ an cn(n?1) + bn dn(n?1)

n?1

+

i=1

n i n?i (n?1)i (n?1)(n?i) ab c d , i

2 proving the auxiliary inequality. Now given the auxiliary inequality and the n ? 1 case of the desired inequality, we apply the auxiliary inequality 1/n 1/n with a = a1 , b = b1 , c = (a2 · · · an )1/n(n?1) , 1/n(n?1) d = (b2 . . . bn ) . The right side will be the n-th power of the desired inequality. The left side comes out to (a1 + b1 )((a2 · · · an )1/(n?1) + (b2 · · · bn )1/(n?1) )n?1 , and by the induction hypothesis, the second factor is less than (a2 + b2 ) · · · (an + bn ). This yields the desired result. Note: Equality holds if and only if ai = bi = 0 for some i or if the vectors (a1 , . . . , an ) and (b1 , . . . , bn ) are proportional. As pointed out by Naoki Sato, the problem also appeared on the 1992 Irish Mathematical Olympiad. It is also a special case of a classical inequality, known as H¨ older’s inequality, which generalizes the Cauchy-Schwarz inequality (this is visible from the n = 2 case); the ?rst solution above is adapted from the standard proof of H¨ older’s inequality. We don’t know whether the declaration “Apply H¨ older’s inequality” by itself is considered an acceptable solution to this problem. A3 First solution: Write f (x) = sin x + cos x + tan x + cot x + sec x + csc x sin x + cos x 1 + . = sin x + cos x + sin x cos x sin x cos x √ We can write sin x + cos x = 2 cos(π/4 ? x); this suggests making the substitution y = π/4 ? x. In this new coordinate, 1 1 sin x cos x = sin 2x = cos 2y, 2 2 √ and writing c = 2 cos y , we have f (y ) = (1 + c) 1 + =c+ 2 . c?1 c2 2 ?1 ?1 Alternate derivation (due to Zuming Feng): We can also minimize |c + 2/(c ? 1)| without calculus (or worrying about boundary conditions). For c > 1, we have 1 + (c ? 1) + √ 2 ≥1+2 2 c?1

by AM-GM on the last two terms, with equality for c ? √ 1 = 2 (which is out of range). For c < 1, we similarly have √ 2 ≥ ?1 + 2 2, 1?c √ here with equality for 1 ? c = 2. ?1 + 1 ? c + Second solution: Write f (a, b) = a + b + 1 a+b + . ab ab

Then the problem is to minimize |f (a, b)| subject to the constraint a2 + b2 ? 1 = 0. Since the constraint region has no boundary, it is enough to check the value at each critical point and each potential discontinuity (i.e., where ab = 0) and select the smallest value (after checking that f has no sign crossings). We locate the critical points using the Lagrange multiplier condition: the gradient of f should be parallel to that of the constraint, which is to say, to the vector (a, b). Since ?f 1 1 =1? 2 ? 2 ?a a b a and similarly for b, the proportionality yields a2 b3 ? a3 b2 + a3 ? b3 + a2 ? b2 = 0. The irreducible factors of the left side are 1 + a, 1 + b, a ? b, and ab ? a ? b. So we must check what happens when any of those factors, or a or b, vanishes. If 1 + a = 0, then b = 0, and the singularity of f becomes removable when restricted to the circle. Namely, we have f =a+b+ 1 b+1 + a ab

We in the range √ must √ analyze this function √ of c √ [? 2, 2]. Its value at c = ? 2 is 2 ? 3 2 < ?2.24, √ √ and at c = 2 is 2 + 3 2 > 6.24. Its derivative is 1 ? 2/(c ? 1)2 , which vanishes when (c ? 1)2 = √ 2, i.e., √ where c = 1 ± 2. Only the value c =√ 1 ? 2 is in bounds, at which the value of f is 1 ? 2 2 > ?1.83. As for the pole at c = 1, we observe that f decreases as c approaches from below (so takes negative values for all c < 1) and increases as c approaches from above (so takes positive values for all c > 1); from the data collected so far, we see that f has no sign crossings, so the minimum of |f | is achieved at a critical √ point of f . We conclude that the minimum of |f | is 2 2 ? 1.

and a2 + b2 ? 1 = 0 implies (1+ b)/a = a/(1 ? b). Thus we have f = ?2; the same occurs when 1 + b = 0. √ If a ? ± 2/2 and either f = √b = 0, then a = b = √ 2 + 3 2 > 6.24, or f = 2 ? 3 2 < ?2.24. If a = 0, then either b = ?1 as discussed above, or b = 1. In the latter case, f blows up as one approaches this point, so there cannot be a global minimum there. Finally, if ab ? a ? b = 0, then a2 b2 = (a + b)2 = 2ab + 1

3 √ and so ab = 1 ± 2. The √ plus sign is impossible since |ab| ≤ 1, so ab = 1 ? 2 and f (a, b) = ab + 1 +1 ab √ = 1 ? 2 2 > ?1.83. A5 First solution: We represent a Dyck n-path by a sequence a1 · · · a2n , where each ai is either (1, 1) or (1, ?1). Given an (n ? 1)-path P = a1 · · · a2n?2 , we distinguish two cases. If P has no returns of even-length, then let f (P ) denote the n-path (1, 1)(1, ?1)P . Otherwise, let ai ai+1 · · · aj denote the rightmost even-length return in P , and let f (P ) = (1, 1)a1 a2 · · · aj (1, ?1)aj +1 · · · a2n?2 . Then f clearly maps the set of Dyck (n ? 1)-paths to the set of Dyck n-paths having no even return. We claim that f is bijective; to see this, we simply construct the inverse mapping. Given an n-path P , let R = ai ai+1 ...aj denote the leftmost return in P , and let g (P ) denote the path obtained by removing a1 and aj from P . Then evidently f ? g and g ? f are identity maps, proving the claim. Second solution: (by Dan Bernstein) Let Cn be the number of Dyck paths of length n, let On be the number of Dyck paths whose ?nal return has odd length, and let Xn be the number of Dyck paths with no return of even length. We ?rst exhibit a recursion for On ; note that O0 = 0. Given a Dyck n-path whose ?nal return has odd length, split it just after its next-to-last return. For some k (possibly zero), this yields a Dyck k -path, an upstep, a Dyck (n ? k ? 1)-path whose odd return has even length, and a downstep. Thus for n ≥ 1,

n?1

This yields the smallest value of |f | in the √list (and indeed no sign crossings are possible), so 2 2 ? 1 is the desired minimum of |f |. Note: Instead of using the geometry of the graph of f to rule out sign crossings, one can verify explicitly that f cannot take the value 0. In the ?rst solution, note that c + 2/(c ? 1) = 0 implies c2 ? c + 2 = 0, which has no real roots. In the second solution, we would have a2 b + ab2 + a + b = ?1. Squaring both sides and simplifying yields 2a3 b3 + 5a2 b2 + 4ab = 0, whose only real root is ab = 0. But the cases with ab = 0 do not yield f = 0, as veri?ed above. A4 We split into three cases. Note ?rst that |A| ≥ |a|, by applying the condition for large x. Case 1: B 2 ? 4AC > 0. In this case Ax2 + Bx + C has two distinct real roots r1 and r2 . The condition implies that ax2 +bx+c also vanishes at r1 and r2 , so b2 ?4ac > 0. Now B 2 ? 4AC = A2 (r1 ? r2 )2 ≥ a2 (r1 ? r2 )2 = b ? 4ac. Case 2: B 2 ? 4AC ≤ 0 and b2 ? 4ac ≤ 0. Assume without loss of generality that A ≥ a > 0, and that B = 0 (by shifting x). Then Ax2 + Bx + C ≥ ax2 + bx + c ≥ 0 for all x; in particular, C ≥ c ≥ 0. Thus 4AC ? B 2 = 4AC ≥ 4ac ≥ 4ac ? b . Alternate derivation (due to Robin Chapman): the ellipse Ax2 + Bxy + Cy 2 = 1 is contained within the ellipse ax2 + bxy + cy 2 = 1, and their respective enclosed areas are π/(4AC ? B 2 ) and π/(4ac ? b2 ). Case 3: B 2 ? 4AC ≤ 0 and b2 ? 4ac > 0. Since Ax2 + Bx + C has a graph not crossing the x-axis, so do (Ax2 + Bx + C ) ± (ax2 + bx + c). Thus (B ? b)2 ? 4(A ? a)(C ? c) ≤ 0, (B + b) ? 4(A + a)(C + c) ≤ 0 and adding these together yields 2(B ? 4AC ) + 2(b ? 4ac) ≤ 0. Hence b2 ? 4ac ≤ 4AC ? B 2 , as desired.

2 2 2 2 2

On =

k=0

Ck (Cn?k?1 ? On?k?1 ).

We next exhibit a similar recursion for Xn ; note that X0 = 1. Given a Dyck n-path with no even return, splitting as above yields for some k a Dyck k -path with no even return, an upstep, a Dyck (n?k ?1)-path whose ?nal return has even length, then a downstep. Thus for n ≥ 1,

n?1

Xn =

k=0

Xk (Cn?k?1 ? On?k?1 ).

To conclude, we verify that Xn = Cn?1 for n ≥ 1, by induction on n. This is clear for n = 1 since X1 = C0 = 1. Given Xk = Ck?1 for k < n, we have

n?1

Xn =

k=0

Xk (Cn?k?1 ? On?k?1 )

n?1

= Cn?1 ? On?1 +

k=1

Ck?1 (Cn?k?1 ? On?k?1 )

= Cn?1 ? On?1 + On?1 = Cn?1 , as desired.

4 Note: Since the problem only asked about the existence of a one-to-one correspondence, we believe that any proof, bijective or not, that the two sets have the same cardinality is an acceptable solution. (Indeed, it would be highly unusual to insist on using or not using a speci?c proof technique!) The second solution above can also be phrased in terms of generating functions. Also, the Cn are well-known to equal the Catalan numbers 2n 1 n+1 n ; the problem at hand is part of a famous exercise in Richard Stanley’s Enumerative Combinatorics, Volume 1 giving 66 combinatorial interpretations of the Catalan numbers. A6 First solution: Yes, such a partition is possible. To achieve it, place each integer into A if it has an even number of 1s in its binary representation, and into B if it has an odd number. (One discovers this by simply attempting to place the ?rst few numbers by hand and noticing the resulting pattern.) To show that rA (n) = rB (n), we exhibit a bijection between the pairs (a1 , a2 ) of distinct elements of A with a1 + a2 = n and the pairs (b1 , b2 ) of distinct elements of B with b1 + b2 = n. Namely, given a pair (a1 , a2 ) with a1 + a2 = n, write both numbers in binary and ?nd the lowest-order place in which they differ (such a place exists because a1 = a2 ). Change both numbers in that place and call the resulting numbers b1 , b2 . Then a1 + a2 = b1 + b2 = n, but the parity of the number of 1s in b1 is opposite that of a1 , and likewise between b2 and a2 . This yields the desired bijection. Second solution: (by Micah Smukler) Write b(n) for the number of 1s in the base 2 expansion of n, and f (n) = (?1)b(n) . Then the desired partition can be described as A = f ?1 (1) and B = f ?1 (?1). Since f (2n) + f (2n + 1) = 0, we have

n

rA (n) (resp. rB (n)) is the coef?cient of xn in f (x)2 ? f (x2 ) (resp. g (x)2 ? g (x2 )). From the evident identities 1 = f (x) + g (x) 1?x f (x) = f (x2 ) + xg (x2 ) g (x) = g (x2 ) + xf (x2 ), we have f (x) ? g (x) = f (x2 ) ? g (x2 ) + xg (x2 ) ? xf (x2 ) = (1 ? x)(f (x2 ) ? g (x2 )) = f (x2 ) ? g (x2 ) . f (x) + g (x)

We deduce that f (x)2 ? g (x)2 = f (x2 ) ? g (x2 ), yielding the desired equality. Note: This partition is actually unique, up to interchanging A and B . More precisely, the condition that 0 ∈ A and rA (n) = rB (n) for n = 1, . . . , m uniquely determines the positions of 0, . . . , m. We see this by induction on m: given the result for m ? 1, switching the location of m changes rA (m) by one and does not change rB (m), so it is not possible for both positions to work. Robin Chapman points out this problem is solved in D.J. Newman’s Analytic Number Theory (Springer, 1998); in that solution, one uses generating functions to ?nd the partition and establish its uniqueness, not just verify it. B1 No, there do not. First solution: Suppose the contrary. By setting y = ?1, 0, 1 in succession, we see that the polynomials 1 ? x + x2 , 1, 1 + x + x2 are linear combinations of a(x) and b(x). But these three polynomials are linearly independent, so cannot all be written as linear combinations of two other polynomials, contradiction. Alternate formulation: the given equation expresses a diagonal matrix with 1, 1, 1 and zeroes on the diagonal, which has rank 3, as the sum of two matrices of rank 1. But the rank of a sum of matrices is at most the sum of the ranks of the individual matrices. Second solution: It is equivalent (by relabeling and rescaling) to show that 1 + xy + x2 y 2 cannot be written as a(x)d(y ) ? b(x)c(y ). Write a(x) = ai xi , b(x) = bi xi , c(y ) = cj y j , d(y ) = dj y j . We now start comparing coef?cients of 1+ xy + x2 y 2 . By comparing coef?cients of 1 + xy + x2 y 2 and a(x)d(y ) ? b(x)c(y ), we get 1 = ai di ? bi ci 0 = ai dj ? bi cj (i = 0, 1, 2) (i = j ).

f (n) =

i=0

0 n odd f (n) n even.

If p, q are both in A, then f (p) + f (q ) = 2; if p, q are both in B , then f (p)+ f (q ) = ?2; if p, q are in different sets, then f (p) + f (q ) = 0. In other words, 2(rA (n) ? rB (n)) =

p+q =n,p<q

(f (p) + f (q ))

and it suf?ces to show that the sum on the right is always n zero. If n is odd, that sum is visibly i=0 f (i) = 0. If n is even, the sum equals

n

f (i)

i=0

? f (n/2) = f (n) ? f (n/2) = 0.

This yields the desired result. Third solution: (by Dan Bernstein) Put f (x) = n n n∈A x and g (x) = n∈B x ; then the value of

The ?rst equation says that ai and bi cannot both vanish, and ci and di cannot both vanish. The second equation says that ai /bi = cj /dj when i = j , where both sides

5 should be viewed in R ∪ {∞} (and neither is undetermined if i, j ∈ {0, 1, 2}). But then a0 /b0 = c1 /d1 = a2 /b2 = c0 /d0 contradicting the equation a0 d0 ? b0 c0 = 1. Third solution: We work over the complex numbers, in which we have a primitive cube root ω of 1. We also use without further comment unique factorization for polynomials in two variables over a ?eld. And we keep the relabeling of the second solution. Suppose the contrary. Since 1 + xy + x2 y 2 = (1 ? xy/ω )(1 ? xy/ω 2 ), the rational function a(ω/y )d(y ) ? b(ω/y )c(y ) must vanish identically (that is, coef?cient by coef?cient). If one of the polynomials, say a, vanished identically, then one of b or c would also, and the desired inequality could not hold. So none of them vanish identically, and we can write c(y ) a(ω/y ) = . d(y ) b(ω/y ) Likewise, a(ω /y ) c(y ) = . d(y ) b(ω 2 /y ) Put f (x) = a(x)/b(x); then we have f (ωx) = f (x) identically. That is, a(x)b(ωx) = b(x)a(ωx). Since a and b have no common factor (otherwise 1 + xy + x2 y 2 would have a factor divisible only by x, which it doesn’t since it doesn’t vanish identically for any particular x), a(x) divides a(ωx). Since they have the same degree, they are equal up to scalars. It follows that one of a(x), xa(x), x2 a(x) is a polynomial in x3 alone, and likewise for b (with the same power of x). If xa(x) and xb(x), or x2 a(x) and x2 b(x), are polynomials in x3 , then a and b are divisible by x, but we know a and b have no common factor. Hence a(x) and b(x) are polynomials in x3 . Likewise, c(y ) and d(y ) are polynomials in y 3 . But then 1 + xy + x2 y 2 = a(x)d(y ) ? b(x)c(y ) is a polynomial in x3 and y 3 , contradiction. Note: The third solution only works over ?elds of characteristic not equal to 3, whereas the other two work over arbitrary ?elds. (In the ?rst solution, one must replace ?1 by another value if working in characteristic 2.) B2 It is easy to see by induction that the j -th entry of the k -th sequence (where the original sequence is k = k ?1 k ?1 1) is i=1 k (i + j ? 1)), and so xn = i?1 /(2 n n?1 n?1 n 1 i=1 i?1 /i. Now i?1 /i = i /n; hence 2n?1 xn = 1 n2n?1

n 2

B3 First solution: It is enough to show that for each prime p, the exponent of p in the prime factorization of both sides is the same. On the left side, it is well-known that the exponent of p in the prime factorization of n! is

n

i=1

n . pi

(To see this, note that the i-th term counts the multiples of pi among 1, . . . , n, so that a number divisible exactly by pi gets counted exactly i times.) This number can be reinterpreted as the cardinality of the set S of points in the plane with positive integer coordinates lying on or under the curve y = np?x : namely, each summand is the number of points of S with x = i. On the right side, the exponent of p in the prime factorization of lcm(1, . . . , n/i ) is logp n/i = logp (n/i) . However, this is precisely the number of points of S with y = i. Thus

n n

logp n/i

i=1

=

i=1

n , pi

and the desired result follows. Second solution: We prove the result by induction on n, the case n = 1 being obvious. What we actually show is that going from n ? 1 to n changes both sides by the same multiplicative factor, that is,

n?1

n=

i=1

lcm{1, 2, . . . , n/i } . lcm{1, 2, . . . , (n ? 1)/i }

Note that the i-th term in the product is equal to 1 if n/i is not an integer, i.e., if n/i is not a divisor of n. It is also equal to 1 if n/i is a divisor of n but not a prime power, since any composite number divides the lcm of all smaller numbers. However, if n/i is a power of p, then the i-th term is equal to p. Since n/i runs over all proper divisors of n, the product on the right side includes one factor of the prime p for each factor of p in the prime factorization of n. Thus the whole product is indeed equal to n, completing the induction. B4 First solution: Put g = r1 + r2 , h = r3 + r4 , u = r1 r2 , v = r3 r4 . We are given that g is rational. The following are also rational: ?b =g+h a c = gh + u + v a ?d = gv + hu a From the ?rst line, h is rational. From the second line, u + v is rational. From the third line, g (u + v ) ? (gv +

i=1

n i

=

2n ? 1 < 2/n, n2n?1

as desired.

6 hu) = (g ? h)u is rational. Since g = h, u is rational, as desired. Second solution: This solution uses some basic Galois theory. We may assume r1 = r2 , since otherwise they are both rational and so then is r1 r2 . Let τ be an automorphism of the ?eld of algebraic numbers; then τ maps each ri to another one, and ?xes the rational number r1 + r2 . If τ (r1 ) equals one of r1 or r2 , then τ (r2 ) must equal the other one, and vice versa. Thus τ either ?xes the set {r1 , r2 } or moves it to {r3 , r4 }. But if the latter happened, we would have r1 + r2 = r3 + r4 , contrary to hypothesis. Thus τ ?xes the set {r1 , r2 } and in particular the number r1 r2 . Since this is true for any τ , r1 r2 must be rational. Note: The conclusion fails if we allow r1 +r2 = r3 +r4 . For instance, take the polynomial x4 ? 2√ and label its 2 roots so that (x ? r1 )( x ? r ) = x ? 2 and (x ? 2 √ r3 )(x ? r4 ) = x2 + 2. B5 First solution: Place the unit circle on the complex plane so that A, B, C correspond to the complex numbers 1, ω, ω 2 , where ω = e2πi/3 , and let P correspond to the complex number x. The distances a, b, c are then |x ? 1|, |x ? ω |, |x ? ω 2 |. Now the identity (x ? 1) + ω (x ? ω ) + ω (x ? ω ) = 0 implies that there is a triangle whose sides, as vectors, correspond to the complex numbers x ? 1, ω (x ? ω ), ω 2 (x ? ω 2 ); this triangle has sides of length a, b, c. To calculate the area of this triangle, we ?rst note a more general formula. If a triangle in the plane has vertices at 0, v1 = s1 + it1 , v2 = s2 + it2 , then it is well known that the area of the triangle is |s1 t2 ? s2 t1 |/2 = |v1 v2 ? v2 v1 |/4. In our case, we have v1 = x ? 1 and v2 = ω (x ? ω ); then √ v1 v2 ? v2 v1 = (ω 2 ? ω )(xx ? 1) = i 3(|x|2 ? 1). √ Hence the area of the triangle is 3(1 ? |x|2 )/4, which depends only on the distance |x| from P to O. Second solution: (by Florian Herzig) Let A , B , C be the points obtained by intersection the lines AP , BP , CP with the unit circle. Let d denote OP . Then A P = (1 ? d2 )/a, etc., by using the power of the point P . As triangles A B P and BAP are similar, we get √ that A B = AB · A P/b = 3(1 ? d2 )/(ab). It follows that triangle A √ B C has sides proportional to a, b, c, by a factor of 3(1 ? d2 )/(abc). In particular, the triangle there is a triangle with √ sides2a, b, c, and it has circumradius R = ( abc ) / ( 3(1 ? d )). Its area is √ 2 abc/(4R) = 3(1 ? d )/4. B6 First solution: (composite of solutions by Feng Xie and David Pritchard) Let ? denote Lebesgue measure on [0, 1]. De?ne E+ = {x ∈ [0, 1] : f (x) ≥ 0} E? = {x ∈ [0, 1] : f (x) < 0};

2 2

then E+ , E? are measurable and ?(E+ ) + ?(E? ) = 1. Write ?+ and ?? for ?(E+ ) and ?(E? ). Also de?ne I+ =

E+

|f (x)| dx |f (x)| dx,

E?

I? = so that

1 0

|f (x)| dx = I+ + I? .

From the triangle inequality |a + b| ≥ ±(|a| ? |b|), we have the inequality |f (x) + f (y )| dx dy

E+ ×E?

≥±

E+ ×E?

(|f (x)| ? |f (y )|) dx dy

= ±(?? I+ ? ?+ I? ), and likewise with + and ? switched. Adding these inequalities together and allowing all possible choices of the signs, we get |f (x) + f (y )| dx dy

(E+ ×E? )∪(E? ×E+ )

≥ max {0, 2(?? I+ ? ?+ I? ), 2(?+ I? ? ?? I+ )} . To this inequality, we add the equalities |f (x) + f (y )| dx dy = 2?+ I+

E+ ×E+

|f (x) + f (y )| dx dy = 2?? I?

E? ×E? 1

?

0

|f (x)| dx = ?(?+ + ?? )(I+ + I? )

to obtain

1 0 0 1 1

|f (x) + f (y )| dx dy ?

0

|f (x)| dx

≥ max{(?+ ? ?? )(I+ + I? ) + 2?? (I? ? I+ ), (?+ ? ?? )(I+ ? I? ), (?? ? ?+ )(I+ + I? ) + 2?+ (I+ ? I? )}. Now simply note that for each of the possible comparisons between ?+ and ?? , and between I+ and I? , one of the three terms above is manifestly nonnegative. This yields the desired result. Second solution: We will show at the end that it is enough to prove a discrete analogue: if x1 , . . . , xn are real numbers, then 1 n2

n

|xi + xj | ≥

i,j =1

1 n

n

|xi |.

i=1

In the meantime, we concentrate on this assertion.

7 Let f (x1 , . . . , xn ) denote the difference between the two sides. We induct on the number of nonzero values of |xi |. We leave for later the base case, where there is at most one such value. Suppose instead for now that there are two or more. Let s be the smallest, and suppose without loss of generality that x1 = · · · = xa = s, xa+1 = · · · = xa+b = ?s, and for i > a + b, either xi = 0 or |xi | > s. (One of a, b might be zero.) Now consider a terms b terms f (t, · · · , t, ?t, · · · , ?t, xa+b+1 , · · · , xn ) as a function of t. It is piecewise linear near s; in fact, it is linear between 0 and the smallest nonzero value among |xa+b+1 |, . . . , |xn | (which exists by hypothesis). Thus its minimum is achieved by one (or both) of those two endpoints. In other words, we can reduce the number of distinct nonzero absolute values among the xi without increasing f . This yields the induction, pending veri?cation of the base case. As for the base case, suppose that x1 = · · · = xa = s > 0, xa+1 = · · · = xa+b = ?s, and xa+b+1 = · · · = xn = 0. (Here one or even both of a, b could be zero, though the latter case is trivial.) Then s f (x1 , . . . , xn ) = 2 (2a2 + 2b2 + (a + b)(n ? a ? b)) n s ? (a + b) n s = 2 (a2 ? 2ab + b2 ) n ≥ 0. This proves the base case of the induction, completing the solution of the discrete analogue. To deduce the original statement from the discrete analogue, approximate both integrals by equally-spaced Riemann sums and take limits. This works because given a continuous function on a product of closed intervals, any sequence of Riemann sums with mesh size tending to zero converges to the integral. (The domain is compact, so the function is uniformly continuous. Hence for any > 0 there is a cutoff below which any mesh size forces the discrepancy between the Riemann sum and the integral to be less than .) Alternate derivation (based on a solution by Dan Bernstein): from the discrete analogue, we have |f (xi ) + f (xj )| ≥

1≤i<j ≤n

or

1 0 0 1

|f (x) + f (y )| dy dx ≥

n?2 n?1

1

|f (x)| dx.

0

Taking the limit as n → ∞ now yields the desired result. Third solution: (by David Savitt) We give an argument which yields the following improved result. Let ?p and ?n be the measure of the sets {x : f (x) > 0} and {x : f (x) < 0} respectively, and let ? ≤ 1/2 be min(?p , ?n ). Then

1 0 0 1 1

|f (x) + f (y )| dx dy ≥ (1 + (1 ? 2?)2 )

0

|f (x)| dx.

Note that the constant can be seen to be best possible by considering a sequence of functions tending towards the step function which is 1 on [0, ?] and ?1 on (?, 1]. Suppose without loss of generality that ? = ?p . As in the second solution, it suf?ces to prove a strengthened discrete analogue, namely 1 n2 |ai + aj | ≥

i,j

1+ 1?

2p n

2

1 n

n

|ai | ,

i=1

where p ≤ n/2 is the number of a1 , . . . , an which are positive. (We need only make sure to choose meshes so that p/n → ? as n → ∞.) An equivalent inequality is |ai + aj | ≥

1≤i<j ≤n

n ? 1 ? 2p +

2p2 n

n

|ai |.

i=1

Write ri = |ai |, and assume without loss of generality that ri ≥ ri+1 for each i. Then for i < j , |ai + aj | = ri + rj if ai and aj have the same sign, and is ri ? rj if they have opposite signs. The left-hand side is therefore equal to

n n

(n ? i)ri +

i=1 j =1

rj Cj ,

where Cj = #{i < j : sgn(ai ) = sgn(aj )} ? #{i < j : sgn(ai ) = sgn(aj )}. Consider the partial sum Pk = j =1 Cj . If exactly pk of a1 , . . . , ak are positive, then this sum is equal to pk 2 + k ? pk 2 ? k pk ? 2 2 ? k ? pk 2 ,

k

n?2 2

n

|f (xi )|,

i=1

for all x1 , . . . , xn ∈ [0, 1]. Integrating both sides as (x1 , . . . , xn ) runs over [0, 1]n yields n(n ? 1) 2 ≥

1 0 1

|f (x) + f (y )| dy dx

0 1

which expands and simpli?es to ?2pk (k ? pk ) + k . 2

n(n ? 2) 2

|f (x)| dx,

0

8 For k ≤ 2p even, this partial sum would be minimized k with pk = k 2 , and would then equal ? 2 ; for k < 2p odd, this partial sum would be minimized with pk = k±1 k ?1 2 , and would then equal ? 2 . Either way, Pk ≥ k ? 2 . On the other hand, if k > 2p, then ?2pk (k ? pk ) + k 2 ≥ ?2p(k ? p) + k 2 as desired. The next-to-last and last inequalities each follow from the monotonicity of the ri ’s, the former by pairing the ith term with the (2p + 1 ? i)th .

since pk is at most p. De?ne Qk to be ? k 2 if k ≤ 2p k and ?2p(k ? p) + 2 if k ≥ 2p, so that Pk ≥ Qk . Note that Q1 = 0. Partial summation gives

n n

rj Cj = rn Pn +

j =1 j =2 n

(rj ?1 ? rj )Pj ?1 (rj ?1 ? rj )Qj ?1

j =2

Note: Compare the closely related Problem 6 from the 2000 USA Mathematical Olympiad: prove that for any nonnegative real numbers a1 , . . . , an , b1 , . . . , bn , one has

≥ rn Qn +

n

=

j =2

rj (Qj ? Qj ?1 )

= ?r2 ? r4 ? · · · ? r2p

n

+ It follows that

n

(j ? 1 ? 2p)rj .

j =2p+1

n

n

n

|ai + aj | =

1≤i<j ≤n i=1 2p

(n ? i)ri +

j =1

rj Cj

i,j =1

min{ai aj , bi bj } ≤

i,j =1

min{ai bj , aj bi }.

≥

i=1

(n ? i ? [i even])ri

n

+

(n ? 1 ? 2p)ri

i=2p+1 n

= (n ? 1 ? 2p)

i=1 2p

ri +

(2p + 1 ? i ? [i even])ri

i=1 n 2p

≥ (n ? 1 ? 2p)

i=1 n

ri + p

i=1

ri

n

2p ≥ (n ? 1 ? 2p) ri + p n i=1

ri ,

i=1

The 65th William Lowell Putnam Mathematical Competition Saturday, December 4, 2004

A1 Basketball star Shanille O’Keal’s team statistician keeps track of the number, S (N ), of successful free throws she has made in her ?rst N attempts of the season. Early in the season, S (N ) was less than 80% of N , but by the end of the season, S (N ) was more than 80% of N . Was there necessarily a moment in between when S (N ) was exactly 80% of N ? A2 For i = 1, 2 let Ti be a triangle with side lengths ai , bi , ci , and area Ai . Suppose that a1 ≤ a2 , b1 ≤ b2 , c1 ≤ c2 , and that T2 is an acute triangle. Does it follow that A1 ≤ A2 ? A3 De?ne a sequence {un }∞ n=0 by u0 = u1 = u2 = 1, and thereafter by the condition that det un un+1 un+2 un+3 = n! B1 Let P (x) = cn xn + cn?1 xn?1 + · · · + c0 be a polynomial with integer coef?cients. Suppose that r is a rational number such that P (r) = 0. Show that the n numbers cn r, cn r2 + cn?1 r, cn r3 + cn?1 r2 + cn?2 r, . . . , cn rn + cn?1 rn?1 + · · · + c1 r are integers. B2 Let m and n be positive integers. Show that (m + n)! m! n! < m n. (m + n)m+n m n B3 Determine all real numbers a > 0 for which there exists a nonnegative continuous function f (x) de?ned on [0, a] with the property that the region R = {(x, y ); 0 ≤ x ≤ a, 0 ≤ y ≤ f (x)} has perimeter k units and area k square units for some real number k . B4 Let n be a positive integer, n ≥ 2, and put θ = 2π/n. De?ne points Pk = (k, 0) in the xy -plane, for k = 1, 2, . . . , n. Let Rk be the map that rotates the plane counterclockwise by the angle θ about the point Pk . Let R denote the map obtained by applying, in order, R1 , then R2 , . . . , then Rn . For an arbitrary point (x, y ), ?nd, and simplify, the coordinates of R(x, y ). B5 Evaluate

∞ x→1?

for all n ≥ 0. Show that un is an integer for all n. (By convention, 0! = 1.) A4 Show that for any positive integer n, there is an integer N such that the product x1 x2 · · · xn can be expressed identically in the form

N

x1 x2 · · · xn =

i=1

ci (ai1 x1 + ai2 x2 + · · · + ain xn )n

where the ci are rational numbers and each aij is one of the numbers ?1, 0, 1. A5 An m × n checkerboard is colored randomly: each square is independently assigned red or black with probability 1/2. We say that two squares, p and q , are in the same connected monochromatic component if there is a sequence of squares, all of the same color, starting at p and ending at q , in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater than mn/8. A6 Suppose that f (x, y ) is a continuous real-valued function on the unit square 0 ≤ x ≤ 1, 0 ≤ y ≤ 1. Show that

1 0 0 1 1 2 1 2 1 1 2

lim

n=0

1 + xn+1 1 + xn

xn

.

f (x, y )dx ≤

0 0

dy +

0 1 0

f (x, y )dy

1 0

dx

2

B6 Let A be a non-empty set of positive integers, and let N (x) denote the number of elements of A not exceeding x. Let B denote the set of positive integers b that can be written in the form b = a ? a with a ∈ A and a ∈ A. Let b1 < b2 < · · · be the members of B , listed in increasing order. Show that if the sequence bi+1 ? bi is unbounded, then

x→∞

lim N (x)/x = 0.

f (x, y )dx dy

+

0

(f (x, y )) dx dy.

Solutions to the 65th William Lowell Putnam Mathematical Competition Saturday, December 4, 2004

Kiran Kedlaya and Lenny Ng

A1 Yes. Suppose otherwise. Then there would be an N such that S (N ) < 80% and S (N + 1) > 80%; that is, O’Keal’s free throw percentage is under 80% at some point, and after one subsequent free throw (necessarily made), her percentage is over 80%. If she makes m of her ?rst N free throws, then m/N < 4/5 and (m + 1)/(N + 1) > 4/5. This means that 5m < 4n < 5m + 1, which is impossible since then 4n is an integer between the consecutive integers 5m and 5m + 1. Remark: This same argument works for any fraction of the form (n ? 1)/n for some integer n > 1, but not for any other real number between 0 and 1. A2 First solution: (partly due to Ravi Vakil) Yes, it does follow. For i = 1, 2, let Pi , Qi , Ri be the vertices of Ti opposide the sides of length ai , bi , ci , respectively. We ?rst check the case where a1 = a2 (or b1 = b2 or c1 = c2 , by the same argument after relabeling). Imagine T2 as being drawn with the base Q2 R2 horizontal and the point P2 above the line Q2 R2 . We may then position T1 so that Q1 = Q2 , R1 = R2 , and P1 lies above the line Q1 R1 = Q2 R2 . Then P1 also lies inside the region bounded by the circles through P2 centered at Q2 and R2 . Since ∠Q2 and ∠R2 are acute, the part of this region above the line Q2 R2 lies within T2 . In particular, the distance from P1 to the line Q2 R2 is less than or equal to the distance from P2 to the line Q2 R2 ; hence A1 ≤ A2 . To deduce the general case, put r = max{a1 /a2 , b1 /b2 , c1 /c2 }. Let T3 be the triangle with sides ra2 , rb2 , rc2 , which has area r2 A2 . Applying the special case to T1 and T3 , we deduce that A1 ≤ r2 A2 ; since r ≤ 1 by hypothesis, we have A1 ≤ A2 as desired. Remark: Another geometric argument in the case a1 = a2 is that since angles ∠Q2 and ∠R2 are acute, the perpendicular to Q2 R2 through P2 separates Q2 from R2 . If A1 > A2 , then P1 lies above the parallel to Q2 R2 through P2 ; if then it lies on or to the left of the vertical line through P2 , we have c1 > c2 because the inequality holds for both horizontal and vertical components (possibly with equality for one, but not both). Similarly, if P1 lies to the right of the vertical, then b1 > b2 . Second solution: (attribution unknown) Retain notation as in the ?rst paragraph of the ?rst solution. Since the angle measures in any triangle add up to π , some angle of T1 must have measure less than or equal to its counterpart in T2 . Without loss of generality assume that ∠P1 ≤ ∠P2 . Since the latter is acute (because T2

is acute), we have sin ∠P1 ≤ sin ∠P2 . By the Law of Sines, A1 = 1 1 b1 c1 sin ∠P1 ≤ b2 c2 sin ∠P2 = A2 . 2 2

Remark: Many other solutions are possible; for instance, one uses Heron’s formula for the area of a triangle in terms of its side lengths. A3 De?ne a sequence vn by vn = (n ? 1)(n ? 3) · · · (4)(2) if n is odd and vn = (n ? 1)(n ? 3) · · · (3)(1) if n is even; it suf?ces to prove that un = vn for all n ≥ 2. Now vn+3 vn = (n + 2)(n)(n ? 1)! and vn+2 vn+1 = (n + 1)!, and so vn+3 vn ? vn+2 vn+1 = n!. Since we can check that un = vn for n = 2, 3, 4, and un and vn satisfy the same recurrence, it follows by induction that un = vn for all n ≥ 2, as desired. A4 It suf?ces to verify that x1 · · · xn 1 = n 2 n!

(e1 · · · en )(e1 x1 + · · · + en xn )n .

ei ∈{?1,1}

To check this, ?rst note that the right side vanishes identically for x1 = 0, because each term cancels the corresponding term with e1 ?ipped. Hence the right side, as a polynomial, is divisible by x1 ; similarly it is divisible by x2 , . . . , xn . Thus the right side is equal to x1 · · · xn times a scalar. (Another way to see this: the right side is clearly odd as a polynomial in each individual variable, but the only degree n monomial in x1 , . . . , xn with that property is x1 · · · xn .) Since each summand contributes 1 2n x1 · · · xn to the sum, the scalar factor is 1 and we are done. Remark: Several variants on the above construction are possible; for instance, x1 · · · xn 1 = n!

(?1)n?e1 ?···?en (e1 x1 + · · · + en xn )n

ei ∈{0,1}

by the same argument as above. Remark: These construction work over any ?eld of characteristic greater than n (at least for n > 1). On the other hand, no construction is possible over a ?eld of characteristic p ≤ n, since the coef?cient of x1 · · · xn in the expansion of (e1 x1 + · · · + en xn )n is zero for any ei . Remark: Richard Stanley asks whether one can use fewer than 2n terms, and what the smallest possible number is.

2 A5 First solution: First recall that any graph with n vertices and e edges has at least n ? e connected components (add each edge one at a time, and note that it reduces the number of components by at most 1). Now imagine the squares of the checkerboard as a graph, whose vertices are connected if the corresponding squares share a side and are the same color. Let A be the number of edges in the graph, and let B be the number of 4-cycles (formed by monochromatic 2 × 2 squares). If we remove the bottom edge of each 4-cycle, the resulting graph has the same number of connected components as the original one; hence this number is at least mn ? A + B. By the linearity of expectation, the expected number of connected components is at least mn ? E (A) + E (B ). Moreover, we may compute E (A) by summing over the individual pairs of adjacent squares, and we may compute E (B ) by summing over the individual 2 × 2 squares. Thus 1 E (A) = (m(n ? 1) + (m ? 1)n), 2 1 E (B ) = (m ? 1)(n ? 1), 8 and so the expected number of components is at least 1 1 mn ? (m(n ? 1) + (m ? 1)n) + (m ? 1)(n ? 1) 2 8 mn + 3m + 3n + 1 mn = > . 8 8 Remark: A “dual” approach is to consider the graph whose vertices are the corners of the squares of the checkerboard, with two vertices joined if they are adjacent and the edge between then does not separate two squares of the same color. In this approach, the 4-cycles become isolated vertices, and the bound on components is replaced by a call to Euler’s formula relating the vertices, edges and faces of a planar ?gure. (One must be careful, however, to correctly handle faces which are not simply connected.) Second solution: (by Noam Elkies) Number the squares of the checkerboard 1, . . . , mn by numbering the ?rst row from left to right, then the second row, and so on. We prove by induction on i that if we just consider the ?gure formed by the ?rst i squares, its expected number of monochromatic components is at least i/8. For i = 1, this is clear. Suppose the i-th square does not abut the left edge or the top row of the board. Then we may divide into three cases. – With probability 1/4, the i-th square is opposite in color from the adjacent squares directly above and to the left of it. In this case adding the i-th square adds one component. – With probability 1/8, the i-th square is the same in color as the adjacent squares directly above and to the left of it, but opposite in color from its diagonal neighbor above and to the left. In this case, adding the i-th square either removes a component or leaves the number unchanged. – In all other cases, the number of components remains unchanged upon adding the i-th square. Hence adding the i-th square increases the expected number of components by 1/4 ? 1/8 = 1/8. If the i-th square does abut the left edge of the board, the situation is even simpler: if the i-th square differs in color from the square above it, one component is added, otherwise the number does not change. Hence adding the i-th square increases the expected number of components by 1/2; likewise if the i-th square abuts the top edge of the board. Thus the expected number of components is at least i/8 by induction, as desired. Remark: Some solvers attempted to consider adding one row at a time, rather than one square; this must be handled with great care, as it is possible that the number of components can drop rather precipitously upon adding an entire row. A6 By approximating each integral with a Riemann sum, we may reduce to proving the discrete analogue: for xij ∈ R for i, j = 1, . . . , n,

n

n

i=1

? ?

n j =1 n

The difference between the right side and the left side is 1 4

n

≤?

?

xij ? + n

n

?2

n j =1

n

2

xij

i=1 n n

i=1 j =1

xij ? + n2

?2

x2 ij .

i=1 j =1

(xij + xkl ? xil ? xkj )2 ,

i,j,k,l=1

which is evidently nonnegative. If you prefer not to discretize, you may rewrite the original inequality as

1 0 0 1 0 1 0 1

F (x, y, z, w)2 dx dy dz dw ≥ 0

for F (x, y, z, w) = f (x, y ) + f (z, w) ? f (x, w) ? f (z, y ).

3 Remark: (by Po-Ning Chen) The discrete inequality can be arrived at more systematically by repeatedly applying the following identity: for any real a1 , . . . , an ,

n n 2

(m + n)!/(m + n)m+n . On the other hand, if p is the probability of picking exactly m red balls, then p < 1 and the probability of picking each ball exactly once is p(mm /m!)(nn /n!). Second solution: (by David Savitt) De?ne Sk = {i/k : i = 1, . . . , k } and rewrite the desired inequality as x

x ∈Sm y ∈Sn

(xi ? xj ) = n

1≤i<j ≤n i=1

2

x2 i

?

i=1

xi

.

Remark: (by David Savitt) The discrete inequality can also be interpreted as follows. For c, d ∈ {1, . . . , n ? 1} and ζn = e2πi/n , put zc,d =

i,j ci+dj ζn xij .

y>

z ∈ S m+ n

z.

Then the given inequality is equivalent to

n?1

To prove this, it suf?ces to check that if we sort the multiplicands on both sides into increasing order, the ith term on the left side is greater than or equal to the i-th term on the right side. (The equality is strict already for i = 1, so you do get a strict inequality above.) Another way to say this is that for any i, the number of factors on the left side which are less than i/(m + n) is less than i. But since j/m < i/(m + n) is equivalent to j < im/(m + n), that number is im in ?1+ ?1 m+n m+n im in ≤ + ? 1 = i ? 1. m+n m+n Third solution: Put f (x) = x(log(x +1) ? log x); then for x > 0, f ′ (x) = log(1 + 1/x) ? f ′′ (x) = ? 1 . x(x + 1)2 1 x+1

|zc,d |2 ≥ 0.

c,d=1

B1 Let k be an integer, 0 ≤ k ≤ n ? 1. Since P (r)/rk = 0, we have cn r

n?k

+ cn?1 r

n?k+1 ?1

+ · · · + ck+1 r

= ?(ck + ck?1 r

+ · · · + c0 r?k ).

Write r = p/q where p and q are relatively prime. Then the left hand side of the above equation can be written as a fraction with denominator q n?k , while the right hand side is a fraction with denominator pk . Since p and q are relatively prime, both sides of the equation must be an integer, and the result follows. Remark: If we write r = a/b in lowest terms, then P (x) factors as (bx ? a)Q(x), where the polynomial Q has integer coef?cients because you can either do the long division from the left and get denominators divisible only by primes dividing b, or do it from the right and get denominators divisible only by primes dividing a. The numbers given in the problem are none other than a times the coef?cients of Q. More generally, if P (x) is divisible, as a polynomial over the rationals, by a polynomial R(x) with integer coef?cients, then P/R also has integer coef?cients; this is known as “Gauss’s lemma” and holds in any unique factorization domain. B2 First solution: We have (m + n)m+n > m+n mm n n m

Hence f ′′ (x) < 0 for all x; since f ′ (x) → 0 as x → ∞, we have f ′ (x) > 0 for x > 0, so f is strictly increasing. Put g (m) = m log m ? log(m!); then g (m + 1) ? g (m) = f (m), so g (m + 1) ? g (m) increases with m. By induction, g (m + n) ? g (m) increases with n for any positive integer n, so in particular g (m + n) ? g (m) > g (n) ? g (1) + f (m) ≥ g (n) since g (1) = 0. Exponentiating yields the desired inequality. Fourth solution: (by W.G. Boskoff and Bogdan Suceava) We prove the claim by induction on m + n. The base case is m = n = 1, in which case the desired inequality is obviously true: 2!/22 = 1/2 < 1 = (1!/11 )(1!/11 ). To prove the induction step, suppose m + n > 2; we must then have m > 1 or n > 1 or both. Because the desired result is symmetric in m and n, we may as well assume n > 1. By the induction hypothesis, we have (m + n ? 1)! m! (n ? 1)! < m . (m + n ? 1)m+n?1 m (n ? 1)n?1

because the binomial expansion of (m + n)m+n includes the term on the right as well as some others. Rearranging this inequality yields the claim. Remark: One can also interpret this argument combinatorially. Suppose that we choose m + n times (with replacement) uniformly randomly from a set of m + n balls, of which m are red and n are blue. Then the probability of picking each ball exactly once is

4 To obtain the desired inequality, it will suf?ce to check that (n ? 1)n?1 n! (m + n ? 1)m+n?1 (m + n)! < m + n (m + n ? 1)! (m + n) (n ? 1)! (n)n or in other words 1? 1 m+n

m+n?1

units to the right. Hence the whole plane must do so as well. Third solution: (attribution unknown) Viewing each Rk as a function of a complex number z as in the ?rst solution, the function Rn ? Rn?1 ? · · · ? R1 (z ) is linear in z with slope ζ n = 1. It thus equals z + T for some T ∈ C. Since f1 (1) = 1, we can write 1 + T = Rn ? · · · ? R2 (1). However, we also have Rn ? · · · ? R2 (1) = Rn?1 ? R1 (0) + 1 by the symmetry in how the Ri are de?ned. Hence Rn (1 + T ) = Rn ? R1 (0) + Rn (1) = T + Rn (1); that is, Rn (T ) = T . Hence T = n, as desired. B5 First solution: By taking logarithms, we see that the desired limit is exp(L), where L = ∞ limx→1? n=0 xn ln(1 + xn+1 ) ? ln(1 + xn ) . Now

N

<

1?

1 n

n?1

.

To show this, we check that the function f (x) = (1 ? 1/x)x?1 is strictly decreasing for x > 1; while this can be achieved using the weighted arithmetic-geometric mean inequality, we give a simple calculus proof instead. The derivative of log f (x) is log(1 ? 1/x) + 1/x, so it is enough to check that this is negative for x > 1. An equivalent statement is that log(1 ? x) + x < 0 for 0 < x < 1; this in turn holds because the function g (x) = log(1 ? x) + x tends to 0 as x → 0+ and has 1 derivative 1 ? 1? x < 0 for 0 < x < 1. B3 The answer is {a | a > 2}. If a > 2, then the function f (x) = 2a/(a ? 2) has the desired property; both perimeter and area of R in this case are 2a2 /(a ? 2). Now suppose that a ≤ 2, and let f (x) be a nonnegative continuous function on [0, a]. Let P = (x0 , y0 ) be a point on the graph of f (x) with maximal y -coordinate; then the area of R is at most ay0 since it lies below the line y = y0 . On the other hand, the points (0, 0), (a, 0), and P divide the boundary of R into three sections. The length of the section between (0, 0) and P is at least the distance between (0, 0) and P , which is at least y0 ; the length of the section between P and (a, 0) is similarly at least y0 ; and the length of the section between (0, 0) and (a, 0) is a. Since a ≤ 2, we have 2y0 + a > ay0 and hence the perimeter of R is strictly greater than the area of R. B4 First solution: Identify the xy -plane with the complex plane C, so that Pk is the real number k . If z is sent to z ′ by a counterclockwise rotation by θ about Pk , then z ′ ? k = eiθ (z ? k ); hence the rotation Rk sends z to ζz + k (1 ? ζ ), where ζ = e2πi/n . It follows that R1 followed by R2 sends z to ζ (ζz + (1 ? ζ )) + 2(1 ? ζ ) = ζ 2 z + (1 ? ζ )(ζ + 2), and so forth; an easy induction shows that R sends z to ζ n z + (1 ? ζ )(ζ n?1 + 2ζ n?2 + · · · + (n ? 1)ζ + n). Expanding the product (1 ? ζ )(ζ n?1 + 2ζ n?2 + · · · + (n ? 1)ζ + n) yields ?ζ n ? ζ n?1 ? · · · ? ζ + n = n. Thus R sends z to z + n; in cartesian coordinates, R(x, y ) = (x + n, y ). Second solution: (by Andy Lutomirski, via Ravi Vakil) Imagine a regular n-gon of side length 1 placed with its top edge on the x-axis and the left endpoint of that edge at the origin. Then the rotations correspond to rolling this n-gon along the x-axis; after the n rotations, it clearly ends up in its original rotation and translated n

xn ln(1 + xn+1 ) ? ln(1 + xn )

n=0 N N

= 1/x

n=0

x

n+1

ln(1 + x

n+1

)?

n=0

xn ln(1 + xn )

N

= xN ln(1 + xN +1 ) ? ln 2 + (1/x ? 1)

n=1

xn ln(1 + xn );

since limN →∞ (xN ln(1 + xN +1 )) = 0 for 0 < x < 1, we conclude that L = ? ln 2 + limx→1? f (x), where

∞

f (x) = (1/x ? 1) = (1/x ? 1)

xn ln(1 + xn )

n=1 ∞ ∞

(?1)m+1 xn+mn /m.

n=1 m=1

This ?nal double sum converges absolutely when 0 < x < 1, since

∞ ∞ ∞

xn+mn /m =

n=1 m=1 n=1 ∞

xn (? ln(1 ? xn )) xn (? ln(1 ? x)),

n=1

<

which converges. (Note that ? ln(1 ? x) and ? ln(1 ? xn ) are positive.) Hence we may interchange the summations in f (x) to obtain f (x) = (1/x ? 1) = (1/x ? 1) (?1)m+1 x(m+1)n m m=1 n=1 (?1)m+1 m m=1

∞ ∞ ∞

xm (1 ? x) 1 ? xm+1

.

5 This last sum converges absolutely uniformly in x, so it is legitimate to take limits term by term. Since xm 1?x limx→1? 1 = m1 m +1 ?x +1 for ?xed m, we have (?1)m+1 lim f (x) = m(m + 1) x→1? m=1

∞ ∞

where each ei runs over {0, 1}, contains at most one element of A; consequently, lim sup N (x)/x ≤ 1/2n. We now produce such bi recursively, starting with b0 = 1 (and both (a) and (b) holding vacuously). Given b0 , . . . , bn satisfying (a) and (b), note that b0 + · · · + bn?1 < bn by induction on n. By the hypotheses of the problem, we can ?nd a set Sn of 6bn consecutive integers, none of which belongs to B . Let bn+1 be the second-smallest multiple of 2bn in Sn ; then bn+1 + x ∈ Sn for ?2bn ≤ x ≤ 0 clearly, and also for 0 ≤ x ≤ 2bn because there are most 4bn ? 1 elements of Sn preceding bn+1 . In particular, the analogue of (b) with n replaced by n + 1 holds for en+1 = 0; of course it holds for en+1 = 0 because (b) was already known. Since the analogue of (a) holds by construction, we have completed this step of the construction and the recursion may continue. Since we can construct b0 , . . . , bn satisfying (a) and (b) for any n, we have lim sup N (x)/x ≤ 1/2n for any n, yielding lim N (x)/x = 0 as desired. Second solution: (by Paul Pollack) Let S be the set of possible values of lim sup N (x)/x; since S ? [0, 1] is bounded, it has a least upper bound L. Suppose by way of contradiction that L > 0; we can then choose A, B satisfying the conditions of the problem such that lim sup N (x)/x > 3L/4. To begin with, we can certainly ?nd some positive integer m ∈ / B , so that A is disjoint from A + m = {a + m : a ∈ A}. Put A′ = A∪(A+m) and let N ′ (x) be the size of A′ ∩{1, . . . , x}; then lim sup N ′ (x)/x = 3L/2 > L, so A′ cannot obey the conditions of the problem statement. That is, if we let B ′ be the set of positive integers that occur as differences between elements of A′ , then there exists an integer n such that among any n consecutive integers, at least one lies in B ′ . But B ′ ? {b + em : b ∈ B , e ∈ {?1, 0, 1}}, so among any n + 2m consecutive integers, at least one lies in B . This contradicts the condition of the problem statement. We conclude that it is impossible to have L > 0, so L = 0 and lim N (x)/x = 0 as desired. Remark: A hybrid between these two arguments is to note that if we can produce c1 , . . . , cn such that |c i ? c j | ∈ / B for i, j = 1, . . . , n, then the translates A + c1 , . . . , A + cn are disjoint and so lim sup N (x)/x ≤ 1/n. Given c1 ≤ · · · ≤ cn as above, we can then choose cn+1 to be the largest element of a run of cn + 1 consecutive integers, none of which lie in B .

= =2

(?1)m+1

m=1 ∞

1 1 ? m m+1 ?1

(?1)m+1 m m=1

= 2 ln 2 ? 1, and henc

相关文章:

更多相关标签: