首页 1998s

1998s

1998s 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...

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 rect- angle lies on the base of the triangle.) Similar triangles yield �� , or � �� A–2 First solution: to fix notation, let ﬀ be the area of re- gion ﬁﬃﬂ��! , and " be the area of ﬁﬃﬂ$#�% ; further let & denote the area of sector '(ﬁﬃﬂ , which only depends on the arc length of � . If ) *,+.-0/ denotes the area of tri- angle ) *1+.- / , then we have ﬀ2� &43 ) '(ﬂ� 5/6�4) '(ﬁﬃ�5/ and "7� &83 ) '(ﬁﬃ%9/:�;) '(ﬂ�#� ) '(ﬁﬃ%?/ , and so ﬀ 3 "@� � & . O D E F G H I Second solution: We may parametrize a point in � by any of A , B , or CD�FE�GK��LB � A � . Then ﬀ and " are just the integrals of B0M�A and ANM�B over the appropriate intervals; thus ﬀ 3 " is the integral of AOM�B5�PBQM�A (mi- nus because the limits of integration are reversed). But M�C$�RAOM�B$�1B0M�A , and so ﬀ 3 "@�TS.C is precisely the radian measure of � . (Of course, one can perfectly well do this problem by computing the two integrals sepa- rately. But what’s the fun in that?) A-3 If at least one of UV�LW � , UYXZ�LW � , UYX X��W � , or UYX X XZ�LW � van- ishes at some point W , then we are done. Hence we may assume each of UV�LA � , UYXZ�[A � , UYX XZ�[A � , and UYX X XZ�[A � is either strictly positive or strictly negative on the real line. By replacing UV�[A � by �OUV�[A � if necessary, we may assume UYX XZ�LA � \^] ; by replacing UV�[A � by UV�_� A � if necessary, we may assume UYX X XZ�[A �!\T] . (No- tice that these substitutions do not change the sign of UV�[A � UYX��LA � UYX`X��LA � UYX`X XZ�[A � .) Now UYX XZ�[A �$\ ] implies that U X �[A � is increasing, and U X X X �[A �!\�] implies that U X �[A � is convex, so that UYX��LA 3 W �!\ UYX��LA � 3 WaUYX XZ�LA � for all A and W . By letting W increase in the latter inequality, we see that UYX��LA 3 W � must be positive for sufficiently large W ; it follows that UYX��LA �b\c] for all A . Similarly, UYX��LA �$\�] and UYX XZ�[A ��\�] imply that UV�[A �!\�] for all A . Therefore UV�LA � UYX��LA � UYX`XZ�[A � UYX`X XZ�[A �N\R] for all A , and we are done. A-4 The number of digits in the decimal expansion of ﬀNd is the Fibonacci number �ed , where � K �f , �hg?�i , and �hdj�f�hd I>K 3 �hd I g for k \l� . It follows that the sequence mnﬀ dpo , modulo 11, satisfies the recursion ﬀ d �c�_�! �_q�rK 3 ﬀ d I g . (Notice that the recur- sion for ﬀ d depends only on the value of � d I g modulo 2.) Using these recursions, we find that ﬀNu�v ] and ﬀOw�vx modulo 11, and that � u v7 and �hw�vx mod- ulo 2. It follows that ﬀOd7vyﬀNdº , so that the given sum is » �[¼ k � �¢½ ¶0d IJK © ��! ��¾�¿VÀ rÁ Â . If ¼ and k are both odd, then »Ã�[¼ k � is the sum of an odd number of Ä. ’s, and thus cannot be zero. Now consider the case where ¼ and k have opposite par- ity. Note that ¹ ¶ º 3 ¹�� z K ¶ º �ÅÆ�Ç for all integers ¸ ¼ . Thus ¹ ¶ º 3 ¹ ¶0d I I>K ¶ º �^k8�} and ¹ d º 3 ¹ ¶0d I IJK d º �È¼É�Ê ; this implies that U�¶N· dp�L¸ � 3 U�¶N· dp�L¼k(�b¸�P � �;¼ 3 k(� � is odd, and so �_�! ��¾_¿VÀ rÁ Â ��! ��¾_¿VÀ rÁ ¶0d I IJK Â for all ¸ . It follows that » �[¼ k � � ] if ¼ and k have opposite parity. Now suppose that ¼¢� � and k8� �<Ë are both even. Then ¹ g g�¶ º �f¹ g z K g�¶ º for all Ì , so » can be computed as twice the sum over only even indices: » � � ��Ë�� gÎÍÎÏ IJK Ð © ��! � ¾�Ñ À Ò Á Â �2» �Z ËZ� �� 3 �_�! � ÍÓzJÏ �Ó� Thus »Ã� � �<ËZ� vanishes if and only if » �Z ËZ� vanishes (if 3 �_�! � ÍÓzJÏ � ] , then and Ë have opposite parity and so » �� Ë�� also vanishes). Piecing our various cases together, we easily deduce that » �L¼ k � � ] if and only if the highest powers of 2 dividing ¼ and k are different. B–5 Write Ô¥� �� ] K�Õ�Õ w �Ö �� . Then � Ô� ] Õ�Õ�Õ � ¦ �× ] I>K�Õ�Õ w � ] Õ�Õ�Õ � �_ O� � ] IJK_Õ�Õ w 3 Ł � where Ł ] I g ©�©�© . Now the digits after the deci- mal point of ] Õ�Õ�Õ � � are given by � �� ®�«� , while the digits after the decimal point of K { ] IpÕ�Õ�Õ are given by � ]�]�]�]�] �«�®� «�� «�®� . It follows that the first 1000 digits of � Ô are given by � �� «�®� ��¨ ; in particu- lar, the thousandth digit is . B–6 First solution: Write e�[k � �Tk 3 Wk g 3 k 3DØ . Note that e�Lk � and e�Lk 3 �� have the same parity, and recall that any perfect square is congruent to 0 or 1 (mod 4). Thus if e�Lk � and e�Lk 3 �� are perfect squares, they are congruent mod 4. But e�[k 3 �� Ãe�Lk � v � k g 3 � (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 coefficients which is not a perfect square, there exists a positive integer k such that Ù�[k � is not a perfect square. Of course it suffices to assume Ù� § � has no repeated factors, which is to say Ù� § � and its derivative Ù!XZ� § � are relatively prime. In particular, if we carry out the Euclidean algorithm on Ù� § � and Ù!X�� § � without dividing, we get an in- teger ﬁ (the discriminant of Ù ) such that the great- est common divisor of Ù�Lk � and Ù!XZ�[k � divides ﬁ for any k . Now there exist infinitely many primes such that divides Ù�[k � for some k : if there were only finitely many, say, K �®�«� Í , then for any k di- visible by ¼ �ÚÙ� ]�� K gÜÛ«Û®Û Í , we have Ù�[k � v Ù� ]� �LÝb�ÞP¼ � , that is, Ù�[k �� Ù� ]�� is not divisible by K6 �«�®� pÍ , so must be Ä. , but then Ù takes some value infinitely many times, contradiction. In particu- lar, we can choose some such not dividing ﬁ , and choose k such that divides Ù�Lk � . Then Ù�[k 3 � � v Ù�[k � 3 6pÙ!X��Lk � �LÝßaÞÜ � (write out the Taylor series of the left side); in particular, since does not divide Ù!X��Lk � , we can find some such that Ù�Lk 3 � � is di- visible by but not by g , and so is not a perfect square. Third solution: (from David Rusin, David Savitt, and Richard Stanley independently) Assume that k 3 Wk g 3 k 3;Ø is a square for all k \�] . For sufficiently large k , �[k Îà�g 3 � Wk K à�g �Ö � g k 3 Wk g 3 k 3DØ �Lk �à�g 3 � Wk K à�g 3 � g�á 2 thus if k is a large even perfect square, we have k 3 W�k g 3 k 35Ø ��[k Îà�g 3 K g Wk K à�g � g . We conclude this is an 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 ar- bitrary polynomials. A related argument, due to Greg Kuperberg: write � k 3 Wk g 3 k 3DØ as k �à�g times a power series in � k and take two finite differences to get an expression which tends to 0 as kDâ£ã , contra- diction.) Note: in case k 3 Wk g 3 k 3ÖØ has no repeated fac- tors, it is a square for only finitely 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

                    本文档为【1998s】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

1998s

你可能还喜欢