1
SKOLIAD
No. 122
Lily Yen and Mogens Hansen
Please send your solutions to problems in this Skoliad by 1 July, 2010. A
opy of CRUX will be sent to one pre-university reader who sends in solutions before the deadline. The de ision of the editors is nal. Our ontest for this number of the Skoliad is the 27th New Brunswi k Mathemati s Competition, 2009, Grade 9, Part C. We thank Daryl Tingley, Department of Mathemati s and Statisti s, University of New Brunswi k, and Paul Deguire, Departement de mathematiques et de statistique, Fa ulte des s ien es, Universite de Mon ton, for providing us with this ontest and for permission to publish it. Complete justi ation is required in order for a solver to obtain redit for his/her solution. th
27
New Brunswi k Mathemati s Competition, 2009 Grade 9, Part C Approximately 30 minutes allowed
. If you write all integers from 1 to 100, how many even digits will be written? (When you write the number 42, two even digits are written.) (A) 50 (B) 71 (C) 80 (D) 89 (E) 91
1
. In a farm there are hens (no hump, two legs), amels (two humps, four legs) and dromedaries (one hump, four legs). If the number of legs is four times the number of humps, then the number of hens divided by the number of amels will be? (A) 12 (B) 1 (C) 32 (D) 2 (E) Not enough information 2
. A ubi box of side 1 m is pla ed on the oor. A se ond ubi box of side m is pla ed on top of the rst box so that the entre of the se ond box is dire tly above the entre of the rst box. A painter paints all of the surfa e area of the two boxes that an be rea hed without moving the boxes. What is the total area of surfa e that is painted?
3
2 3
(A) 4
49 9
m2
(B)
57 9
m2
(C)
61 9
. What is the ones digit of 22009 ? (A) 0 (B) 2 (C) 4
m2
(D)
72 9
(D) 6
m2
(E) None of these (E) 8
2 . The numbers 1, 2, 3, 4, 5, and 6 are to be arranged in a row. In how many ways an this be done if 2 is always to the left of 4, and 4 is always to the left of 6? (For example 2, 5, 3, 4, 6, 1 is an arrangement with 2 to the left of 4 and 4 to the left of 6.) (A) 20 (B) 36 (C) 60 (D) 120 (E) 240 5
. The square ABCD is ins ribed in a ir le with diameter BD of length 2. If AB is the diameter of the semi ir le on top of the square, what is the area of the shaded region? 6
(A) 4 −4 π (D) 1
2 (B) π − (C) 4 (E) Not enough information e
27
1 2
.............................. ......... ..... ..... .... . . . . .... ............................................. ..... . . A ........................................................................................ B ....... ......... ..... .. ... ... ... .... .... ..... . . .... .... . ... . . ... .... ..... ... .. ... .. .... . . . ..... ..... ... .... . . . . . .. .. ... .. .... 2 .. . . ... ... . . . ... ... . . ... ... . . ... ... ....... ... ... . . . .... ... .... ............................................................................... . ...... . . . D ..................................................... C
Con ours de Mathematiques du Nouveau-Brunswi k, 2009 e
9
annee, Partie C
Duree : environ 30 minutes
. Si vous e rivez tous les entiers de 1 a 100, ombien de hi res pairs seront e rits ? (Quand vous e rivez le nombre 42, vous e rivez deux hi res pairs.) (B) 71 (C) 80 (D) 89 (E) 91 (A) 50
1
. Dans une ferme il y a des poules (pas de bosse, deux pattes), des hameaux (deux bosses, quatre pattes) et des dromadaires (une bosse, quatre pattes). Si le nombre de pattes est quatre fois le nombre de bosses, alors le nombre de poules, divise par le nombre de hameaux sera de ? 2
(A)
1 2
(B) 1
(C)
3 2
(D) 2
(E) Information insuÆsante
. Une bo^te ubique dont le ot ^ e mesure 1 m est pla ee sur le sol. Une se onde bo^te ubique dont le ot ^ e mesure 23 m est pla ee sur la premiere de maniere a e que son entre soit exa tement au dessus du entre de la premiere bo^te. Un peintre peint alors les surfa es des deux bo^tes qu'il peut rejoindre sans bouger les bo^tes. Quelle est la surfa e totale qui est peinte ? 3
(A) 4
49 9
m2
(B)
57 9
m2
(C)
61 9
m2
. Quel est le hi re des unites de 22009 ? (A) 0 (B) 2 (C) 4
(D)
72 9
(D) 6
m2
(E) Au une de es reponses (E) 8
3 5. Les nombres 1, 2, 3, 4, 5 et 6 sont pla es en ligne. De ombien de fa ons
ela peut-il e^ tre fait si 2 est toujours a la gau he de 4 et 4 est toujours a la gau he de 6 ? (2, 5, 3, 4, 6, 1 est un tel pla ement ave 2 a la gau he de 4 et 4 a la gau he de 6). (B) 36 (C) 60 (D) 120 (E) 240 (A) 20
. Le arre ABCD est ins rit dans un er le dont le diametre BD est de du longueur 2. Si AB est le diametre demi- er le au-dessus du arre, quelle est l'aire de la region ombragee ? 6
(A) 4 −4 π (D) 1
2 (B) π − (C) 4 (E) Information insuÆsante
1 2
......................... ........... ..... ..... .... . . . .. .. ..... ......................................... ..... . . . . . . . . . . . . . . . . . A ........................................................................... B .. ......... ....... ..... .. ... ... .. .... .... .... . . ... .... . ... . . .... ..... ..... ... .. ... .... .... . . . ..... ..... .. .. . .... .. .. ... .. . . . . .. .. 2 . ... ... . . . ... .. . . ... ... . . ... ... ....... ... ... . . . . .... .. .... ................................................................................. . ...... . . .. D ...................................................... C
Next follow solutions to the Swedish Junior High S hool Mathemati s Contest, Final Round, 2007/2008 [2009 : 129{131℄. 1. Values are assigned to a number of ir les, and these values are written in the ir les. When two or more ir les overlap, the sum of the values of the overlapping ir les is written in the ommon region. In the example on the left below, the three ir les have been assigned the values 1, 3, and 8. Where the ir le with value 1 overlaps the ir le with value 3 we write 4 (= 1 + 3). In the region in the middle, we add all three values and write 12. .............................................................................................. ........ ...... ..... ..... ..... .... ..... ....... .... .... . . ... . .... ... ... ... ... . . ... . . .. ... ... .. .. ... .. ... ... .. .. .... ... ... ... ................................... .... ... .......... ........ .. ... . . . . . ...... ... ... .... .... . . . . . . . . .. . ..... . .. ... . . . . . ... . . ... ... ... ... ... ... ... .... .... .... .. ..... .... .... ... ..... .... .. .... ....... ......... ........ ............ . . . ................. . . . . . . ........................... ....................................... ... ... ... .. .. ... .. .. .. ... .. . ... . .. .... .... ..... ..... ...... ....... .......... .....................................
1
3
4
9
12
8
11
.............................................................................................. ........ ...... ..... ..... ..... .... ..... ....... .... .... . . ... . .... ... ... ... ... . . ... . . .. ... ... .. .. ... .. ... ... .. .. .... ... ... . . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. ......... ... ........................... ... ................ ... . . . . . . .. ..... .. ..... .. ... . ... ....... . . . . . . . . . . .. ... .... .. .... .. .. ..... ...... . . ..... . . .... .... .. .. ... ... .... .. ... .. .... ? .... ... .... ... .. .... .. ........ ....... ... .... .... .. ......... ... ........... ..... . . ... .. . .......... . . .... . . . . . . . .. ................................... ........................................ ... . . ... ... .. .. .. .. .. .. .. . . .. . . .. . . ... . . . . . ... ... . .... ... .... ... .... .... .... .... ..... ....... .... ... . .. ........ ..... ............... .......................................... ...................... ........... ..........
In the gure on the right above are four ir les and, thus, thirteen regions. Find the number in the middle if the sum of all thirteen numbers is 294. Solution by Alison Tam, student, Burnaby South Se ondary S hool, Burnaby, BC. Assign the values a, b, c, and d to the four ir les, as shown in the diagram on the following page. Then the overlapping regions get the values shown. The sum of the thirteen regions is 7a + 7b + 7c + 7d. Sin e this
4
c
b+
+
d
a+d
c+
d
+
b+
a+b+ c+d
d
a
+
c+
c
a
a
b+c
. This is the 20th edition of the Swedish Junior High S hool Mathemati s Contest. The rst quali ation round was held in the fall of 1988, and this year's nal is held in2008. That is twenty-one alendar years, 1988{2008, but the table at right has room for only eighteen of them. Whi h three must be omitted if the digit sum in every row and every olumn must be divisible by 9? (Two solutions exist.) 2
a+b
b
b+
Also solved by CINDY CHEN, student, Burnaby North Se ondary S hool, Burnaby, BC; EMILY HUANG, student, Burnaby Central Se ondary S hool, Burnaby, BC; JIXUAN WANG, student, Don Mills Collegiate Institute, Toronto, ON; LENA CHOI, student, E ole Banting Middle S hool, Coquitlam, BC; NATALIA DESY, student, SMA Xaverius 1, Palembang, Indonesia; and THOMAS HSU, student, Mos rop Se ondary S hool, Burnaby, BC.
............................................... ............................................... ............. ......... ..................... ......... ......... ... ....... ....... ...... ...... ...... ..... ...... ..... ......... . . . . . . . . .... .... .. .. . . . . .... . . . .... ... ... ... . . . . . ... ... ... ... ... ... . . . . ... . . ... . . .. .. .. .. . . .. . . .. .. ... ... ... .. .. ... ... .. .. .. .. ... . .. . . .... . . . .................................... ................................... . . . . . . . . . . . . ... . . . . . . ... . . . . . . . . . . . . . . .......... .......... .......... ... . ... ....... ... . . . . . . . . . . . . . . . . . . . . . . . . . . ... ....... .. . ... ...... .............. . . . . . . . .. . . . . . . . . . . . . ..... ..... .. . . ... ..... ..... .... .... .. .. .. ... .. ....... .... .... ... .... ... ... ...... ... ... ... .. ... ... ..... ..... ...... ...... . . . . . . . . . . . . .. .. ... ... ... ... ... ..... ... ..... .... .... .... .... ... ....... ... ....... .. .... .... .. .. ..... ... ..... .. .. .. ..... ..... ...... . . . . . . . . . . . .. . . . . . . ... . . . . . ....... ........... . .. .. ......... .. ........ .. ... ... .. ............. ......... ...................... ......... . . . . . . . . . . . . . . . .... . . . . . . . . . . ... . . . . . . ............................... ............................... ... . . . ... . ... ... . . . . ... ... ... .. .. .... .... .. .. . . ... ... .. .. .. .. ... ... .. .. ... ... .. .. . . ... . . . ... . ... .. .... ... .... ... .... ... .... .... ... ..... ..... ... .... ..... ...... ..... . . . ................... . . ........ . ......... ...... ........ .............. ......... ...................... ......... .......................................... ..........................................
a
sum is required to be 294, it follows that the value in the middle region is 294 a+b+c+d= = 42. 7
c+d
d
.............................................. .............................................. ................................................. ................................................. .. .... .... .... .. .. .... .... .... .. .............................................. .............................................. .. ..... ..... ..... .. .. ..... ..... ..... .. ................................................. ................................................. ............................................. ............................................. ...................................................... ...................................................... .. ... ... ... .. .. ... ... ... .. ........................................... ........................................... .. ..... ..... ..... .. .. ..... ..... ..... .. .............................................. .............................................. ................................................ ................................................ ...................................................... ......................................................
Solution by Jixuan Wang, student, Don Mills Collegiate Institute, Toronto, ON. The digits in the rst olumns of ea h of the two parts of the hart are 1's and 2's. Say one su h olumn has k opies of 1 and 9 − k opies of 2. Then the sum is k + 2(9 − k) = 18 − k. If this sum is a multiple of 9, then k is a multiple of 9, so either k = 0 or k = 9. Thus, one rst olumn ontains only 1's while the other rst olumn ontains only 2's. Sin e only nine years begin with 2, all of them must be used and they must all be in the same part of the hart. See the left-hand diagram below. .............................................. .............................................. ......1............9............................... ......2............0.............0............0...... .. 1 ..... 9 ..... ..... .. ... 2 ..... 0 ..... 0 ..... 1 .. .............................................. .............................................. ... 1 .... 9 .... .... . ... 2 .... 0 .... 0 .... 2 . .................................................. .................................................. ......1...........9............................ ......2...........0............0...........3..... ......1.............9.................................. ......2.............0..............0.............4....... ... .... .... .... .. ... .... .... .... .. ......1...........9............................. ......2...........0............0...........5...... ... 1 .... 9 .... .... . ... 2 .... 0 .... 0 .... 6 . ............................................... ............................................... ......1...........9............................ ......2...........0............0...........7..... ......1............9................................ ......2............0.............0............8.......
.............................................. .............................................. ......1............9.............9............6...... ......2............0.............0............0...... .. 1 ..... 9 ..... 9 ..... 5 .. ... 2 ..... 0 ..... 0 ..... 1 .. .............................................. .............................................. ... 1 .... 9 .... 9 .... 4 . ... 2 .... 0 .... 0 .... 2 . .................................................. .................................................. ......1...........9............9...........3..... ......2...........0............0...........3..... ......1.............9..............9.............2....... ......2.............0..............0.............4....... ... .... .... .... .. ... .... .... .... .. ......1...........9............9...........1...... ......2...........0............0...........5...... ... 1 .... 9 .... 9 .... x. ... 2 .... 0 .... 0 .... 6 . ............................................... ............................................... ......1...........9............9...........8..... ......2...........0............0...........7..... ......1............9.............9............7....... ......2............0.............0............8.......
Here x is either 0 or 9
The third olumn in the 1900's part of the hart ontains 8's and 9's.
5 Sin e there are at most two 8's and the olumn sum is divisible by 9, the
olumn must onsist of only 9's. Thus the years 1988 and 1989 must be ex luded from the hart. Using that the row sums are divisible by 9, it is now easy to ll in the hart as in the right-hand diagram. Hen e the ex luded years are either 1988, 1989, and 1990; or 1988, 1989 and 1999. Also solved by LENA CHOI, student, E ole Banting Middle S hool, Coquitlam, BC.
. The line segments DE , CE , BF , and CF divide the re tangle ABCD into a number of smaller regions. Four of these, two triangles and two quadrilaterals, are shaded in the gure at right. The areas of the four shaded regions are 9, 35, 6, and x (see the gure). Determine the value of x. 3
B ................................................................................................................................................... C E
... ....... .............. ........ ... .... ............. .. ... .... ...... .............. .. .. .... ............. . . . . ... . . . . . . . . .. ... .... ...... ... .. .. .... .......................... .. .... ... . . . . . . . . . . . . . . . .... ......................... .. .. .... .............. .. ..... .. .... ... .......... ... .. .... ... ........... . .... ......... . ... .. ... ......... ...... .. .... . . . . .... . . . ......... ... .. ............. ..... .... . . ............ . ... . .... ........ .. .... ............. . ... . .... .......... . .... . ... .... .......... .. .... .... . . .. .... ... .... ................... ... .... .. .......... .... ......... ..... .... .. . .... . . . . . ..........................................................................................................................................................
9
x
35
A
6
F
D
Solution by Lena Choi, student, E ole Banting Middle S hool, Coquitlam, BC. Sin e the base of △BCF is |BC| and its height is |CD|, the area of B C △BCF is half the area of re tana gle ABCD. But then △ABF and 9 △CDF take up the other half of E x b the re tangle. Similarly, the area of △CDE equals half the area of the d re tangle as does the ombined area of 35 c △BCE and △ADE . 6 Assign letters to the areas of the A D F four unshaded regions as in the gure. Then the paragraph above amounts to saying that a+x+c, 9+b+35+d+6, b+x+d, and 9+a+35+c+6 are all equal. In parti ular, a + x + c = 9 + a + 35 + c + 6, so x = 9 + 35 + 6 = 50. ............................................................................................................................................................... ... .... ..... . ............. ......... .... ...... ............. . .... ... .............. .. ... .... .............. . . ... . . .. ... . . . . . . . . .... ...... . .. .. ... ...................... .... .. ... .. .... . .... ................................ . ... .... .............. .. . .... .. .... ................ ..... ... .. ......... .... .... .. ......... ...... .. . ......... .... .... .... ......... .... .. ... . ... . ............ . .... . ... ........... .. ......... .... .... . . ............. . ... . ... .... .......... .... .......... .... .... .... ........... .... .... .... .......... .... . ... ... . .... .. .......... ... . . . . . . ... ... . ......................................................................................................................................................................
Also solved by ALISON TAM, student, Burnaby South Se ondary S hool, Burnaby, BC; CINDY CHEN, student, Burnaby North Se ondary S hool, Burnaby, BC; JIXUAN WANG, student, Don Mills Collegiate Institute, Toronto, ON; and NATALIA DESY, student, SMA Xaverius 1, Palembang, Indonesia. 4. A goody bag ontains a two-digit number of goodies. Lisa adds the two digits and then removes as many goodies as the sum yields. Lisa repeats this pro edure until the number of goodies left is a single digit number larger than zero. Find this single digit number.
Solution by the editors. Say the number of goodies is 10a + b. Then Lisa removes a + b goodies and is left with 9a goodies. It follows that on e Lisa has removed goodies at
6 least on e, then the number of goodies left is divisible by nine. Thus, when the number of goodies left rea hes a single-digit number, that number must be nine. Several solvers found that Lisa is left with nine goodies with several hoi es of the initial number of goodies. However, that does not prove that Lisa always ends up with nine goodies.
. In how many ways an the list [1, 2, 3, 4, 5, 6] be permuted if the produ t of neighbouring numbers must always be even?
5
Solution by Natalia Desy, student, SMA Xaverius 1, Palembang, Indonesia. If the produ t of neighbouring numbers is even, then the parity of the numbers must follow one of the patterns eoeoeo , oeoeoe , oeoeeo , or oeeoeo , where e is an even number and o is an odd number. On e you have hosen one of the four patterns, you an arrange the three even numbers into the even slots in six ways, and you an arrange the odd numbers in six ways. Thus the total number of permutations is 4 · 6 · 6 = 144. Also solved by JIXUAN WANG, student, Don Mills Collegiate Institute, Toronto, ON.
. The digits of a ve-digit number are abcde. Prove that abcde is divisible by 7 if and only if the number abcd − 2 · e is divisible by 7. 6
Solution by the editors. Let A and B denote the two numbers abcde and abcd − 2e, respe tively. Let x denote the four-digit number abcd. Then A = 10x + e and B = x − 2e. Therefore, 2A + B = 20x + 2e + (x − 2e) = 21x . If A is divisible by 7, then A = 7m for some integer m, so B = 21x − 2A = 21x − 14m = 7(3x − 2m) , whi h is divisible by 7. If B is divisible by 7, then B = 7n for some integer n, so 2A = 21x − B = 21x − 7n = 7(3x − n) , whi h is divisible by 7. But if 2A is divisible by 7, then so is A. Thus, A is divisible by 7 if and only if B is divisible by 7. This issue's prize of one opy of CRUX with MAYHEM for the best solutions goes to Jixuan Wang, student, Don Mills Collegiate Institute, Toronto, ON. We would very mu h appre iate re eiving more solutions from our readers. Solutions to just some of the problems are also very wel ome.
7
MATHEMATICAL MAYHEM Mathemati al Mayhem began in 1988 as a Mathemati al Journal for and by . It ontinues, with the same emphasis, as an integral part of Crux Mathemati orum with Mathemati al Mayhem. The Mayhem Editor is Ian VanderBurgh (University of Waterloo). The other sta members are Monika Khbeis (Our Lady of Mt. Carmel Se ondary S hool, Mississauga, ON) and Eri Robert (Leo Hayes High S hool, Frederi ton, NB). High S hool and University Students
Mayhem Problems Please send your solutions to the problems in this edition by 1 May 2010. Solutions re eived after this date will only be onsidered if there is time before publi ation of the solutions. The Mayhem Sta ask that ea h solution be submitted on a separate page and that the solver's name and onta t information be in luded with ea h solution. Ea h problem is given in English and Fren h, the oÆ ial languages of Canada. In issues 1, 3, 5, and 7, English will pre ede Fren h, and in issues 2, 4, 6, and 8, Fren h will pre ede English. The editor thanks Jean-Mar Terrier of the University of Montreal for translations of the problems.
. Proposed by the Mayhem Sta . Riley is a poor starving university student, but is mathemati ally astute. He noti es that ve suppers in residen e ost the same as seven lun hes. After one week of skipping supper most nights, he noti es that ve lun hes and one supper ost $48 in total. How mu h do 16 suppers ost? M420
. Proposed by Ne ulai Stan iu, George Emil Palade Se ondary S hool, Buzau, Romania. Let ⌊x⌋ be the greatest integer less than or equal to the real number x. Determine all real numbers x su h that M421
1
x
+
3
x
= 4.
M422. Proposed by Adnan Arapovi , student, University of Waterloo, Waterloo, ON. Prove that n X k(k + 1) k=1
2
=
n(n + 1)(n + 2) 6
.
8 M423. Proposed by John Grant M Loughlin, University of New Brunswi k, Frederi ton, NB. The tens digit of a perfe t square S is three greater than the ones digit of S . Determine all possible remainders when S is divided by 100.
. Proposed by Margo Kondratieva, Memorial University of Newfoundland, St. John's, NL. In the diagram, line segments AB , A ........................................................ B ... ...... CDE , and F GH are parallel. Also, line .. ... ... ... ... ... ... segments ACF and BDG are perpendi ular ... ...... .. ... .... ... ... ... to AB . Suppose that the area of re tangle ... ... .. E .... C D . ................................................................................................ ABDC is x, the area of re tangle CDGF is . ... .... . . . y , and the area of △BDE is z . Determine ..................................................................................................... F H the area of DEHG in terms of x, y, and z . G M424
. Proposed by Titu Zvonaru, Comane sti, Romania. In △ABC , ∠BAC = 90◦ and I is the in entre. The interior bise tor of angle C meets AB at D. The line segment through D perpendi ular to BI interse ts BC at E . The line segment through D parallel to BI meets AC at F . Prove that E , I , and F are ollinear. M425
................................................................. . Propose par l'Equipe de Mayhem. Ri hard est un etudiant pauvre et a ame, mais mathematiquement doue. Il a remarque qu'a la residen e,
inq soupers outent ^ le m^eme prix que sept lun hs. Apres avoir saute les soupers presque tous les soirs pen48 au dant une semaine, il onstate que inq lun hs et un souper outent ^ total. Combien outent ^ 16 soupers ? M420
. Propose par Ne ulai Stan iu, E ole se ondaire George Emil Palade, Buzau, Roumanie. Soit ⌊x⌋ le plus grand entier plus petit ou egal au nombre reel x. Trouver tous les nombres reels tels que M421
1 3 + x x
= 4.
. Propose par Adnan Arapovi , etudiant, Universite de Waterloo, Waterloo, ON. Montrer que
M422
n X k(k + 1) k=1
2
=
n(n + 1)(n + 2) 6
.
9 M423. Propose par John Grant M Loughlin, Universite du NouveauBrunswi k, Frederi ton, NB. La di eren e entre le hi re des dizaines et elui des unites d'un arre parfait S est de trois. Trouver tous les restes de la division de S par 100.
. Propose par Margo Kondratieva, Universite Memorial de TerreNeuve, St. John's, NL. Dans la gure i- ontre, les segments de droite AB , CDE , et F GH sont pa- A .................................................................B ... .... ...... ... ralleles. De plus, les segments ACF et ... ... ...... .. ... ... BDG sont perpendi ulaires a AB . Suppo... .... ... ... . ... .. E sons que les aires respe tives des re tangles C .................................................D .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ................. ... . . ... ... . ABDC , CDGF , et △BDE sont x, y et z . . ... . .. Trouver l'aire de DEHG en fon tion de x, F ................................................................................................. H G y et z . M424
. Propose par Titu Zvonaru, Comane sti, Roumanie. ◦ Dans le triangle ABC , ∠BAC = 90 et soit I le entre du er le ins rit. La bisse tri e interieure de l'angle C oupe AB en D. La droite passant par D et perpendi ulaire a BI oupe BC en E . La droite passant par D et parallele a BI oupe AC en F . Montrer que E , I et F sont olineaires. M425
Mayhem Solutions Last year we re eived some late solutions that did not appear in the De ember issue. We therefore a knowledge a orre t solution to M383 by Mridul Singh, student, Kendriya Vidyalaya S hool, Shillong, India, and orre t solutions to problems M383, M384, and M386 by Hugo Luyo San hez, Ponti ia Universidad Catoli a del Peru, Lima, Peru. . Proposed by Kyle Sampson, St. John's, NL. A sequen e is generated by listing (from smallest to largest) for ea h positive integer n the multiples of n up to and in luding n2 . Thus, the sequen e begins 1, 2, 4, 3, 6, 9, 4, 8, 12, 16, 5, 10, 15, 20, 25, 6, 12, . . . . Determine the 2009th term in the sequen e. M388
Solution by Kristof Huszar, Valeria Ko h Grammar S hool, Pe s, Hungary. First, we noti e that there are k positive integral multiples of k less than or equal to k2 . If we group the terms of the sequen e as the multiples of 1, then the multiples of 2, then the multiples 3, and so on, we noti e that the groups have 1 term, then 2 terms, then 3 terms, and so on.
10 If n is a positive integer, then the sum of the rst n positive integersis th
equal to 1 + 2 + 3 + · · · + n = n(n2+ 1) . Therefore, n2 is the n(n2+ 1) term of the sequen e. th Hen e, 632 = 3969 is the 63 2· 64 = 2016th term. Sin e 3969 o
urs 2016 − 2009 = 7 terms after the 2009th term, we nd that the 2009th term is 632 − 7(63) = 3528.
Also solved by EDIN AJANOVIC, student, First Bosniak High S hool, Sarajevo, Bosnia and Herzegovina ; JACLYN CHANG, student, Western Canada High S hool, Calgary, AB ; NATALIA DESY, student, SMA Xaverius 1, Palembang, Indonesia ; ANTONIO GODOY TOHARIA, Madrid, Spain ; RICHARD I. HESS, Ran ho Palos Verdes, CA, USA ; RICARD PEIRO, IES \Abastos", Valen ia, Spain ; EDWARD T.H. WANG, Wilfrid Laurier University, Waterloo, ON ; and JIXUAN WANG, student, Don Mills Collegiate Institute, Toronto, ON. One in orre t solution was submitted.
. Proposed by Lino Demasi, student, Simon Fraser University, Burnaby, BC. There are 2009 students and ea h has a ard with a di erent positive integer on it. If the sum of the numbers on these ards is 2020049, what are the possible values for the median of the numbers on the ards ? M389
Solution by Jixuan Wang, student, Don Mills Collegiate Institute, Toronto, ON. Let a be the smallest of the numbers on the ards. The smallest possible sum of the 2009 numbers on the ards is then S
= a + (a + 1) + (a + 2) + · · · + (a + 2008) = 2009a +
1 (2008)(2009) = 2009a + 2017036 . 2
If a ≥ 2 then S ≥ 2021054 > 2020049. Therefore, a = 1. Next, onsider the sequen e of numbers 1, 2, 3, . . . , 2009. The sum of these numbers is 2019045 (whi h is 1004 less than the desired sum of 2020049). Also, their median is 1005. In order to obtain the desired sum of 2020049, some of the numbers in this sequen e need to be in reased. When a ertain term in the sequen e is in reased, then every greater term must be in reased as well in order for the terms of the sequen e to remain distin t. If a term that is less than 1006 is in reased, then every larger term will also have to in rease, resulting in an in rease of the initial sum 2019045 by at least 1005 (sin e at least 1005 terms are in reased), yielding a new sum of at least 2019045 + 1005 = 2020050, whi h is too large. Therefore, only terms that are 1006 or greater may be in reased. When only terms greater than or equal to 1006 are in reased, then the median 1005 remains un hanged. Thus, 1005 is the only possible value for the median.
11 Also solved by NATALIA DESY, student, SMA Xaverius 1, Palembang, Indonesia ; IES \Abastos", RICHARD I. HESS, Ran ho Palos Verdes, CA, USA ; RICARD PEIRO, Valen ia, Spain ; and EDWARD T.H. WANG, Wilfrid Laurier University, Waterloo, ON. There was one in orre t solution submitted.
. Proposed by Ne ulai Stan iu, George Emil Palade Se ondary S hool, Buzau, Romania. A Pythagorean triangle is a right-angled triangle with all three sides of integer length. Let a and b be the legs of a Pythagorean triangle and let h be the altitude to the hypotenuse. Determine all su h triangles for whi h M390
1 a
+
1 b
+
1 h
= 1.
Solution by D.J. Smeenk, Zaltbommel, the Netherlands. Let A be the area of the triangle and c the length of its hypotenuse. Then A equals both 12 ab and 12 ch, and so ab = ch. Also, 1 = =
1 1 1 bh + ah + ab ah + bh + ch + + = = a b h abh abh (a + b + c)h a+b+c = , abh ab
hen e ab = a + b + c. √ By the Pythagorean Theorem, c = a2 + b2 . Sin e a + b + c = ab, we then obtain the equivalent equations p ab = a + b + a2 + b2 , p ab − a − b = a2 + b2 , 2 2 (ab − a − b) = a + b2 , a2 b2 + a2 + b2 − 2a2 b − 2ab2 + 2ab = a2 + b2 , a2 b2 − 2a2 b − 2ab2 + 2ab = 0 , ab(ab − 2a − 2b + 2) = 0 . Sin e ab > 0, then ab −2a − 2b+ 2 = 0, or b(a − 2) = 2a − 2, whi h implies −2 2 that b = 2a =2+ . a−2 a−2 Sin e a and b are positive integers, then a − 2 is a positive divisor of 2 ; that is, a − 2 = 2 or a − 2 = 1. If a − 2 = 2, then a = 4, b = 3, and c = 5. If a − 2 = 1, then a = 3, b = 4, and c = 5. There is therefore just one Pythagorean triangle for whi h a1 + 1b + h1 = 1, namely the triangle with legs 3 and 4, and hypotenuse 5. Also solved by EDIN AJANOVIC, student, First Bosniak High S hool, Sarajevo, Bosnia and Herzegovina ; CAO MINH QUANG, Nguyen Binh Khiem High S hool, Vinh Long, Vietnam ; ANTONIO GODOY TOHARIA, Madrid, Spain ; RICHARD I. HESS, Ran ho Palos HUSZAR, Verdes, CA, USA ; KRISTOF Valeria Ko h Grammar S hool, Pe s, Hungary ; IES \Abastos", Valen ia, Spain ; EDWARD T.H. WANG, Wilfrid Laurier RICARD PEIRO,
12 University, Waterloo, ON ; and KONSTANTINE ZELATOR, University of Pittsburgh, Pittsburgh, PA, USA.
. Proposed by Ne ulai Stan iu, George Emil Palade Se ondary S hool, Buzau, Romania. M391
Determine all pairs (a, b) of positive integers for whi h both b+2 a
are positive integers.
a+1 b
and
Solution by Edin Ajanovi , student, First Bosniak High S hool, Sarajevo, Bosnia and Herzegovina, modi ed by the editor. 1 2 Let x = a + and y = b + , where x and y are positive integers. b a Rearranging, we obtain a = bx − 1 and b = ay − 2. Substituting for a in the se ond equation, we obtain b = (bx − 1)y − 2 y+2 and so y + 2 = bxy − b or b = xy . −1
2 y−1+3 3 . Sin e b and y are If x = 1, then b = yy + = = 1+ −1 y−1 y−1 positive integers, then y = 2 or y = 4 (giving b = 4 and b = 2, respe tively). y+2 If x = 2, then b = 2y . Sin e b is a positive integer, then we must −1 have y + 2 ≥ 2y − 1 and so y ≤ 3. Che king y = 1, y = 2, and y = 3 shows that y = 1 and y = 3 give positive integer values for b (namely b = 3 and b = 1, respe tively). y+2 If x = 3, then b = 3y . Sin e b is a positive integer, then we must −1
have y + 2 ≥ 3y − 1 and so y ≤ 32 . The only possible value of y is y = 1, whi h does not give an integer value for b. y+2 If x = 4, then b = 4y . Sin e b is a positive integer, then we must −1 have y + 2 ≥ 4y − 1 and so y ≤ 1. If y = 1, then b = 1. If x ≥ 5, then xy − 1 ≥ 5y − 1 > y + 2 for all positive integers y, so y+2 b=
annot be a positive integer. xy − 1 We nish by al ulating the values of a that go with the values of b to obtain the pairs (a, b) = (3, 4), (1, 2), (5, 3), (1, 1), (3, 1). Also solved by ANTONIO GODOY TOHARIA, Madrid, Spain ; RICHARD I. HESS, Ran ho HUSZAR, Valeria Palos Verdes, CA, USA ; KRISTOF Ko h Grammar S hool, Pe s, Hungary ; IES \Abastos", Valen ia, Spain ; JOSE JAIME SAN JUAN CASTELLANOS, RICARD PEIRO, student, Universidad te hnologi a de la Mixte a, Oaxa a, Mexi o ; EDWARD T.H. WANG, Wilfrid Laurier University, Waterloo, ON ; and KONSTANTINE ZELATOR, University of Pittsburgh, Pittsburgh, PA, USA.
. Proposed by the Mayhem Sta . Determine, with justi ation, the fra tion pq , where p and q are positive
M392
integers and q < 1000, that is losest to, but not equal to,
19 . 72
13 Solution by Jixuan Wang, student, Don Mills Collegiate Institute, Toronto, ON, modi ed by the editor. In order to nd the desired fra tion, we need to minimize the value of p 19 |72p − 19q| − = q 72 72q
,
where p and q are positive integers and q < 1000. To do this, we attempt to make the numerator of this di eren e as small as possible, while at the same time keeping the denominator as large as possible, hen e by making q as large as possible. To minimize the numerator, we try to make 72p−19q equal to 1 or −1. Consider 72p − 19q modulo 19. Sin e 72 ≡ −4 (mod 19), then 72p − 19q ≡ −4p (mod 19), so we try to nd p su h that −4p ≡ ±1 (mod 19). Solving this ongruen e, we obtain p ≡ 14 (mod 19), or p ≡ 5 (mod 19), and so p = 14 + 19k for some integer k ≥ 0 or p = 5 + 19k for some integer k ≥ 0. In the rst ase, 72p − 19q = 1, so q = 72p19− 1 = 53 + 72k ; sin e q < 1000, then k ≤ 13 ; when k = 13, q = 989. In the se ond ase, 72p + 1 72p − 19q = −1, so q = = 19 + 72k ; sin e q < 1000, then k ≤ 13 ; 19 when k = 13, q = 955. 1 In either of these ases, the di eren e is equal to 72q , and so is minimized when q is maximized. Thus, in these ases, the minimum possible di eren e o
urs when q is as large as possible, or q = 989 (and so k = 13 and p = 261). This di eren e is 72 ·1989 . It is not possible to a hieve a smaller di eren e when |72p − 19q| ≥ 2 and q < 1000, sin e this di eren e would always be at least 72 · 21000 whi h is larger than the di eren e that we have already found. under the given Therefore, the fra tion losest to, but not equal to 19 72 p 261
onditions is q = 989 . Also solved by RICHARD I. HESS, Ran ho Palos Verdes, CA, USA ; and KRISTOF Valeria HUSZAR, Ko h Grammar S hool, Pe s, Hungary ; One in orre t solution was also submitted. A very similar problem appeared in the 2006 Canadian Open Mathemati s Challenge (problem 4(a), Part B).
. Proposed by the Mayhem Sta . Inside a large ir le of radius r two smaller ir les of radii a and b are drawn, as shown, so that the smaller ir les are tangent to the larger ir le at P and Q. The smaller ir les interse t at S and T . If P , S , and Q are ollinear (that is, they lie on the same straight line), prove that r = a + b. M393
...................................... ................ .......... .......... ........ ....... ........ ...... ....... ..... ..... . . . .... .. . . . .... ... . .... . ... ... . . ... .. . . .. . . . . . . . . . . . . . ... . . . . . . ............ .. .......... . . . . .. . . . . . . ... . . ....... .. ..... . . . . ... ... . . .... ... . . ... . ... .... ... . . ... .. ... . ... .... .. ... .. .. . ........... ... ... ... . . . . . . . . . . . . . . . . . . . ....... ... ... . ..... .... . . . . . . . . . .... .. .. . . . .. .. ... .... .. .. .. .. .. .. .. ... ..... .. ... .. ...... ... .. .. .. .... .. . .. ...... . . .. ...... .. ... .... ... .. .. ...... . ... ............................................................. ...... .................................................................. ...... ........................ . . . . . . . . . ...... . . . . . . . . . . . . . . . . . . . . . . . . ............. . . ........... ........... ..................... ... ................... ....................................... .............. .... ...............................................
T
P
S
Q
14 Solution by Miguel Amengual Covas, Cala Figuera, Mallor a, Spain and Geo rey A. Kandall, Hamden, CT, USA (independently). Let O be the entre of the large ir le of radius r. Let O1 be the entre of the smaller ir le of radius a tangent to the large ir le at point P , and let O2 be the
entre of the smaller ir le of radius b tanO gent to the large ir le at point Q. T Sin e the ir les entred at O1 and O1 O2 are tangent to the large ir le, then O , O2 O1 , P are ollinear, as are O , O2 , Q. Triangle OP Q is isos eles with P S Q OP = OQ, triangle O1 P S is isos eles with O1 P = O1 S , and triangle O2 QS is isos eles with O2 Q = O2 S (sin e ea h of these triangles has two radii of one of the ir les as sides). Therefore, ∠OP Q = ∠OQP , ∠O1 P S = ∠O1 SP , and ∠O2 QS = ∠O2 SQ. Sin e P , S , and Q are ollinear, then ... ....................... ................................. .......... ......... ......... ....... ...... ....... . . . . ..... .. .... ..... ... .... . . ... .. . . ... ... ... . . ... . . .. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .......... .. . ....... . . . . ... . . . . . . ... . ..... .... . .. . . . . ... . .... .. .. . . . ... ... . . ... ... .. .... . . ... .... ... ... . ... . .. .. .... ... ... . ... . . . .... .......................... .. ... .. .. . . . . . . . . . . . . . . . . ... .. ..... . .. ........ ... . . . . . . . .. .. . . . ... . ..... .. ... ... ...... .... ... .. .. .. .... ... .. .... .. .. .. ..... .... ...... ... ...... .. .... .... .. ... ...... .. .. ........... .... .. .... ..... . . . . . . . . . . ... ....... . .. .. .... ...... ....... ...... .. ... ..... .. .... .... ......... ................................................................ .. .... ................................................................... ...... ....... ... ......... .................................................................. . . . . . . ................... . ............................ ....................................... ....... ............. .................................................
∠P SO1 = ∠O1 P S = ∠OP Q = ∠P QO ,
whi h tells us that O1 S and OQ are parallel. Similarly, ∠QSO2 = ∠O2 QS = ∠OQP = ∠QP O ,
whi h tells us that O2 S and OP are parallel. Therefore, quadrilateral OO1 SO2 is a parallelogram. Thus, OO1 = SO2 . But SO2 = b and OO1 = OP − O1 P = r − a, and so r − a = b, or r = a + b.
Also solved by EDIN AJANOVIC, student, First Bosniak High S hool, Sarajevo, Bosnia and Herzegovina ; CAO MINH QUANG, Nguyen Binh Khiem High S hool, Vinh Long, HUSZAR, Vietnam ; ANTONIO GODOY TOHARIA, Madrid, Spain ; KRISTOF Valeria Ko h IES \Abastos", Valen ia, Spain ; Grammar S hool, Pe s, Hungary ; RICARD PEIRO, D.J. SMEENK, Zaltbommel, the Netherlands ; and JIXUAN WANG, student, Don Mills Collegiate Institute, Toronto, ON.
Problem of the Month Ian VanderBurgh
To start the new year of Problems of the Month, we'll look at a problem that relies on a on ept that we learn early on { addition { but requires us to think in some fairly deep ways to ome up with a omplete solution and total understanding of what is going on.
15 Sin e we've had a short break sin e the last issue, we should start with a warm-up problem. Your task is to ompute the following sum : 2 + 22 + 222 + 2222 + 22222 + 222222 + 2222222 . But before you start, there are two rules : no al ulators are allowed, and you have to ompute the sum aloud. If you're as out of pra ti e on this sort of thing as some of us are, this isn't all that easy. We an rewrite the sum rst in a form that makes it easier to ompute :
+
2
2 2 2 2 2
2 2 2 2
2 2 2 2 2 2 2
2 2 2 2 2 2
2 2 2 2 2
Here's an attempt to do this in words : The sum in the units' olumn is 14. Put down the 4 ; arry the 1. The sum in the tens' olumn is 12 plus the arry of 1 gives 13. Put down the 3 ; arry the 1. The sum in the hundreds' olumn is 10 plus the arry of 1 gives 11. Put down the 1 ; arry the 1. The sum in the thousands' olumn is 8 plus the arry of 1 gives 9. Put down the 9 ; no arry. The sum in the ten thousands' olumn is 6. Put down the 6. The sum in the hundred thousands' olumn is 4. Put down the 4. The sum in the millions' olumn is 2. Put down the 2. The nal sum is thus 2469134. That's a bit of a workout, isn't it ? We should larify the role of the digit and
arry. If the sum in a olumn is 14, we write this as 14 = 10(1) + 4 ; the units digit (the 4) is the digit that we write down, while the quotient when dividing by 10 (the 1) is the arry. (The units digit is also the remainder when we divide the sum by 10.) Let's have a look at our Problem of the Month, then. Problem
(2009 Fryer Contest)
The addition shown below, representing
2+22+222+2222+· · · , has 101 rows and the last term onsists of 101 2's :
2
2 2
2 2
2 2
2 2
2 2
··· C
B
A
.. .
+ 2
2 2 2 2
··· ···
2 2 2 2
2 2 2
.. .
16 (a) Determine the value of the ones digit A . (b) Determine the value of the tens digit B and the value of the hundreds digit C . ( ) Determine the middle digit of the sum. This problem looks pretty s ary at rst glan e. Despite this, at least (a) and (b) an be answered exa tly as in our warm-up problem. Let's do these parts and then think a bit about part ( ). We pro eed exa tly as we did above. The units' olumn
onsists of 101 opies of the digit 2. Therefore, the sum in the units' olumn is 101 × 2 = 202. We put down the 2 and arry 20. The tens' olumn onsists of 100 opies of the digit 2 plus the arry of 20. Therefore, the sum in the tens' olumn is 100 × 2 + 20 = 220. We put down the 0 and arry 22. The hundreds' olumn onsists of 99 opies of the digit 2 plus the arry of 22. Therefore, the sum in the hundreds' olumn is 99 × 2 + 22 = 220. We put down the 0 and arry 22. We an stop at this point, sin e we have determined the hundreds, tens, and units digits of the sum. Therefore, A = 2, B = 0, and C = 0. Solution to (a) and (b)
Great { that was mu h less s ary than it looked like it ould be. Now we need to try to ta kle ( ), whi h a tually is quite s ary. One approa h would be to pro eed by \brute for e" and work our way systemati ally olumn by olumn from the units' olumn towards the left. Of
ourse, we don't need to go all of the way to the leftmost olumn, sin e we
an stop when we get to the middle digit of the sum. Whi h digit will this be ? In order to answer this, we need to know how many digits the nal sum has. How many digits do you think that it has ? My best guess is 101 digits, sin e it seems pretty unlikely that the single 2 in the leftmost olumn is going to have enough of a arry from the olumn to its right to reate two-digit sum in this leftmost olumn. How do we know for sure that this is orre t ? If we knew this for sure, then the middle digit would be the 51st digit, sin e there would be 50 digits to its left and 50 digits to its right. Now, this 51st olumn onsists of 51 opies of the digit 2, so its sum is 102 plus whatever
arry omes from the olumn to the right. The olumn to the right onsists of 52 opies of 2, so its sum is 104 plus the arry from the olumn to its right, whose sum is at least 106 (that is, 106 from the 2's plus the arry). This is getting ompli ated ! Let's try this again with a bit of agreement on our terminology. We'll denote the leftmost olumn C1 and the rightmost olumn C101 ; we label the olumns in between in the logi al way. We also use sn to represent the sum in the nth olumn, in luding the arry. We saw above that the sum of the digits in C51 is 102, in C52 is 104, and in C53 is 106. Therefore, s53 ≥ 106. (We haven't in luded any arry here from C54.) Therefore, the arry from C53 to C52 is at least 10, so
17 s52 ≥ 104 + 10 = 114. Therefore, the arry from C52 to C51 is at least 11, so s51 ≥ 102 + 11 = 113. If s51 = 113, then the middle digit is 3, and we're done. But is it a tually the ase that s51 = 113 ? Could it be bigger ? If s51 was at least 114, then the arry from C52 to C51 would be at least 114 − 102 = 12, whi h would mean that s52 ≥ 120. If s52 ≥ 120, then the arry from C53 to C52 would be at least 120 − 104 = 16, so s53 ≥ 160. If s53 ≥ 160, then arry from C54 to C53 would be at least 160 − 106 = 54, so s54 ≥ 540. If s54 ≥ 540, then the arry from C55 to C54 would be at least 540 − 108 = 432, whi h is getting just plain silly, given that in parts (a) and (b) the arries that we got from the \largest olumns" were 22 only. So it seems pretty lear that s51 should be 113, so the middle digit should be 3. Now, I don't know about you, but I'm just about onvin ed. However, I'm not sure if \the middle digit should be 3" is all that rigorous and \just plain silly" ounts as a solid mathemati al proof. So we should prove some restri tion on the arries. Let's do this, and also write out a ohesive solution to part ( ). We'll use a bit of algebrai notation to simplify things.
We label the olumns as above and let sn be the sum in the nth
olumn, in luding the arry from the (n + 1)th olumn ; we denote this arry by cn+1 . Column n onsists of n opies of the digit 2, so sn = 2n + cn+1 . From our solution to (a) and (b), we know that c101 = 20 and that c100 = c99 = 22. Let's argue that cn ≤ 22 for all n with 1 ≤ n ≤ 101. We use an informal ba kwards indu tion. Suppose that cn+1 ≤ 22. (We know that this is true for n = 98, 99, 100.) Then sn = 2n + cn+1 is at most 2(101) + 22 = 224 and so cn ≤ 22. Thus, if cn+1 ≤ 22, then cn ≤ 22. Sin e c101 ≤ 22, then we an arry this hain along to show that cn ≤ 22 for all n with 1 ≤ n ≤ 101. We an use this to show that the sum has exa tly 101 digits. For the sum to have more than 101 digits, we would need to have s1 ≥ 10. But s1 = 2+ c2 , so this would mean that c2 ≥ 8 and so s2 ≥ 80. But s2 = 4+ c3 , so this would mean that c3 ≥ 76, whi h is not possible. Therefore, the sum has exa tly 101 digits. Finally, we an determine the 51st digit. We know that s51 = 102 + c52 and s52 = 104 + c53 and s53 = 106 + c54 . Sin e 0 ≤ c54 ≤ 22, then 106 ≤ s53 ≤ 128. Thus, 10 ≤ c53 ≤ 12. Sin e 10 ≤ c53 ≤ 12, then 114 ≤ s52 ≤ 116. Thus, c52 = 11, whi h means that s51 = 113, and so the 51st (that is, the middle) digit of the sum is 3. Solution to ( )
Let's make a ouple of observations to nish this o . First, a little bit of algebra and notation helped to save us a large number of words and onvoluted explanations. Se ond, a relatively simple topi like addition gave us a problem that requires some pretty high-level thinking. To me, one of the great beauties of mathemati s is that simpli ity and omplexity an be so
ompletely interwoven.
18
THE OLYMPIAD CORNER No. 283 R.E. Woodrow
Another year, and it is time to thank the many people who have ontributed solutions, problems, omments, and advi e during 2009. Arkady Alt Pavlos Maragoudakis Miguel Amengual Covas Robert Morewood George Apostolopoulos Bill Sands S efket Arslanagi D.J. Smeenk Ri ardo Barroso Campos Daniel Tsai Mi hel Bataille George Tsapakidis Jose Luis Daz-Barrero Edward T.H. Wang Oliver Geupel Konstantine Zelator Jean-David Houle Titu Zvonaru John Grant M Loughlin Thank you to both Jill Ainsworth, who produ ed the text for the Corner for the rst four issues, and to Joanne Canape, who ontinued the rest of the issues, for their skilled and tireless e orts to translate my s ribbles and notes into a ni e presentation. To start the New Year for the Corner, we give the problems proposed but not used at the 2007 IMO in Vietnam. My thanks go to Bill Sands, Canadian Team Leader, for olle ting them for our use. 2007 IMO in VIETNAM Problems Proposed But Not Used Contributing Countries. Austria, Australia, Belgium, Bulgaria, Canada, Croatia, Cze h Republi , Estonia, Finland, Gree e, India, Indonesia, Iran, Japan, Korea (North), Korea (South), Lithuania, Luxembourg, Mexi o, Moldova, Netherlands, New Zealand, Poland, Romania, Russia, Serbia, South Afri a, Sweden, Thailand, Taiwan, Turkey, Ukraine, United Kingdom, and the United States of Ameri a
. Ha Huy Khoai, Ilya Bogdanov, Tran Nam Dung,
Problem Sele tion Committee
Le Tuan Hoa, Geza Kos.
Algebra
. Consider those fun tions f
A1
: N → N whi h
satisfy the ondition
f (m + n) ≥ f (m) + f f (n) − 1
for all m, n ∈ N. Find all possible values of f (2007). (Here N denotes the set of positive integers.)
19 A2. Let n be a positive integer, and let x and y be positive real numbers su h that xn + yn = 1. Prove that n X 1 + x2k k=1
1+
x4k
. Find all fun tions f
A3
!
n X 1 + y 2k k=1
1+
: R+ → R+
f x + f (y)
!
y 4k
<
1 (1 − x)(1 − y)
.
su h that
= f (x + y) + f (y)
for all x, y ∈ R+ . (Here R+ denotes the set of positive real numbers.) . Let c > 2, and let a(1), a(2), . . . , be a sequen e of nonnegative real numbers su h that (a) a(m + n) ≤ 2a(m) + 2a(n) for all m, n ≥ 1, and A4
(b)
a 2k ≤
1 (k + 1)c
for all k ≥ 0.
Prove that the sequen e {a(n)}∞ n=1 is bounded. . Let a1 , a2 , . . . , a100 be nonnegative real numbers satisfying the relation 12 a21 + a22 + · · · + a2100 = 1. Prove that a21 a2 + a22 a3 + · · · + a2100 a1 < . A5
25
Combinatori s
C1
. Let n > 1 be an integer. Find all sequen es a1 , a2 , . . . , an
(a) (b)
ai ∈ {0, 1}
for all 1 ≤ i ≤ n2 + n, and
2 +n
ai+1 + ai+2 + · · · + ai+n < ai+n+1 + ai+n+2 + · · · + ai+2n
all 0 ≤ i ≤ n2 − n.
su h that holds for
C2. A unit square is disse ted into n > 1 re tangles whose sides are parallel to the sides of the square. Any line, parallel to a side of the square and interse ting its interior, also interse ts the interior of some re tangle. Prove that one of the re tangles has no point on the boundary of the square.
. Determine all positive integers n for whi h the numbers in the set S = {1, 2, . . . , n} an be oloured red and blue so that S × S × S ontains exa tly 2007 ordered triples (x, y, z) with these two properties :
C3
(a) x, y, z are of the same olour ; and (b) x + y + z is divisible by n. . Let A0 = (a1 , a2 , . . . , an ) be a sequen e of real numbers. For ea h integer k ≥ 0, form a new sequen e Ak+1 from Ak = (x1 , . . . , xn ) as follows :
C4
20 (a) Choose a partition {1, 2, . . . , n}
= I∪J
P
su h that
i∈I
xi −
P
xj
j∈J
is minimized (if I or J is empty, then the orresponding sum is 0 ; if several su h partitions exist, then hoose one arbitrarily). (b) Set Ak+1 = (y1 , y2 . . . , yn ), where yi = xi + 1 if i ∈ I , and yi = xi − 1 if i ∈ J . Prove that for some k, the sequen e Ak has a term x with |x| ≥ n2 . . In the Cartesian oordinate plane let Sn = {(x, y) : n ≤ x < n + 1} for ea h integer n, and paint ea h region Sn either red or blue. Prove that any re tangle whose side lengths are distin t positive integers may be pla ed in the plane so that its verti es lie in regions of the same olour.
C5
√
. Let α < 3 −2 5 be a positive real number. Prove that there exist positive integers n and p > α2n for whi h one an sele t 2p pairwise distin t subsets S1 , . . . , Sp , T1 , . . . , Tp of the set {1, 2, . . . , n} su h that Si ∩ Tj 6= ∅ for all 1 ≤ i, j ≤ p. C6
C7. A onvex n-gon P in the plane is given. For every three verti es of P , the triangle determined by them is good if all its sides are of unit length. Prove that P has at most 2n good triangles. 3 Geometry
. An isos eles triangle ABC with AB = AC is given. The midpoint of side BC is denoted by M . Let X be a variable point on the shorter ar M A of the ir um ir le of triangle ABM . Let T be the point in the angle domain BM A, for whi h ∠T M X = 90◦ and T X = BX . Prove that ∠M T B − ∠CT M does not depend on X . G1
. The diagonals of a trapezoid ABCD interse t at point P . Point Q lies between the parallel lines BC and AD su h that ∠AQD = ∠CQB , and line CD separates points P and Q. Prove that ∠BQP = ∠DAQ.
G2
G3. Let ABC be a xed triangle, and let A1 , B1 , C1 be the midpoints of sides BC , CA, AB , respe tively. Let P be a variable point on the ir um ir le of ABC . Let lines P A1 , P B1 , P C1 meet the ir um ir le again at A′ , B ′ , C ′ respe tively. Assume that the points A, B , C , A′ , B ′ , C ′ are distin t, and that the lines AA′ , BB ′ , CC ′ form a triangle. Prove that the area of this triangle does not depend on P .
. Let ABCD be a onvex quadrilateral, and let points A1 , B1 , C1 , and lie on sides AB , BC , CD, and DA, respe tively. Consider the areas of triangles AA1 D1 , BB1 A1 , CC1 B1 , and DD1 C1 ; let S be the sum of the two smallest ones, and let S1 be the area of quadrilateral A1 B1 C1 D1 . G4
D1
21 Find the smallest positive real number k su h that kS1 the ase.
≥S
is always
. Triangle ABC is a ute with ∠ABC > ∠ACB , in entre I , and ir umradius R. Point D is the foot of the altitude from vertex A, point K lies on line AD su h that AK = 2R, and D separates A and K . Finally, lines DI and KI meet sides AC and BC at E and F , respe tively. Prove that if IE = IF , then ∠ABC > 3∠ACB . G5
. Point P lies on side AB of a onvex quadrilateral ABCD. Let ω be the in ir le of triangle CP D, and let I be its in entre. Suppose that ω is tangent to the in ir les of triangles AP D and BP C at points K and L, respe tively, Let lines AC and BD meet at E , and let lines AD and BL meet at F . Prove that points E , I , and F are ollinear. G6
Number Theory
. Find all pairs of positive integers (k, n) su h that
N1
7k − 3n | k4 + n2
.
. Let b, n > 1 be integers. Suppose that for ea h k > 1 there exists an n integer ak su h that k | b − ak . Prove that b = An for some integer A. N2
. Let X be a set of 10, 000 integers, none of them divisible by 47. Prove that there exists a 2007-element subset Y of X su h that a − b + c − d + e is not divisible by 47 for any a, b, c, d, e ∈ Y . N3
. For every integer k ≥ 2, prove that 23k divides the number
N4
2k+1 2k
−
2k
2k−1
but 23k+1 does not. . Find all surje tive fun tions f : N → N su h that for every m, n ∈ N and every prime p, the number f (m + n) is divisible by p if and only if f (m) + f (n) is divisible by p. (N is the set of all positive integers.) N5
. For a prime p and a positive integer n, denote by νp (n) the exponent of p in the prime fa torization of n!. Given a positive integer d and a nite set of primes {p1 , p2 , . . . , pk }, show that there are in nitely many positive integers n su h that d | νp (n) for all 1 ≤ i ≤ k. N6
i
As a nal pair of ontests for your puzzling pleasure, we give two rounds of the Bundeswettbewerb Mathematik. Thanks go to Bill Sands, Canadian Team Leader to the 2007 IMO in Vietnam, for olle ting them for our use.
22 BUNDESWETTBEWERB MATHEMATIK 2006 Se ond Round
1. A ir le is divided into 2n ongruent se tors, n of them oloured bla k and n of them oloured white. Starting with an arbitrarily hosen se tor, the white se tors are numbered lo kwise from 1 to n. Subsequently, the bla k se tors are numbered ounter lo kwise from 1 to n, again starting at an arbitrary se tor. Prove that there exist n onse utive se tors ontaining all of the numbers from 1 to n.
. Let Q+ (resp. R+ ) denote the set of positive rational (resp. real) numbers. Find all fun tions f : Q+ → R+ that satisfy
2
f (x) + f (y) + 2xyf (xy) =
f (xy) f (x + y)
for all
x, y ∈ Q+ .
. The point P lies inside the a ute-angled triangle ABC and C ′ , A′ , B ′ are the feet of the perpendi ulars from P to AB , BC , CA. Find all positions of P su h that ∠BAC = ∠B ′ A′ C ′ and ∠CBA = ∠C ′ B ′ A′ . 3
4. A positive integer n is de ient if there are at most nine di erent digits in the de imal representation of n. (Leading zeroes are not ounted.) Prove that for any nite set S of de ient numbers, the sum of the re ipro als of its elements is less than 180. BUNDESWETTBEWERB MATHEMATIK 2007 First Round
. Show that one an distribute the integers from 1 to 4014 on the verti es and the midpoints of the sides of a regular 2007-gon so that the sum of the three numbers along any side is onstant.
1
. Ea h positive integer is oloured either red or green so that (a) The sum of three (not ne essarily distin t) red numbers is red. (b) The sum of three (not ne essarily distin t) green numbers is green. ( ) There is at least one green number and one red number. Find all olourings satisfying these onditions.
2
3. In triangle ABC the points E and F lie in the interiors of sides AC and BC (respe tively) so that |AE| = |BF |. Furthermore, the ir le through A, C and F and the ir le through B , C and E interse t in a point D 6= C . Prove that the line CD is the bise tor of ∠ACB .
. Let a be a positive integer. How many nonnegative integers x satisfy
4
j k j k x x = a a+1
?
23 Our solutions in the New Year begin with solutions from our readers to problems of the Bulgarian National Olympiad 2006 given in the Corner at [2008 : 409{410℄. . (Emil Kolev) Let △ABC be su h that ∠BAC = 30◦ and ∠ABC = 45◦ . −→ Consider all pairs of points X and Y su h that X is on the ray AC , Y is on − − → the ray BC , and OX = BY , where O is the ir um enter of △ABC . Prove that the perpendi ular bise tors of the segments XY pass through a xed point. Solution by Titu Zvonaru, Comane sti, Romania. Without loss of generality, supM pose that OA = OB = OC = 1. Sin e ∠BAC = 30◦ , we have that B ... ............ ∠BOC = 60◦ and BC = 1, that is, ... .......... ........ ... ........ ... △BOC is equilateral. O ........ ... ........ . ◦ ........ . ... Sin e ∠ABC = 45 , it follows . . ........ ... ........ ... ........ that △AOC has a right angle at O, ... ........ ... ........ ◦ hen e ∠OCA = ∠OAC = 45 and ........ . . ... √ ........ . ........ . AC = 2. ........ Y .... ........ ... ..... ... If X = A, then OX = 1 and ............................................................................................................................... BY = 1, and hen e Y = C ; as a A C X result, the xed point we seek lies on the perpendi ular bise tor of AC . Let M be the point on the same side of AC as O su h that △AM C is equilateral. Then ∠OCM = 60◦ − 45◦ = 15◦ , ∠M CB = 45◦ , and by the Law of Cosines in △M CB we obtain 5
.............. ... ..... ......
....... ...................... ................ .......... ..... . ................ ................ .... .... .... . . . . . . . . . . . . . . . . . . ... ........ .... .... ... ................ ... . ............................. ... . . . . . ... .. ................... .... .............. .. ... ... .... . . .. .............. . . ... . ... .............. ..... . ... . ................ . .. . ... . . . . . . .............. . .. ... ... . . .. . . . . . . . . . ... ................. .. . . . . . . ... ... . .... ..... .. . . . . .. . . ... . .... ...... ... .. . . ... . . . .... .. .. ..... . ... . . . . ... . . . .... .. ... ... ... . . . . .. . . . .... ... .. .. ... .. . . . . . . . .... ... .. . ... ... . . . . .. . .. . . . . .... . ... ..... .. . . . . . . .... ..... .. .. ..... . . . . . . . . . .... .... .... . .. . . ... . . . . .... .... . . ... .... .. .. .... .. .... ... .... .. .. .... .. .. .... .. . . . . .... ... . .. ..... .. ....... ... .... . .... ...................................................................... .......................................................................................................................
........ ........ ........ ..........
BM 2
= M C 2 + BC 2 − 2M C · BC cos ∠M CB √ 1 = 2 + 1 − 2 2 · √ = 1, 2
hen e △M CB has a right angle B . Let AX = α. By the Law of Cosines we have √ OX 2 = OA2 + AX 2 − 2OA · AX cos ∠OAX = 1 + α2 − α 2 , √ M X 2 = M A2 + AX 2 − 2M A · AX cos ∠M AC = 2 + α2 − α 2 ,
(1)
and by the Pythagorean Theorem we have √ M Y 2 = M B 2 + BY 2 = M B 2 + OX 2 = α2 − α 2 + 2 .
(2)
By (1) and (2) it follows that the point M belongs to the perpendi ular bise tors of the segments XY .
24 We ontinue with solutions from our readers to problems of the Indian Mathemati al Olympiad 2006 (Team Sele tion Problems) given in the Corner at [2008 : 410{412℄. . Let n be a positive integer divisible by 4. Find the number of permutations of (1, 2, 3, . . . , n) whi h satisfy the ondition σ(j) + σ−1 (j) = n + 1 for all j ∈ {1, 2, 3, . . . , n}. 1
σ
Solution by Mi hel Bataille, Rouen, Fran e. Let Sn be the set of all permutations of [n] = {1, 2, . . . , n} and let Qn
= =
{σ ∈ Sn : ∀j ∈ [n] , σ(j) + σ −1 (j) = n + 1} {σ ∈ Sn : ∀k ∈ [n] , σ ◦ σ(k) = n + 1 − k} .
We show that if n = 4m, then |Qn | = (2m)! = 2m Nm where Nm denotes m! the produ t 1 × 3 × · · · × (2m − 1) of the rst m odd natural numbers. Let σ ∈ Qn , k ∈ [n] and let j = σ(k). Then, j 6= k (otherwise k = n + 1 − k, ontradi ting the fa t that n + 1 is odd) and σ(j) σ(n + 1 − k) σ(n + 1 − j)
= = =
σ ◦ σ(k) = n + 1 − k , σ ◦ σ(j) = n + 1 − j , σ ◦ σ(n + 1 − k) = n + 1 − (n + 1 − k) = k .
Thus, the y le ontaining k is (k, j, n + 1 − k, n + 1 − j). Sin e k is arbitrary, the standard expression of σ as a produ t of disjoint y les (the y le de omposition of σ) onsists of m 4- y les of the form (k, j, n + 1 − k, n + 1 − j ). Conversely, if σ ∈ Sn has su h a y le de omposition, then learly σ ∈ Qn . Consider now the set S = {pk : k ∈ [2m]} where pk = {k, n + 1 − k} and let σ ∈ Qn . Using its y le de omposition, we asso iate with σ in a natural way a partitionS{P1 , P2 , . . . , Pm } where ea h Pk is a 2-subset of S (Pk ∩ Pl = ∅ if k 6= l ; m i=1 Pi = S ). There are Nm su h partitions (see the lemma below) and ea h of them is obtained from exa tly 2m elements of Qn , sin e any 2-subset P = {pk , pj } of S is obtained from two distin t 4- y les, namely (j, k, n + 1 − j, n + 1 − k) and (k, j, n + 1 − k, n + 1 − j). It follows that |Qn | = 2m Nm . If S is a set with |S| = 2m, then the number of partitions of S formed by 2-subsets of S is Nm = (2m − 1)(2m − 3) · · · (3)(1) = (2m)! . 2m m! Lemma
Proof. Fix s ∈ S . We partition S into 2-subsets by rst hoosing one of the 2m − 1 2-subsets {s, t}, where t ∈ S and t 6= s, and then augmenting this subset with a partition into 2-subsets of S − {s, t} (and there are Nm−1 su h partitions). Thus, Nm = (2m − 1)Nm−1 when m > 1, and the result follows sin e N1 = 1.
25 3. (Short list, IMO 2005) There are n markers, ea h with one side white and the other side bla k, aligned in a row with their white sides up. In ea h step (if possible) we pi k a marker with the white side up that is not an outermost marker, remove it, and turn over the losest marker to the left and the losest marker to the right of it. Prove that one an rea h a terminal state of exa tly two markers if and only if (n − 1) is not divisible by 3.
Solution by Oliver Geupel, Bruhl, NRW, Germany. We prove that if 3 ∤ (n − 1), then two markers an be left behind. This is lear if n = 2, 3. Now assume that by starting with n markers we an leave behind two markers, and that n + 3 markers are given. By su
essively
hoosing the se ond, third, then se ond marker from the left, we obtain n markers all white side up, and then we an nish with two markers. This
ompletes the proof by indu tion. It only remains to prove that if two markers an be left behind, then 3 ∤ (n − 1). In a xed state S , we let b(m) be the number of bla k to P markers the left of marker m. Further, we assign the number T (S) = (−1)b(m) m white
to the state S . Let B or W denote a marker with the bla k or white side up, respe tively ; then the admissible redu tion steps are (i) (ii)
BW B → W W , BW W → W B ,
(iii) (iv)
W W B → BW , W W W → BB .
Note that the parity of the number of B 's is invariant, hen e it is always even, and also we have T (BB) = 0, T (W W ) = 2, and for the initial state I with n white markers T (I) = n. It therefore suÆ es to prove that T (S) modulo 3 is invariant under the transitions (i)-(iv), be ause this implies that if F ∈ {BB , W W } is rea hable from I , then n = T (I) ≡ T (F ) 6≡ 1 (mod 3)
.
In the ase of transition (i), if the white marker m that is pi ked has value (−1)b(m) = v ∈ {−1, 1} in state S , then the two markers m′1 and m′2 whi h are turned over have values (−1)b(m ) = (−1)b(m ) = −v in the new state S ′ , whereas the values of all other markers remain un hanged, thus ′ 1
′ 2
T (S ′ ) = T (S) − v − 2v = T (S) − 3v ≡ T (S) (mod 3)
.
The transitions (ii) to (iv) are analyzed similarly. This ompletes the proof. . Let ABC be a triangle with inradius r, ir umradius R, a = BC , b = AC , and c = AB . Prove that
7
R 2r
≥
4a2 − (b − c)2
64a2 b2 c2 4b2 − (c − a)2
and with sides !2
4c2 − (a − b)2
.
26 Commentary by Miguel Amengual Covas, Cala Figuera, Mallor a, Spain. Solved by George Apostolopoulos, Messolonghi, Gree e. We give the omment of Amengual Covas. This problem appears as Problem 11195 of the Ameri an Mathemati al Monthly, Vol. 113 (January 2006), p. 79. The solution appears on p. 648 of the August{September 2007 issue of the Ameri an Mathemati al Monthly, Vol. 114, and in ludes two generalizations of the given inequality. Next we give the write-up of Apostolopoulos.
È
By Heron's formula, the area of △ABC is s(s − a)(s − b)(s − c), abc and also the same area is given by abc . Hen e, R = p . 4R 4 s(s − a)(s − b)(s − c) Furthermore, theparea of △ABC is rs, and a omparison with Heron's formula yields r = s(s − a)(ss − b)(s − c) , where s = a + 2b + c . Therefore, R
abc
=
2r
8(s − a)(s − b)(s − c)
.
(1)
By using the AM{GM Inequality, we obtain 4a2 − (b − c)2
= a2 + a2 + a2 + 4(s − b)(s − c) ≥ 4
È 4
= 4a
a2 a2 a2 4(s − b)(s − c)
È 4
4a2 (s − b)(s − c) .
Similarly, we have the inequality 4b2 −(c−a)2 ≥ 4b È and 4c2 − (a − b)2 ≥ 4c 4c2 (s − a)(s − b), so that 4
4a2 4a2 ≤
− (b −
c)2
4b2 4b2
a
È 4
·
4a2 (s
− (c −
a)2
·
È 4
4b2 (s − c)(s − a)
4c2 4c2
− (a − b)2 b
c · È · È 4 4 2 2 − b)(s − c) 4b (s − c)(s − a) 4c (s − a)(s − b)
Finally, we have
4a2 − (b − c)2
64a2 b2 c2 4b2 − (c − a)2
!2
4c2 − (a − b)2
a2 b2 c2
≤
È
≤
abc R = 8(s − a)(s − b)(s − c) 2r
64a2 b2 c2 (s − a)2 (s − b)2 (s − c)2
as desired, where the last equality is from (1).
.
.
27 8
. The positive divisors d1 , d2 , . . . , dl of a positive integer n are ordered 1 = d1 < d2 < · · · < dl = m .
Suppose it is known that d27 + d215 = d216 . Find all possible values of d17 . Solution by Titu Zvonaru, Comane sti, Romania. It is known (see the omment at the end of this solution) that if a, b, c are positive integers su h that a2 = b2 + c2 , then abc is divisible by 60 and one of a, b, c is divisible by 4. Let D = {d1 , . . . , dl } be the set of divisors of n. Sin e d27 + d215 = d216 , it follows that n is divisible by 60, hen e d1 = 1, d2 = 2, d3 = 3, d4 = 4, d5 = 5, d6 = 6 and 10 ∈ D . We dedu e that d7 ∈ {7, 8, 9, 10}. 2 2 Case 1. Suppose that d7 = 10. Then we have d16 − d15 = 100, and fa toring yields (d16 − d15 )(d16 + d15 ) = 100. Sin e d16 + d15 and d16 − d15 have the same parity, we must have d16 − d15 = 2 and d16 + d15 = 50, and hen e d15 = 24, d16 = 26. This means that 8 ∈ D , ontradi ting d7 = 10. Case 2. Suppose that d7 = 9. Then (d16 − d15 )(d16 + d15 ) = 81. Sin e d15 + d16 ≥ 15 + 16 = 31, we must have d16 − d15 = 1 and d16 + d15 = 81, and hen e d15 = 40, d16 = 41. This means that 8 ∈ D, ontradi ting d7 = 9. Case 3. Suppose that d7 = 8. Sin e 7 6∈ D , we dedu e d15 > 15, d16 > 16, hen e d15 + d16 ≥ 33. Then (d16 − d15 )(d16 + d15 ) = 64 has no solution, be ause d15 + d16 ≥ 33 and d16 + d15 and d16 − d15 have the same parity. Case 4. Suppose d7 = 7. Then ne essarily d16 − d15 = 1 and d16 + d15 = 49, and hen e d15 = 24, d16 = 25. If n is divisible by 9, 11, or 13, then d15 < 24, a ontradi tion. As a result, the positive divisors of n are i di
1 1
2 3 2 3
4 5 4 5
6 7 6 7
8 9 8 10
10 12
11 14
12 15
13 20
14 21
15 24
16 25
and we dedu e that d17 = 28. Comment. The fa t that 60 | abc whenever a2 = b2 + c2 an be seen as follows. There are positive integers m, n with m > n su h that a = m2 +n2 , b = m2 − n2 , c = 2mn. Let Ri = {x ∈ Z : x ≡ ±i (mod 5)}. • If m ∈ R0 or n ∈ R0 , then c ≡ 0 (mod 5). • If m, n ∈ R1 or m, n ∈ R2 , then b ≡ 0 (mod 5). • If m ∈ R1 and n ∈ R2 (or vi e-versa), then a ≡ 0 (mod 5). Hen e, 5 | abc. The divisibility by 3 and 4 is proved similarly. Next we present solutions from our readers to problems given in the November 2008 number of the Corner, and the Third Round, Senior Division, of the 2004 South Afri an Mathemati al Olympiad given at [2008 : 412{413℄. . Let a = 1111 · · · 1111 and b = 1111 · · · 1111, where a has forty ones and has twelve ones. Determine the greatest ommon divisor of a and b.
1
b
28 Solved by George Apostolopoulos, Messolonghi, Gree e ; and Edward T.H. Wang, Wilfrid Laurier University, Waterloo, ON. We give Wang's version. 1 40 1 12 10 −1 and b = 10 −1 . 9 9 1 − 1 and 1012 − 1 , and we also have 9
Let d = gcd(a, b). Observe that a = 1 40 10 9
Sin e d divides both
104 − 1 = 1040 − 1 − 1028 + 1016 + 104 d|
1012 − 1
, then
1 4 10 − 1 . 9
(1)
10
From (1) and (2), it follows that d =
1 4 10 − 1 = 1111. 9
3
Conversely, sin e 1040 −1 = 104 −1 and 1012 −1 = 104 −1 are both divisible by 104 −1, we see that both a and b are divisible by 19 104 −1 . Hen e, 1 4 10 − 1 | d . (2) 9
. Let n ≥ 2 be an integer. Find the number of integers x with 0 ≤ x < n and su h that x2 leaves a remainder of 1 when divided by n.
5
Solution by Mi hel Bataille, Rouen, Fran e. For ea h positive integer n let S(n) be the set of all integers x su h that 0 ≤ x < n and x2 ≡ 1 (mod n) and let s(n) denote its ardinality. We will prove that if λ(n) is the number of odd prime divisors of n and µ(n) is the greatest nonnegative integer su h that 2m divides n, then 8 < 2λ(n)
s(n) =
2λ(n)+1 : λ(n)+2 2
if if if
µ(n) = 0, 1 ; µ(n) = 2 ; µ(n) > 2 .
We rst show that s is a multipli ative fun tion. Clearly, s(1) = 1. Suppose that n = ab where a, b are oprime positive integers. If x ∈ S(n), then x2 ≡ 1 (mod ab), hen e x2 ≡ 1 (mod a) and x2 ≡ 1 (mod b) and therefore x ≡ y (mod a) and x ≡ z (mod b) for some unique pair of integers (y, z) ∈ S(a) × S(b). Conversely, if (y, z) ∈ S(a) × S(b), then the Chinese Remainder Theorem ensures that the system x ≡ y (mod a), x ≡ z (mod b) has a unique solution x with 0 ≤ x < ab = n. Then both a, b divide x2 − 1, hen e x2 − 1 ≡ 0 (mod ab) (sin e a, b are oprime) and so x ∈ S(n). Thus, S(n) and S(a) × S(b) orrespond bije tively and s(n) = s(a)s(b). It just remains to determine s(pr ) and s(2r ) where p is an odd prime and r is a positive integer. If x2 − 1 ≡ 0 (mod pr ), then p divides x − 1 or x + 1 but not both, or else it would divide (x + 1) − (x − 1) = 2. It follows that either x − 1 ≡ 0 (mod pr ) or x + 1 ≡ 0 (mod pr ). As a result, we have S(pr ) = {1, pr − 1} and s(pr ) = 2.
29 We readily verify that s(2) = 1, s(22 ) = 2. If r ≥ 3, then 2 is the highest power of 2 that an possibly divide both x − 1 and x + 1 whenever x2 − 1 ≡ 0 (mod 2r ). Hen e, in addition to the obvious solutions 1, 2r − 1 to the latter, we also have 2r−1 + 1 and 2r−1 − 1, orresponding to the ases 2r−1 |(x − 1), 2|(x + 1) and 2|(x − 1), 2r−1 |(x + 1), respe tively. Thus, s(2r ) = 4 whenever r ≥ 3. The result follows. Now we turn to the 2006 Vietnamese Mathemati al Olympiad given at [2008 : 413{414℄. . Find all real solutions of the system of equations
1
p
x2 − 2x + 6 · log3 (6 − y) = x ,
È p
y 2 − 2y + 6 · log3 (6 − z) = y ,
z 2 − 2z + 6 · log3 (6 − x) = z .
Solved by Jose Luis Daz-Barrero, Universitat Polite ni a de Catalunya, Bar elona, Spain ; and Titu Zvonaru, Comane sti, Romania. We give the solution of Daz-Barrero, modi ed by the editor. First, we observe that x, y, z ∈ (−∞, 6). To nd all real solutions we rst rewrite the system in the form y = 6−3 z = 6−3 x = 6−3
Let f (t) = 6 − 3
√
d dt
t t2 −2t+6
x x2 −2x+6
√
√
y
y 2 −26+6
z z 2 −2z+6
√
, , .
for t ∈ (−∞, 6). Sin e on the domain of f we have
t (6 − t) = √ 3/2 > 0 , t2 − 2t + 6 t2 − 2t + 6
then f is a stri tly de reasing fun tion, when e f (f (f (t))) is also a de reasing fun tion for t ∈ (−∞, 6). However, f (x) = y, f (y) = z , f (z) = x ; and thus f (f (f (x))) = x. We laim that if f (f (f (x))) = x, then f (x) = x. Indeed, let f n denote the n-fold omposition of f , and note that both f 3 (x) = x and f (x) < x yield f (x) = f (f 3 (x)) = f 3 (f (x)) > f 3 (x) = x, a ontradi tion. The ase f (x) > x similarly leads to a ontradi tion, and our laim is established. √ Now, 6 − x is a de reasing fun tion and 3 is in reasing for x ∈ (−∞, 6). Hen e, f (x) = x has at most one root. Sin e f (3) = 3, it follows that (x, y, z) = (3, 3, 3) is the unique real solution of the system. x
x2 −2x+6
30 2. Let ABCD be a given onvex quadrilateral. A point M moves on the line AB but does not oin ide with A or B . Let N be the se ond point of interse tion (distin t from M ) of the ir les (M AC) and (M BD), where (XY Z) denotes the ir le passing through the points X , Y , Z . Prove that
(a)
N
moves on a xed ir le,
(b) the line M N passes through a xed point. Solution to part (a) by Mi hel Bataille, Rouen, Fran e. Solution to part (b) by J. Chris Fisher, University of Regina, Regina, SK. (a) We denote by ∠(T U, V W ) the dire ted angle of the lines T U and V W . Let the diagonals AC and BD interse t at O. The point N moves on the ir le (CDO) as it immediately follows from the hara terization of on y li ity in terms of angles and the following al ulation : = = = =
∠(N C, N D) ∠(N C, N M ) + ∠(N M, N D) ∠(AC, AM ) + ∠(BM, BD) ∠(AC, BD) ∠(OC, OD) .
(b) Be ause of the use of dire ted angles, onvexity was not required in part (a). Likewise in part (b), A, B , C , and D an be any four points in the plane, no three ollinear. Let Γ be the ir le (CDO) from part (a). For any two positions of M on AB , say M1 and M2 , we know that the ir les (AM C) meet Γ at the orresponding points N , say N1 and N2 . It suÆ es to prove that the lines M1 N1 and M2 N2 interse t at a point of Γ. To this end, we de ne P to be the point where these two lines interse t, and we apply Miquel's theorem to triangle M1 M2 P and the points A on M1 M2 , N1 on M1 P , and N2 on M2 P . By onstru tion the ir les (AM1 N1 ) and (AM2 N2 ) meet at C . By Miquel's theorem the ir le (P N1 N2 ) also passes through C . Sin e Γ = (N1 N2 C), we on lude that P lies on Γ, as laimed. . Consider the fun tion
4
f (x) = −x +
È
(x + a)(x + b)
where a and b are distin t positive real numbers. Prove that for every real number s in the interval (0, 1), there exists a unique positive real number α su h that
f (α) =
as + bs 2
1/s
.
31 Solution by Mi hel Bataille, Rouen, Fran e. Let v, w lie in (0, ∞) with w > v. Then f (w) − f (v)
È
È
(w + a)(w + b) −
=
(v + a)(v + b) − (w − v)
(w + a)(w + b) − (v + a)(v + b)
=
È
=
(w − v)
(w + a)(w + b) +
N −1 D È
where N = v + w + a + b and D = By the AM{GM Inequality, D <
2w + a + b 2
hen e f (w) > f (v) and tinuous on (0, ∞) and
f
lim f (x) =
x→0+
È
.
(w + a)(w + b) +
+
2v + a + b 2
is stri tly in reasing on √
− (w − v)
(v + a)(v + b)
ab ,
= N
È
(v + a)(v + b).
,
(0, ∞).
Also,
a+b 2
lim f (x) =
x→∞
f
is on-
,
the latter holding be ause a + b + (ab/x) (x + a)(x + b) − x2 È f (x) = È = (x + a)(x + b) + x 1 + 1 + (a + b)/x + (ab)/x2
Thus,
.
√
is a bije tion from (0, ∞) onto (m0 , m1 ), where m0 = ab and s a+b a + bs 1/s m1 = . The s-mean of a and b is ms = , and we know 2 2 from the Power Mean Inequality that m0 < ms < m1 whenever 0 < s < 1. Sin e f is bije tive, ms = f (α) for some unique α ∈ (0, ∞). 5
f
. Find all polynomials P (x) with real oeÆ ients satisfying
P (x2 ) + x 3P (x) + P (−x)
= P (x)2 + 2x2 ,
for all real numbers x. Solution by Titu Zvonaru, Comane sti, Romania. First we will prove a lemma. 2 2 Lemma Let f be a polynomial that satis es f (x ) = f (x) for all x. Then m either f = 0 or f (x) = x . Proof : We will prove by indu tion that f x2 = f (x)2 . For p = 1 the identity holds by hypothesis. Assume the identity holds for p − 1 ≥ 1, then p
p
f x2
= f
p−1
x2
2
p−1
= f x2
2
=
p
p−1
f (x)2
2
p
= f (x)2
,
32 whi h ompletes the indu tion. Now we hoose a natural number p su h that g = 2p > deg f . Let x0 be any omplex root of f and let z1 , z2 , . . . , zg be the (distin t) omplex roots of z g = x0 . We then have
g
f (zi )
= f (zig ) = f (x0 ) = 0 ,
so that f (zk ) vanishes for ea h zk . We dedu e that the polynomial f has g > deg f distin t roots, or x0 = 0. Therefore, f = 0 or f (x) = axm for some number a. In the latter ase f (x2 ) = f (x)2 be omes ax2m = a2 x2m , hen e f ≡ 0 or f (x) = xm . The given equation, for x and −x, is
P (x2 ) + x 3P (x) + P (−x)
=
P (x)2 + 2x2 ,
P (x2 ) − x 3P (−x) + P (x)
=
P (−x)2 + 2x2 .
Subtra ting, we obtain
4x P (x) + P (−x)
=
P (x) − P (−x)
P (x) + P (−x)
,
whi h leads to two ases. Case 1. P (x) + P (−x) = 0. Here the following are equivalent : P (x2 ) + 2xP (x) P (x2 ) − x2 P (x2 ) − x2
= P (x)2 + 2x2 , = P (x)2 − 2xP (x) + x2 , =
2
P (x) − x
.
Thus, f (x) = P (x) − x satis es f (x2 ) = f (x)2 , and by the Lemma we have either f ≡ 0 and P (x) = x, or f (x) = xm and P (x) = xm + x. In the latter ase, sin e P (x) + P (−x) = 0, we have xm + x + (−x)m − x = xm + (−x)m = 0 ,
that is, m is odd. We on lude that P (x) = x or P (x) = x2n+1 +x, with n a nonnegative integer. Case 2. P (x) − P (−x) = 4x. Here the following are equivalent :
P (x2 ) + x 3P (x) + P (x) − 4x
P (x2 ) − 2x2 P (x2 ) − 2x2
= P (x)2 + 2x2 , = P (x)2 − 4xP (x) + 4x2 , =
2
P (x) − 2x
.
Thus, f (x) = P (x) − 2x satis es f (x2 ) = f (x)2 , and by similar reasoning as in Case 1, we dedu e that either P (x) = 2x or P (x) = xm + 2x.
33 In the latter ase, sin e P (x) − P (−x) = 4x, we have xm + 2x − (−x)m + 2x = 4x ,
or xm − (−x)m = 0, that is, m is even. So, in this ase, we obtain the polynomials x2n + 2x with n a nonnegative integer.
P (x) = 2x
and
P (x) =
n = 0 we have x2n+1 + x = 2x, so a omplete list of polynomials P (x) is x, x2n+1 + x, and x2n + 2x, where n is a nonnegative integer.
For
6. A set of integers T is alled sum-free if for every two (not ne essarily distin t) elements u and v in T , their sum u + v does not belong to T . Prove that (a) a sum-free subset of S = {1, 2, . . . , 2006} has at most 1003 elements, (b) any set S onsisting of 2006 positive integers has a sum-free subset
onsisting of 669 elements. Solution by Oliver Geupel, Bruhl, NRW, Germany. For part (a), £ we laim that a sum free subset T of S = {1, 2, . . . , n} has at most n2 elements. To prove this fa t, let m = max S . If m is even © then ea h of the sets {1, m − 1}, {2, m − 2}, . . . , m 2− 2 , m 2+ 2 ontains n at most one element of T ; hen e |T | ≤ m ≤ . Now suppose that m is odd. 2 2 © Then ea h of the sets {1, m − 1}, {2, m − 2}, . . . , m 2− 1 , m 2+ 1 ontains at most one element of S ; thus |S| ≤ m 2+ 1 . If n is even, then m 2+ 1 ≤ n2 , n£ 1 = while if n is odd, then m 2+ 1 ≤ n + . This ompletes the proof of 2 2 part (a). For part (b), we laim that any set £ S onsisting of n positive integers has a sum free subset onsisting of n3 elements. To prove this, hoose a prime number p > max S su h that 3 | (p + 1), whi h is possible by Diri hlet's theorem. Let
§
I =
k∈N:
p+1 2p − 1 ≤ k ≤ 3 3
ª
.
Consider the bipartite graph with sets of nodes P = {1, 2, . . . , p − 1} and I , where a node k ∈ P is adja ent to a node l ∈ I if and only if there exists a number a ∈ S su h that ka ≡ l (mod p). Note that for ea h edge, the number a ∈ S is unique, and label the respe tive edge with the number a. 1 For ea h a ∈ S there are exa tly |I| = p + numbers k ∈ P su h that ka 3 has a residue modulo p whi h belongs to I , hen e our graph has n(p 3+ 1) edges. By the Pigeonhole Prin iple, there is a node k ∈ P with degree not
34 £
+ 1) less than n(p , hen e not less than n3 . Let T ⊆ S be the set of labels 3(p − 1) of its respe tive edges. £ We laim that T has the required properties. Clearly, |T | ≥ n3 . Assume that a + b = c for some a, b, c ∈ T . Then ka, kb, kc are ea h ongruent modulo p to numbers in I . Moreover, ka + kb = kc, so that ka + kb is
ongruent modulo p to a number in I . On the other hand, it is easy to he k that for all l, l′ ∈ I , the residue modulo p of the number l + l′ does not belong to I . This ontradi ts the hyothesis a + b = c, and ompletes our proof.
Next we move to solutions from our readers to problems proposed but not used for the 47th International Mathemati al Olympiad 2006 in Slovenia given at [2008 : 459{464℄. . Given an arbitrary real number a0 , de ne a sequen e of real numbers by the re ursion
A1
a0 , a1 , a2 , . . .
ai+1 = ⌊ai ⌋ · {ai } ,
i ≥ 0,
where ⌊ai ⌋ is the greatest integer not ex eeding ai , and {ai } Prove that ai = ai+2 for suÆ iently large i.
= ai − ⌊ai ⌋.
Solution by Oliver Geupel, Bruhl, NRW, Germany. We onsider the three ases a0 = 0, a0 > 0, and a0 < 0 separately. If a0 = 0, then the sequen e (ai ) is onstant. Next, suppose a0 > 0. Then all ai are nonnegative. Let ⌊ai ⌋ = n and {ai } = r . If n = 0, then ai+1 = ai+2 = ai+3 = · · · = 0. Otherwise we have n ≥ 1 and ai − ai+1 = (n + r) − nr = (n − 1)(1 − r) + 1 ≥ 1 ; hen e we obtain 0 ≤ ai+n < 1, whi h redu es to the previous ase. Lastly, suppose a0 < 0. Then a0 ≤ a1 ≤ a2 ≤ · · · ≤ 0. Hen e, the integer sequen e (⌊ai ⌋) is non-de reasing and bounded above by 0. If just one term of this sequen e is 0, then (ai ) terminates in zeros and we are done. The other possibility is that there exist positive integers i0 and n su h that for all i ≥ i0 we have ⌊ai ⌋ = −n. Let {ai } = r. We will prove by indu tion that for ea h nonnegative integer k, 0
ai0 +k = −
n2 + (n − nr − r)(−n)k n+1
.
(1)
The equation (1) is immediate if k = 0. For the indu tive step, assuming (1),
35 we obtain ai0 +k+1
−n(ai0 +k) + n)
=
2
−n + n
=
−
=
n2 + (n − nr − r)(−n)k n+1
2
n + (n − nr − r)(−n)k+1 n+1
,
thus ompleting the proof of (1) by indu tion. If n > 1, then we obtain from (1) that lim |ai +k | = ∞. But this k→∞
ontradi ts our hypothesis that ⌊ai ⌋ = −n for i ≥ i0 . Consequently, n = 1. Then ai = −1+r, ai +1 = −r = −1+(1−r), and ai +2 = −(1−r) = ai , whi h ompletes the proof. 0
0
0
0
0
. Let a1 , a2 , . . . , an be positive real numbers. Prove that
A4
X i<j
X ai aj n ≤ ai aj . ai + aj 2(a1 + a2 + · · · + an ) i<j
Solution by Mi hel Bataille, Rouen, Fran e. Equality holds for n = 2, so we will suppose that n ≥ 3. We laim that if a, b, c are positive real numbers, then 1 1 1 1 + + ≤ b+c c+a a+b 2
1 1 1 + + a b c
2 is the harmoni mean of Proof : Observe that x + y y ). Using the AM{HM Inequality, it follows that
2 b+c
+
2 c+a
+
2 a+b
1 x
and
1 y
.
(1)
(for positive x,
1 1 1 1 1 1 + + + b c c a a b = 1 + 1 + 1 ≤ + +
2
2
2
a
b
c
.
Ba k to the problem. The proposed inequality is equivalent to (a1 + a2 + · · · + an )
whose left-hand side is
P
ai aj +
i<j
Thus, (2) is equivalent to L ≤
X
ai aj
i<j
ai + aj
P i<j
ai aj ai + aj
n−2X 2
i<j
≤
nX 2
P k6=i,j
ai aj .
ai aj ,
(2)
i<j
ak
=
P i<j
ai aj + L.
(3)
36 Note that L =
P
ai aj ak
i,j,k≤n
1 1 1 + + ai + aj aj + ak ak + ai
, the sum taken
over distin t positive integers i, j , k. By (1) above, ≤
L
X 1≤i<j
X
=
ai aj ak 2
ai
a a i j
+
2
1≤i<j
1
+
1
+
aj
1 ak
aj ak ak ai + = 2 2
X 1≤r<s≤n
(n − 2)
ar as 2
,
and (3) is obtained, ompleting the proof. . Let a, b, and c be the lengths of the sides of a triangle. Prove that
A5
√ √ √ b+c−a c+a−b a+b−c √ √ + √ √ √ √ + √ √ √ ≤ 3. b+ c− a c+ a− b a+ b− c
Solution by Titu Zvonaru, Comane sti, Romania. √ √ √ Let x = a, y = b, z = c. By the well-known inequality (α + β + γ)2 obtain :
p
X
y li
2
−x2 + y 2 + z 2 −x + y + z
≤ 3
≤ 3 α2 + β 2 + γ 2
X −x2 + y 2 + z 2
y li
(−x + y + z)2
we
.
The following inequalities are then equivalent X −x2 + y 2 + z 2
y li
⇐⇒
(−x + y + z)2
≤ 3 ⇐⇒
X 2x2 − 2xy − 2xz + 2yz
y li
(−x + y +
z)2
X
y li
1−
≥ 0 ⇐⇒
−x2 + y 2 + z 2
(−x + y + z)2
X (x − y)(x − z)
y li
(−x + y + z)2
≥ 0 ≥ 0.
To prove the last inequality above, we may assume that x ≥ z , y ≥ z . After some algebra, we have : (x − y)(x − z) (−x + y +
+
z)2
= (x − y) ·
(y − z)(y − x) (x − y + z)2
(x − z)(x − y + z)2 − (y − z)(−x + y + z)2
= (x − y)2 ·
(−x + y + z)2 (x − y + z)2
(x − y)2 + 2z(x + y − 2z) + z 2 (−x + y + z)2 (x − y + z)2
≥ 0,
37 − x)(z − y) be ause x + y ≥ 2z . Also, (z ≥ 0, sin e x ≥ z and y ≥ z . (−z + x + y)2 Therefore, the last of the pre eding equivalent inequalities is true, hen e the original inequality is true. Equality holds if and only if x = y = z , that is a = b = c.
. There are n ≥ 2 lamps L1 , L2 , . . . , Ln arranged in a row. Ea h of them is either on or o . Initially the lamp L1 is on and all of the other lamps are o . Ea h se ond the state of ea h lamp hanges as follows : if the lamp Li and its neighbours (L1 and Ln ea h have one neighbor, any other lamp has two neighbours) are in the same state, then Li is swit hed o ; otherwise, Li is swit hed on. Prove that there are (a) in nitely many n for whi h all of the lamps will eventually be o , (b) in nitely many n for whi h the lamps will never be all o . Solved by Oliver Geupel, Bruhl, NRW, Germany. First, we prove by mathemati al indu tion that, if n = 2k where k is a positive integer, all lamps are on after n − 1 steps, while not all lamps have equal states after ea h of the steps 1, 2, . . . , n − 2. This is lear for k = 1. Let n = 2k and assume the leftmost m = n2 lamps are on after m − 1 steps. This is valid, as the m rightmost lamps do not hange during the rst m − 1 steps. After step m the two middle lamps are on and the other lamps are o . Afterwards, the on/o -pattern is symmetri about the entre, and from then on the two middle lamps will have the same state. Hen e, the state of Lm is only a e ted by Lm−1 , so the state of (Lm , Lm−1 , . . . , L1 ) after step m+j oin ides with that of (L1 , L2 , . . . , Lm ) after step j . Hen e, after n − 1 steps the m leftmost lamps are again on, and by symmetry so are the m rightmost lamps. Moreover, not all the lamps are in the same state before then. The indu tion is omplete. Thus, for n = 2k , all lamps are o after n steps, ompleting part (a). For part (b), we laim that the lamps will never all be in the same state if n = 2k + 1. To see this, note that after n − 2 steps the lamps L1 , L2 , . . . , Ln−1 are on and Ln is o . Moreover, by the analysis for part (a), the lamps are never all in the same state before then. After step n − 1, the lamps Ln−1 and Ln are on and the rest are o . At this moment, the state of (Ln , Ln−1 , . . . , L1 ) oin ides with that of (L1 , L2 , . . . , Ln ) after the rst step. Therefore, the state of (L1 , L2 , . . . , Ln ) after step j ≥ 1 is the same as that of (Ln , Ln−1 , . . . , L1 ) after step n − 2 + j . Hen e, the sequen e of states is eventually periodi with minimal period 2(n − 2), and the lamps are never all in the same state. C1
. Let P be a onvex polyhedron with no parallel edges and no edge parallel to a fa e other than the two fa es it borders. A pair of points on P are antipodal if there exist two parallel planes ea h ontaining one of the points and su h that P lies between them. Let A be the number of antipodal pairs of verti es and let B be the number of antipodal pairs of midpoints of edges. Express A − B in terms of the numbers of verti es, edges, and fa es of P . C6
38 Solution by Oliver Geupel, Bruhl, NRW, Germany. Let F1 , F2 , . . . , Ff be the fa es of P and n1 , n2 , . . . nf the respe tive outward normal unit ve tors. Consider a graph G on the unit sphere S entred at the origin O. The verti es of G are the end points V1 , V2 , . . . , Vf of the position ve tors n1 , n2 , . . . , nf . An edge Vi Vj is drawn as an ar on a great
ir le of S if and only if the fa es Fi and Fj of P have a ommon edge. The graph G is dual to P , in that ea h vertex V , ea h edge E , and ea h fa e F of P
orresponds to a unique fa e d(V ), edge d(E), and vertex d(F ), respe tively, of G . Let P have f fa es, e edges, and v verti es, then G has v fa es, e edges, and f verti es. Let σ be the re e tion of S with respe t to the point O. Then G is mapped to another graph σ(G) = G ′ . Finally we merge G and G ′ into a new graph, G˜. The verti es of G˜ are the verti es of G ∪ G ′ and the points of interse tion of edges of G with edges of G ′ . The edges of G˜ are all segments of edges of G ∪ G ′ . Consider the planes π that ontain an edge E of P bordering fa es Fi and Fj . The outward normal unit ve tors of these planes π all lie on the great
ir le of S ontaining d(E) in G . The plane π does not interse t the interior of P if and only if its outward normal unit ve tor is on the edge (that is, ar ) d(E). Parallel edges of P orrespond to ar s on the same great ir le of S . An edge E is parallel to a fa e F in P if and only if d(E) and the vertex d(F ) are on the same great ir le of S . By hypothesis, all edges of G˜ are on distin t great ir les, and no vertex of G˜ lies on the same great ir le as a non-adja ent edge. The edges Ei and Ej of P have antipodal midpoints if and only if there are planes πi and πj ontaining Ei and Ej , respe tively, and with opposite normal ve tors, that is, if d(Ei ) and σ d(Ej ) interse t on S . Hen e, G˜ has a total of v˜ = 2f + 2B verti es. Ea h of the 2B verti es splits 2 edges ; hen e G˜ has e˜ = 2e + 4B verti es. Consider a plane π ontaining a vertex V of P if and only if its outward normal unit ve tor is in the fa e of G on S bordered by the edges d(E1 ), d(E2 ), . . . , d(Ek ). Thus, Vi and Vj of P are antipodal if and only if verti es the fa es d(Vi ) and σ d(Vj ) are non-disjoint on G˜. Therefore, the number of fa es of G˜ is f˜ = 2A. By Euler's polyhedral formula, we obtain 0
= v ˜ + f˜ − e˜ − 2 = 2f + 2B + 2A − 2e − 4B − 2 = 2(A − B) + 2(f − e − 1) = 2(A − B) + 2(1 − v) .
Consequently, A − B verti es of P .
= v−1
and A − B depends only on the number of
That ompletes the Corner for this issue. Send me your ni e solutions and generalizations.
39
BOOK REVIEWS Amar Sodhi
When Less is More : Visualizing Basi Inequalities By Claudi Alsina and Roger Nelsen, Mathemati al Asso iation of Ameri a, 2009 ISBN 978-0-88385-342-9, hard over, 164 pages, US$58.95 Reviewed by Bru e Shawyer, Memorial University of Newfoundland, St. John's, NL I have always (at least, sin e my High S hool days) been a great believer in the power of Geometry to lead one into understanding Mathemati s. Let no one ignorant of Geometry enter here. Tradition has it that this phrase was engraved at the door of Plato's A ademy, the s hool he had founded in Athens. Pro lus tells us about 750 years later that Ptolemy Soter, the rst King of Egypt and the founder of the Alexandrian Museum, patronized the Museum by studying geometry there under Eu lid. He found the subje t diÆ ult and one day asked his tea her if there was not some easier way to learn the material. To this Eu lid replied, Oh King, in the real world there are two kinds of roads, roads for the ommon people to travel upon and roads reserved for the King to travel upon. In Geometry there is no royal road. Claudi Alsina and Roger Nelsen's book expounds the prin iple that many inequalities be ome mu h more apparent when they an be visualized. Of
ourse, Roger Nelsen is famous for his \Proofs without Words" that are wonderful examples of this prin iple. To quote Charles Ashba her : Proofs without words will not work everywhere, but when they do, it an be the di eren e that makes the light bulb of understanding burn bright. This book takes a range of inequalities from the simplest and best known to the more ompli ated and somewhat obs ure. The exposition is well presented with easy to follow diagrams and there are hallenges to the reader in every se tion. I should like to illustrate an example to give a avour of what to expe t. . First, we show that the length of any side of a triangle is less than or equal to the sum of the lengths of the other two sides. The subadditive property of the square root fun tion
40 C
I
... .... ............... ....... ....................... .... .. .... .......... ... ... ......... . .... . ......... ... .... .. ......... ... .... .... ......... . . ... ......... .. ... . . . . ......... ... . .. . . ......... . . . ... . ......... ... . . . . .. ......... . ... . . . ......... . . .. . .. ......... . . . . . . . ......... ... ... .. . ......... . . .. ......... ... ... . . . . .. ......... .. . . . . . ......... . . ... . ......... ... . . . . .. ......... .. ... . . . ......... . ... .. .. ......... . . . . . ... ......... .. ... . . . .......................................................................................................................................................................................................................................................................................................................................
a
B
b
?
a
? c
A
-
b
√
√
Now, we take a right triangle with legs of lengths a and b. √ Use of the Pythagorean Theorem gives the length of the hypotenuse as a + b. ........... .......... ..... .......... . .......... .... .......... . . . . . . . . .... . ... .......... .... .......... . . . . . . . . .... . ....... . . . . . . . . ... . ....... . . . . . . . .... . . ....... . . . . . . . . .... . ...... . . . . . . . . .... . ....... . . . . . . . . ... . ....... . . . . . . . . ... . ...... . . . . . . . . .... . ....... . . . . . . . . .... . ....... . . . . . . . . ... . ...... . . . . . . . . .... . ....... . . . . . . . . .... . ....... . . . . . . . . .... . ....... . . . . . . . . .... . ....... . . . . . . . . ... . ....... . . . . . . . .... . . ...... . . . . . . . . . .....................................................................................................................................................................................................................................................................................................................................
a+b
√
√
a
................ .........
√
b
√
√
√
An appli ation of the rst result shows that a + b ≤ a + b. This book should be in the personal library of everyone who tea hes Mathemati s where inequalities ome into the urri ulum. And this means that almost everyone who tea hes Mathemati s should own this book. I Want to be a Mathemati ian, A Conversation with Paul Halmos A DVD produ ed and dire ted by George Csi sery, Zala Films, for the Mathemati al Asso iation of Ameri a, 2009 ISBN 978-0-88385-909-4, Running time : 44 minutes, US$39.95 Reviewed by Brenda Davison, Simon Fraser University, Burnaby, BC In the DVD, 'I Want to be a Mathemati ian', Paul Halmos (1916-2006) is interviewed late in his areer by Peter Renz, primarily about his tea hing. Interspersed are interviews with several people who worked or studied with Halmos, notably an emotional Don Sarason whom Halmos onsidered to be his best student. The title of the DVD follows from the title of Halmos' book I Want to be a Mathemati ian, an Automathography in Three Parts but the ontent does not. Where the book is really an ex ellent meditation on one person's journey from hemi al engineering to philosophy, ending in mathemati s, the DVD fo uses primarily on the tea hing of mathemati s. For Halmos, the best tea hing onsisted of the Moore method with softened edges. The Moore method is a dis overy based tea hing te hnique where the tea her does not
41 tell but rather asks and leads students to dis over the ideas for themselves. Perhaps the reason for this emphasis is that, in the end, Halmos onsiders himself to be primarily an expositor of mathemati s | his tea hing and his textbooks are what he is most proud of. The te hni al aspe ts of the DVD are good : the lighting, amera motion, the speed of the presentation, the Ba h violin ba kground musi make for an easy to wat h, easy to follow introdu tion to Halmos. The DVD should appeal to two groups of people : 1) those starting their tea hing areer, after having already de ided to make mathemati s their subje t and who are re e ting on how best to onvey mathemati al ontent to their students, and 2) those who are de iding whether or not to take on mathemati s as an undergraduate or graduate major. This se ond group will not be served solely by the DVD. For this group, the fun tion of the DVD will be to provide a short, easy introdu tion to Halmos whi h an then be followed by reading some or all of the book of the same title. The transition is made easy by the in lusion of several long ex erpts from the book on the DVD. These an be read on a Windows or Ma intosh based omputer as DVD-ROM ontent and will allow a qui k and inexpensive look into Halmos' book prior to ommitting to pur hasing it. I would most de nitely re ommend that someone onsidering mathemati s as a areer buy and read the book. Halmos is honest about himself, his profession, the people around him and he is parti ularly areful not to present himself as a nished, polished pa kage. This provides the reader with the opportunity to glimpse a mathemati ian in the making. Someone interested in studying in the United States will also bene t from dis ussion that spans the last 70 years of Ameri an mathemati al a tivity in su h geographi al dispersed areas as the Institute for Advan ed Study in Prin eton, Syra use, Indiana and Santa Clara Universities, and the Universities of Mi higan, Hawaii and Illinois. The well-written book has the added advantage that the mathemati s that Halmos produ ed is dis ussed in an a
essible way. Furthermore, many di erent topi s are tou hed upon as Halmos hanged his fo us from one area of mathemati s to another several times throughout his areer. So, wat h the DVD and allow it to lead you to the book.
42
On an Inequality from the IMO 2008 Nikolai Nikolov and Svilena Hristova
The following problem is from the IMO 2008 : 2
2
2
x y z (IMO 2008) Prove that (1 − + + ≥ 1 for x)2 (1 − y)2 (1 − z)2 all real numbers x, y, z , ea h di erent from 1, and satisfying xyz = 1. Problem 2(a)
Repla ing x, y, z respe tively by x1 , y1 , z1 , the inequality be omes 1 1 1 + + ≥ 1. (1 − x)2 (1 − y)2 (1 − z)2
The aim of this note is to show that this inequality remains true for three or more variables. More pre isely, we have the following. Let n ≥ 2 be an integer and let x1 , x2 , . . . , xn be real numbers, n P 1 ea h di erent from 1, and satisfying x1 x2 · · · xn = 1. Let Sn = . (1 − x )2 Proposition 1
i=1
i
(a) If n = 2, then Sn ≥ , with equality if and only if x = y = −1. (b) If n = 3, then Sn ≥ 1, with equality if and only if x + y + z = 3. ( ) If n = 4, then Sn ≥ 1, with equality if and only if x = y = z = t = −1. (d) If n ≥ 5, then Sn > 1. The inequality is sharp. Proof : Clearing the fra tions in (a), the inequality be omes x2 + y2 ≥ 2xy, that is, (x − y)2 ≥ 0. Clearing the fra tions in (b), the inequality be omes (x+y+z−3)2 ≥ 0. To prove ( ) and (d), we shall use the following result (see [2℄, and also the remark at the end of [1℄) : If y1 , y2 , . . . , yn are positive real numbers, 1 − n ≤ α < 0, n n Q P and yi = λn , then (1 + yi )α ≥ min {1 , n(1 + λ)α }. The i=1 i=1 inequality is sharp, with equality if and only if n(1 + λ)α ≤ 1 and y1 = y2 = · · · = yn = λ. This result implies ( ) and (d) by setting α = −2, λ = 1, yi = |xi |, and using the fa t that (1 −1x )2 ≥ (1 +1y )2 . i i A more dire t approa h for proving ( ) and (d) is to use the inequality 1 1 1 + ≥ for a, b ≥ 0. This inequality holds sin e it is (1 + a)2 (1 + b)2 1 + ab 1 2
Copyright
c 2010
Canadian Mathemati al So iety
Crux Mathemati orum with Mathemati al Mayhem, Volume 36, Issue 1
43 equivalent to the obvious inequality (ab − 1)2 + ab(a − b)2 follows immediately : 4 X i=1
≥ 0.
Then ( )
1 1 1 ≥ + = 1. (1 − xi )2 1 + |x1 x2 | 1 + |x3 x4 |
To prove (d), it is enough to observe that n X
1
i=1
(1 − xi )2
≥
n X i=1
1 1 + |x1 x2 |
+
1 1 + |xi |
n X
i=3
2 ≥
1
1 + |xi |
and then apply indu tion on n.
2
n X 1 1 ≥ 2 + 2 1 + |x1 x2 | i=3 1 + |xi |
More is true when all the variables are positive. With notation as in Proposition 1, if additionally x1 , . . . , xn n P 1 are positive, then > 1. The inequality is sharp. (1 − x )2 Proposition 2
i=1
i
Proof : For n = 2, by learing fra tions, the inequality be omes x + y > 2, √ 2 that is, x − √y > 0. It remains only to note that x = y implies that x = y = 1. For n = 3 we know that stri t inequality holds in Proposition 1(b) when (x + y + z − 3)2 > 0. In the present ase it then suÆ es to observe that √ x + y + z ≥ 3 xyz = 3, with equality if and only if x = y = z = 1. If n ≥ 4, the inequality follows from Proposition 1, parts ( ) and (d). Finally, to see that the inequality is sharp, set x1 = · · · = xn−1 = j , 1 xn = n−1 , and let j → ∞. j 3
Referen es
[1℄ O. Mushkarov and N. Nikolov, Some generalizations of an inequality from IMO 2001, CRUX Mathemati orum with Mathemati al Mayhem, Vol. 28, No. 5 (2002) pp. 308-312. [2℄ O. Mushkarov and N. Nikolov, Variations on an inequality from IMO 2001, Mathemati s and Edu ation in Mathemati s, Vol. 32 (2003) pp. 323-327. (arXiv:math.HO/0605380v1) Nikolai Nikolov
[email protected]
Institute of Mathemati s and Informati s Bulgarian A ademy of S ien es 1113 So a, Bulgaria
Svilena Hristova
[email protected]
44
PROBLEMS Solutions to problems in this issue should arrive no later than 1 August 2010. An asterisk (⋆) after a number indi ates that a problem was proposed without a solution. Ea h problem is given in English and Fren h, the oÆ ial languages of Canada. In issues 1, 3, 5, and 7, English will pre ede Fren h, and in issues 2, 4, 6, and 8, Fren h will pre ede English. In the solutions' se tion, the problem will be stated in the language of the primary featured solution. The editor thanks Jean-Mar Terrier of the University of Montreal for translations of the problems.
. Proposed by Hassan A. ShahAli, Tehran, Iran. Let N be the set of positive integers, E the set of all even positive integers, and O the set of all odd positive integers. A set S ⊆ N is losed if x + y ∈ S for all distin t x, y ∈ S , and un losed if x + y 6∈ S for all distin t x, y ∈ S . Prove that if N is partitioned into A and B , where A is losed and nonempty, and B is un losed and in nite, then A = E and B = O. 3501
. Proposed by Jose Luis Daz-Barrero, Universitat Polite ni a de Catalunya, Bar elona, Spain. Find all real solutions of the following system of equations
3502
x21 + x22 + x2n +
È
È
x22 + 21
=
x23 + 21 ···
= ···
x21 + 21
=
È È
x22 + 77 ,
È
x23 + 77 , ···
È
x21 + 77 .
. Proposed by Bru e Shawyer, Memorial University of Newfoundland, St. John's, NL. Given a triangle and the midpoints of its sides, with the use of a straight edge and only three uses of a pair of ompasses, bise t all three angles of the triangle.
3503
. Proposed by Mariia Rozhkova, Kiev, Ukraine. Given triangle ABC , set Q = a cos2 A + b cos2 B + c cos2 C , and let ABC have area S and ir umradius R. Prove that S (a) Q ≥ R , with equality if and only if ABC is equilateral. 3504
(b)
S
√
2
if ABC is not obtuse, with equality if and only if ABC is an isos eles right triangle. Q≤
R
45 . Proposed by Yakub N. Aliyev, Qafqaz University, Khyrdalan, Azerbaijan. The ir les Γ1 and Γ2 have a ommon entre O, and Γ1 lies inside Γ2 . The point A 6= O lies inside Γ1 and a ray through A interse ts Γ1 and Γ2 at the points B and C , respe tively. Let E be a point on the line BC su h that DE is perpendi ular to BC . Prove that AB = EC if and only if OA is perpendi ular to BC . 3505
. Proposed by Pedro Henrique O. Pantoja, UFRN, Brazil. Prove that Q(n) + Q n2 + Q n3 is a perfe t square for in nitely many positive integers n that are not divisible by 10, where Q(n) is the sum of the digits of n. 3506
. Proposed by Pham Huu Du , Ballajura, Australia. Let a, b, and c be positive real numbers. Prove that
3507
Ê
a(b + c) + a2 + bc
Ê
b(c + a) + b2 + ca Ê
≤
Ê
c(a + b) c2 + ab
1 1 1 2(a + b + c) + + a+b b+c c+a
.
. Proposed by Hung Pham Kim, student, Stanford University, Palo Alto, CA, USA. Let a, b, c, d be nonnegative real numbers su h that a + b + c + d = 4. Prove that 3508
√ √ √ √ √ a bc + b cd + c da + d ab ≤ 2 1 + abcd .
. Proposed by Hung Pham Kim, student, Stanford University, Palo Alto, CA, USA. Let a, b, and c be nonnegative real numbers su h that a + b + c = 3. For ea h positive real number k, nd the maximum value of 3509
a2 b + k
b2 c + k
c2 a + k
.
. Proposed by Cosmin Pohoata , Tudor Vianu National College, Bu harest, Romania. Let d be a line exterior to a given ir le Γ with entre O. Let A be the orthogonal proje tion of O on the line d, M be a point on Γ, and X , Y be the interse tions of Γ, d with the ir le Γ′ of diameter AM . Prove that the line XY passes through a xed point as M moves about Γ. 3510
46 3511. Proposed by Pham Van Thuan, Hanoi University of S ien e, Hanoi, Vietnam. Let a, b, c, and d be nonnegative real numbers. Prove that
Y
a2 + b2 + c2
y li
≤
1 64
(a + b + c + d)8 .
. Proposed by Ovidiu Furdui, Campia Turzii, Cluj, Romania. Let α be a real number and let p ≥ 1. Find
3512
n Y np + (α − 1)kp−1
lim
n→∞
k=1
np − kp−1
.
. Proposed by Hassan A. ShahAli, Tehran, Iran. Let α and β be positive real numbers, and r be a positive rational number. Prove that there exist in nitely many integers m and n su h that 3513
⌊mα⌋ = r, ⌊nβ⌋
where ⌊x⌋ is the greatest integer not ex eeding x.
.................................................................
. Propose par Hassan A. ShahAli, Teh eran, Iran. Soit N l'ensemble des nombres entiers positifs, E ⊆ N l'ensemble de
eux qui sont pairs, et O ⊆ N l'ensemble de eux qui sont impairs. On dit qu'un ensemble S ⊆ N est ferme si x+y ∈ S pour tous les x, y ∈ S distin ts, et non-ferme si x + y 6∈ S pour tous les x, y ∈ S distin ts. Montrer que si N est partage en A et B , ou A est ferme et non vide, et B est non-ferme et in ni, alors A = E et B = O.
3501
. Propose par Jose Luis Daz-Barrero, Universite Polyte hnique de Catalogne, Bar elone, Espagne. Trouver toutes les solutions reelles du systeme d'equations suivant
3502
x21 + x22 + x2n +
È
È
x22 + 21
=
x23 + 21 ···
= ···
x21 + 21
=
È È
x22 + 77 ,
È È
x23 + 77 , ···
x21 + 77 .
47 . Propose par Bru e Shawyer, Universite Memorial de Terre-Neuve, St. John's, NL. Etant donne un triangle et les points milieux de ses ot ^ es, onstruire les bisse tri es de ses trois angles ave la regle et trois utilisations du ompas. 3503
. Propose par Mariia Rozhkova, Kiev, l'Ukraine. Dans un triangle donne ABC , d'aire S et dont le rayon du er le ir ons rit est R, on pose Q = a cos2 A + b cos2 B + c cos2 C . Montrer que 3504
(a) (b)
S , l'egalit e ayant lieu si et seulement si ABC est equilat eral. R √ S 2 Q≤ si ABC est non obtus, l'egalit e ayant lieu si et seulement R
Q≥
ABC
est un triangle re tangle iso ele.
si
. Propose par Yakub N. Aliyev, Universite de Qafqaz, Khyrdalan, Azerbadjan. Les er les Γ1 et Γ2 ont un entre ommun O, et Γ1 est a l'interieur de Γ2 . Par le point A 6= O , situe a l'interieur de Γ1 , on tra e un rayon oupant respe tivement Γ1 et Γ2 aux points B et C . Soit E un point de la droite BC tel que DE soit perpendi ulaire a BC . Montrer que AB = EC si et seulement si OA est perpendi ulaire a BC . 3505
. Propose par Pedro Henrique O. Pantoja, UFRN, Bresil. 2 3 Montrer que Q(n) + Q n + Q n est un arre parfait pour une in nite d'entiers positifs n qui ne sont pas divisibles par 10, ou Q(n) denote la somme des hi res de n. 3506
. Propose par Pham Huu Du , Ballajura, Australie. Soit a, b et c trois nombres reels positifs. Montrer que
3507
Ê
a(b + c) a2
+ bc
Ê
+
b(c + a) b2
+ ca
Ê
+
c(a + b)
Ê
≤
2(a + b + c)
c2 + ab
1 1 1 + + a+b b+c c+a
.
. Propose par Pham Kim Hung, etudiant, Universite de Stanford, Palo Alto, CA, E-U. Soit a, b, c et d des nombres reels non negatifs tels que a+b+c+d = 4. Montrer que 3508
√ √ √ √ √ a bc + b cd + c da + d ab ≤ 2 1 + abcd .
48 . Propose par Pham Kim Hung, etudiant, Universite de Stanford, Palo Alto, CA, E-U. Soit a, b et c trois nombres reels non negatifs tels que a + b + c = 3. Pour tout nombre reel positif k, trouver la valeur maximale de 3509
a2 b + k
b2 c + k
c2 a + k
.
. Propose par Cosmin Pohoata , College National Tudor Vianu, Bu arest, Roumanie. Soit d une droite exterieure a un er le donne Γ de entre O. Soit A la proje tion orthogonale de O sur la droite d, M un point sur Γ, et X , Y les AM . Montrer que la interse tions de Γ et d ave le er le Γ′ de diametre droite XY passe par un point xe lorsque M par ourt Γ.
3510
. Propose par Pham Van Thuan, Universite de S ien e de Hano, Hano, Vietnam. Soit a, b, c et d quatre nombres reels non negatifs. Montrer que
3511
Y
a2 + b2 + c2
y lique
≤
1 64
(a + b + c + d)8 .
. Propose par Ovidiu Furdui, Campia Turzii, Cluj, Roumanie. Soit α un nombre reel et soit p ≥ 1. Trouver
3512
lim
n→∞
n Y np + (α − 1)kp−1 k=1
np − kp−1
.
. Propose par Hassan A. ShahAli, Tehran, Iran. positifs, et soit r un nombre rationnel Soit α et β deux nombres reel positif. Montre qu'il existe une in nite d'entiers positifs m et n tels que
3513
⌊mα⌋ = r, ⌊nβ⌋
le plus grand entier ne depassant pas x. ou ⌊x⌋ denote
49
SOLUTIONS No problem is ever permanently losed. The editor is always pleased to onsider for publi ation new solutions or new insights on past problems. 3401. [2009 : 42, 44℄ Proposed by Tigran Sloyan, Basi Gymnasium of SEUA, Yerevan, Armenia. Let ABCDE be a onvex pentagon su h that ∠BAC = ∠EAD and ∠BCA = ∠EDA, and let the lines CB and DE interse t in the point F . Prove that the midpoints of CD, BE , and AF are ollinear.
Solution by Peter Y. Woo, Biola University, La Mirada, CA, USA, modi ed by the editor. Convexity is not required here. We shall prove that the midpoints of CD, BE , and AF are ollinear when ABC and AED are oppositely similar triangles that share the vertex A (and F = CB∩DE ). Our argument requires two easy lemmas. If P QRS is a quadrilateral for whi h ∠P QR = ∠P SR and the midpoint M of P R lies between Q and S on QS , then P QRS is a parallelogram. Proof. Let us all S ′ the point of the line QM for whi h M is the midpoint of QS ′ , and show that S ′ = S . Be ause its diagonals bise t one another, P QRS ′ is ne essarily a parallelogram, when e, ∠P S ′ R = ∠P QR = ∠P SR. But there an only be one point on the ray from Q toward M that an be the vertex of this angle, when e S ′ = S and P QRS is a parallelogram. Lemma 1
When all the points P on BC are related by a similarity to all the points P ′ on B ′ C ′ (that is, B ′ C ′ : BC = B ′ P ′ : BP ), then the midpoints of P P ′ are ollinear. Proof. Let B ′′ , C ′′ , P ′′ be the midpoints of the segments BB ′ , CC ′, P P ′ . Translate B ′ , C ′ , P ′ to B , C1′ , P1′ and denote by C1′′ , P1′′ the midpoints of CC1′ , P P1′ . Be ause P P1′ uts the sides BC and BC1′ of triangle BCC1′ proportionally, it follows that CC1′ kP P1′ ; onsequently, the midpoints C1′′ and P1′′ are ollinear with the vertex B . Be ause C1′′ C ′′ is parallel to and half the length of C1′ C ′ , whi h is parallel and equal to BB ′ , it follows that BC1′′ C ′′ B ′′ is a parallelogram. Similarly for BP1′′ P ′′ B ′′ . Sin e B , C1′′ , P1′′ are ollinear, so are B ′′ , C ′′ , P ′′ . Lemma 2
Comment. Lemma 2 is a spe ial ase of a lassi al theorem : Given two dire tly similar gures in the plane, the points that divide the line segments joining orresponding points of the two gures in the same ratio form a gure that is dire tly similar to them. See, for example, F. G.-M., Exer i es de
50 Geom etrie| omprenant l'expose des methodes geom etriques et 2000 questions resolues, sixieme edition, J. De Gigord, Paris, 1920, Paragraph 1146d, pages 473-474, whose proof was used above. In the lemma, our given gures are lines, and the ratio is 1 : 1. Note that as an immediate onsequen e of the general theorem, one an ontinuously transform any gure into any dire tly similar gure in the plane in su h a way that the shape never hanges and orresponding points move along straight lines. We turn now to the given oppositely similar triangles ABC and AED. We assume that the midpoints of CD and BE are distin t; otherwise there is nothing to prove. The lines BC and ED play the roles of BC and B ′ C ′ of Lemma 2 | P will move along BC while P ′ moves along ED in su h a way that the triangles ABP and AEP are dire tly similar; in parti ular, ∠AP F = ∠AP ′ F for all positions of P . By Lemma 2, the midpoint of P P ′ moves along the line joining the midpoints of CD and BE . There will be a unique position of P on BC where P P ′ ontains the midpoint of AF . At this position AP F P ′ is a parallelogram by Lemma 1; there the midpoint of AF
oin ides with the midpoint of P P ′ , and therefore it lies on the line joining the midpoints of CD and BE . Also solved by MICHEL BATAILLE, Rouen, Fran e; FRANCISCO JAVIER GARC I A CAPITAN, IES Alvarez Cubero, Priego de Cordoba, Spain; OLIVER GEUPEL, Bruhl, NRW, Y, Big Rapids, MI, USA; ALBERT STADLER, Herrliberg, Germany; V ACLAV KONECN Switzerland; and the proposer. There was one in orre t submission. Most of the submitted solutions used oordinates. Geupel found the problem in the 2005 Mathlinks internet forum, www.mathlinks.ro/viewtopic.php?t=38041, where there is a ni e syntheti proof from someone who goes by the name of \Armo".
. [2009 : 42, 44℄ Proposed by Mihaly Ben ze, Brasov, Romania. Let D and E be the midpoints of the sides AB and AC in triangle ABC , respe tively. Prove that CD is perpendi ular to BE if and only if 3402
5BC 2 = AC 2 + AB 2 .
Solution by Dung Nguyen Manh, High S hool of HUS, Hanoi, Vietnam. Let G = BE ∩ CD, and a = BC , b = CA, c = AB , mb = BE , mc = CD . Using the Pythagorean Theorem, its onverse, and Stewart's theorem, we have I.
CD ⊥ BE
⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒
as desired.
⇐⇒
BG2 + CG2 = BC 2
2 mb 3
2
+
2 mc 3
2
4m2b + 4m2c = 9a2
= a2
2 c2 + a2 − b2 + 2 a2 + b2 − c2 = 9a2 b2 + c2 = 5a2 ,
51 Solution by Joe Howard, Portales, NM, USA. From Problem 5 of CRUX with MAYHEM [2003 : 375, 377℄, in quadrilateral BCED the diagonals CD and BE are perpendi ular if and only if BC 2 + DE 2 = BD 2 + CE 2 . Sin e D and E are midpoints of their respe tive sides, the perpendi ularity of the two lines is equivalent to II.
BC 2 +
1 BC 2
2
=
1 AB 2
2
+
1 AC 2
2
,
or 5BC 2 = AC 2 + AB 2 .
Also solved by GEORGE APOSTOLOPOULOS, Messolonghi, Gree e; SEFKET University of Sarajevo, Sarajevo, Bosnia and Herzegovina; MATTHEW BABBITT, ARSLANAGIC, home-s hooled student, Fort Edward, NY, USA; DIONNE BAILEY, ELSIE CAMPBELL, and CHARLES R. DIMINNIE, Angelo State University, San Angelo, TX, USA; ROY BARBARA, Lebanese University, Fanar, Lebanon; RICARDO BARROSO CAMPOS, University of Seville, Seville, Spain; MICHEL BATAILLE, Rouen, Fran e; CAO MINH QUANG, Nguyen Binh Khiem High S hool, Vinh Long, Vietnam; CHIP CURTIS, Missouri Southern State University, Joplin, MO, USA; OLIVER GEUPEL, Bruhl, NRW, Germany; RICHARD I. HESS, Ran ho Palos Verdes, CA, USA; JOHN G. HEUVER, Grande Prairie, AB; WALTHER JANOUS, Ursulinengymnasium, Y, Big Rapids, MI, USA; KEE-WAI LAU, Hong Kong, Innsbru k, Austria; V ACLAV KONECN China; MADHAV R. MODAK, formerly of Sir Parashurambhau College, Pune, India; CRISTINEL MORTICI, Valahia University of T^argoviste, Romania (two solutions); JOSE H. NIETO, Universidad del Zulia, Mara aibo, Venezuela; JUAN-BOSCO ROMERO MARQUEZ, Universidad de Valladolid, Valladolid, Spain; JOEL SCHLOSBERG, Bayside, NY, USA; BOB SERKEY, Leonia, NJ, USA; ALBERT STADLER, Herrliberg, Switzerland; VASILE TEODOROVICI, Toronto, ON; PETER Y. WOO, Biola University, La Mirada, CA, USA; KONSTANTINE ZELATOR, University of Pittsburgh, Pittsburgh, PA, USA; TITU ZVONARU, Comane sti, Romania; and the proposer. Most of the submitted solutions were similar to one of the featured solutions.
. [2009 : 42, 44℄ Proposed by D.J. Smeenk, Zaltbommel, the Netherlands. The ir les Γ1 and Γ2 interse t at P and Q. A line ℓ through P interse ts Γ1 and Γ2 for the se ond time at A and B , respe tively. The tangents to Γ1 and Γ2 at A and B interse t at C . If O is the ir um entre of △ABC determine the lo us of O when ℓ rotates about P . 3403
Solution by Mi hel Bataille, Rouen, Fran e. Let O1 and O2 be the entres of Γ1 and Γ2 , respe tively, and Γ be the ir um ir le of the triangle QO1 O2 . We show that the required lo us is Γ − {Q, O1 , O2 }. (See the gure on the next page.) Let σ denote the spiral similarity with entre Q transforming O1 into O2 . Then, σ(Γ1 ) = Γ2 and it follows that σ(A) = B (a known property). We ex lude the ases when △ABC is degenerate, that is, when ℓ either is the line P Q (in whi h ase A = B = Q) or is tangent to Γ1 or Γ2 at P (in whi h ase B = C or A = C ). Sin e the lines CA and CB are perpendi ular to O1 A and O2 B , we also have σ(CA) = CB .
52 Thus, we have ∠(CA, CB) θ
=
= ∠(QA, QB) (mod π), θ is the angle of σ , so
where that Q is on the ir um ir le of △ABC . Note that we ertainly have O 6= O1 , O2 (if O = O1 , say, then O1 B = O1 A, hen e B = P or Q, whi h has been ex luded) and the lines OO1 and OO2 are the perpendi ular bise tors of QA and QB , respe tively. Thus, ∠(OO1 , OO2 ) = ∠(QA, QB) = ∠(QO1 , QO2 ) (mod π)
.......................................................... ............. .......... ......... ........ ........ ....... ....... ...... . . . . . ..... .... . ..... 2 . . .. .... . . . .... .. . . . . . . . . . . . . . . . . . . . .... ........ .. .. .. . ... .. .. .. .. .. .. .. .. . . . ... . . . . . . . . . . . . . .... .... ........... ............................. . . . ... . . . . . . . . .... .... ......... ............ ... . 1........... . . . . . . . ... ... ......... ... . ............ . . . . . . . . . . . . ... ..... .. . .. ........ .... .. . . . . . . .. .......... . .. . . .. . . . . .. . . . . . . ... ... ...... .. .. .... .. . . . ... . . . . . . ... . .. ..... . . . .. ... .. ..... . . ... .. ........ .... .. ..... ... .. . . . . . . .... . ..... . . .. . . ... ..... . ... .. ...... ....... .... . . ..... .... . . .. ..... 2 ... . . ... . ... . ..... .. .. . . . ... .. .... . .. . . . . . . . . . . . ...... .. .... . . . ..... ... . .. . . . . . . . . . . . . . . . 1 . .. ..... ... .... .. . ... . ......... ...... ... ....... .. ...... ...... .. ..... ... ... ........ . .. .. ... .. ..... .. .... ...... ...... ..... .. ... ..... .. .. ..... ... .... ...... ...... .......... ......... ..... .. . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . ..... .. .......... ................................................... .. .. . .. ............ .. ..... .. .... .. .......................... .................................................... .. ..... .. ... .... ..... ......... ........................ ... .. ..... .. .............. ........................ ..... .... . .. . . . . . . ......................... ..... .... ........................ .......... .............. .. ..... .... ................................. ..... . ..... .... ..... . ..... ....... ..... ....... . ........ ........ . ..... .. ......... ..... ................. .. . . . . . . . . . ............ ..... . .......................................................................... . ..... . ..... .. ... .. ..... ... .... .. ..... ..... ... ..... ..... ... ... ..... ..... ... . . ... . . ..... . . . .... ..... ..... ... ..... .... .... .... ..... ..... .... ..... ..... .... .... ..... ......... .. .... .. .. .. .. .. .. .. .. . .. ..................... .. .. .. . .. .. .... ..... .. .... ..... .....
Γ
Q
Γ
Γ
qO
q
O
O
A
q
P
B
C and nally, O, Q, O1 , O2 are
on y li . Conversely, let O 6= Q, O1 , O2 be any point on the ir le (QO1 O2 ). Let the perpendi ular to OO1 through Q meet Γ1 again at A and the perpendi ular to OO2 through Q meet Γ2 again at B . Then, ∠(QA, QB) = ∠(OO1 , OO2 ) (mod π), hen e σ(A) = B (sin e σ(Γ1 ) = Γ2 ) and it follows that A, P , B are ollinear on a line ℓ. The ir um entre of △QAB is O (be ause OO1 and OO2 are the perpendi ular bise tors of QA and QB ; note that O1 A = O1 Q and O2 B = O2 Q). Moreover σ(CA) = CB (sin e σ(AO1 ) = BO2 and CA ⊥ AO1 , CB ⊥ BO2 ), hen e ∠(QA, QB) = ∠(CA, CB) and the ir le (QAB) passes through C . Thus, O is the ir um entre of △ABC .
Also solved by RICARDO BARROSO CAMPOS, University of Seville, Seville, Spain; OLIVER GEUPEL, Bruhl, NRW, Germany; JOHN G. HEUVER, Grande Prairie, AB; PETER Y. WOO, Biola University, La Mirada, CA, USA; and the proposer. Geupel noted that problem G4 on the IMO 2002 short list essentially generalizes the given problem (he gave the referen e D. Djuki et al., The IMO Compendium, Springer 2006, pages 319 and 692 for the problem and solution, respe tively).
. [2009 : 42, 45℄ Proposed by Mi hel Bataille, Rouen, Fran e. Let Q be a y li quadrilateral. The perpendi ulars to ea h diagonal through its endpoints form a parallelogram, P . Chara terize the entre of P and show that opposite sides of Q interse t on a diagonal of P . 3404
Solution by Oliver Geupel, Bruhl, NRW, Germany. Let A, B , C , and D be the verti es of Q in y li order. First, we prove that the entre of P is the ir um entre of Q. The entre of P is the point of interse tion of the perpendi ular bise tors of the line segments AC and BD. But AC and BD are hords of the ir um ir le of Q. Hen e, their perpendi ular bise tors interse t at the entre of this ir le.
53 It remains to prove that opposite sides of Q interse t on a diagonal of P . Let E , F , G, and H be the verti es of P su h that A, B , C , and D lie on HE , EF , F G, and GH , respe tively. We show that the lines AD, BC , and EG are on urrent. (The proof that the lines AB , CD , and F H are on urrent is similar.) Sin e ∠AHD = ∠BF C and ∠DAH = 90◦ − ∠CAD = 90◦ − ∠CBD = ∠CBF
,
we on lude that triangles ADH and BCF are similar. Hen e, DH
=
AH
CF BF
.
Similarly, AE BE = DG CG
.
Let the lines AD and BC meet the line EG at points I and J , respe tively. Using Menelaus' thereom for △EGH and △EGF , we obtain IE IG
=
DH · AE
DG · AH
=
CF · BE
CG · BF
=
JE JG
.
Consequently, I = J , whi h shows that the lines AD, BC , and EG are
on urrent. If we assume that parallel lines interse t at in nity, then the result remains true when one or both pairs of opposite sides of Q are parallel (Q is then an isos eles trapezium or re tangle, respe tively). If opposite sides of Q are parallel, then they are also parallel to a diagonal of P , in whi h ase they both interse t the diagonal at in nity. Also solved by WALTHER JANOUS, Ursulinengymnasium, Innsbru k, Austria; PETER Y. WOO, Biola University, La Mirada, CA, USA; and the proposer.
. [2009 :42, 45℄ Proposed by Mi hel Bataille, Rouen, Fran e. Find the minimum value of
3405
| cos α| + | cos β| + | cos γ| + | cos(α − β)| + | cos(β − γ)| + | cos(γ − α)| ,
where α, β , and γ are real numbers. Solution by Oliver Geupel, Bruhl, NRW, Germany. We prove that the minimum value is 2. Suppose that x, y, and z are real numbers su h that x + y + z = 0. Then using the triangle inequality as
54 well as the trigonometri addition formulas, we obtain | cos x| + | cos y| + | cos z| ≥ | cos x| + | cos y sin z + sin y cos z| = | cos x| + | sin(y + z)| ≥ | cos x cos(y + z) − sin x sin(y + z)| = | cos(x + y + z)| = 1
Choosing su
essively (−α, β, α − β), (−β, γ, β − γ), (−γ, α, γ − α), and (α − β, β − γ, γ − α) for (x, y, z), yields | cos α| + | cos β| + | cos(α − β)| ≥ 1 , | cos β| + | cos γ| + | cos(β − γ)| ≥ 1 , | cos γ| + | cos α| + | cos(γ − α)| ≥ 1 , | cos(α − β)| + | cos(β − γ)| + | cos(γ − α)| ≥ 1 . By adding up, we on lude that | cos α| + | cos β| + | cos γ| + | cos(α − β)| + | cos(β − γ)| + | cos(γ − α)| ≥ 2 . The minimum is a hieved when (α, β, γ) =
0,
π 3π , 2 2
, among other values.
Also solved by ALBERT STADLER, Herrliberg, Switzerland; PETER Y. WOO, Biola University, La Mirada, CA, USA; and the proposer
. [2009 : 43, 45℄ Proposed by Jose Luis Daz-Barrero and Miquel Grau-San hez, Universitat Polite ni a de Catalunya, Bar elona, Spain. Find " # n 1 Y k . lim ln n 2+ 2 n→∞
3406
2
n
k=1
Independent solutions by Mi hel Bataille, Rouen, Fran e and Alberto Arenas Gomez, student, University of La Rioja, Logrono, ~ Spain. Let An
n 1 Q k = ln n 2+ 2 2 k=1 n
An = ln
n Y k=1
k 1+ 2n2
Using the known inequalities and setting x =
k , 2n2
. Then we have !
=
n X
ln 1 +
k=1
x ≤ ln(1 + x) ≤ x 1+x
k 2n2
.
valid for positive x,
we obtain k
k k 2n2 = ≤ ln 1 + 2 k 2n + k 2n2 1+ 2 2n
≤
k 2n2
.
(1)
55 For ea h k = 1, 2, . . . , n we have 1+
and (1) yields 2n 2n + 1
k 2n2
k 2n2
≤ 1+
n 2n2
=
≤ ln 1 +
Summing over k and using the identity
n P
2n + 1
k 2n2 k=
k=1
2n
≤
k 2n2
n(n + 1) 2
1 n+1 n+1 ≤ An ≤ · 2(2n + 1) 4 n
.
yields
.
1 Finally, by the Squeeze Theorem, we have that n→∞ lim An = . 4
Also solved by ARKADY ALT, San Jose, CA, USA; ROY BARBARA, Lebanese University, Fanar, Lebanon; CAO MINH QUANG, Nguyen Binh Khiem High S hool, Vinh Long, Vietnam; CHIP CURTIS, Missouri Southern State University, Joplin, MO, USA; OLIVER GEUPEL, Bruhl, NRW, Germany; RICHARD I. HESS, Ran ho Palos Verdes, CA, USA; JOE HOWARD, Portales, NM, USA; WALTHER JANOUS, Ursulinengymnasium, Innsbru k, Austria; KEE-WAI LAU, Hong Kong, China; DAVID E. MANES, SUNY at Oneonta, Oneonta, NY, USA; MADHAV R. MODAK, formerly of Sir Parashurambhau College, Pune, India; JOSE H. NIETO, Universidad del Zulia, Mara aibo, Venezuela; JOEL SCHLOSBERG, Bayside, NY, USA; ALBERT STADLER, Herrliberg, Switzerland; and the proposer. There was one in omplete solution submitted. Stan Wagon, Ma alester College, St. Paul, MN, USA, submitted a omputer generated solution.
3407. [2009 : 43, 45℄ Proposed by Roy Barbara, Lebanese University, Fanar, Lebanon. Let S be a set of positive integers ontaining the integer 2007 and su h that (a) If x, y ∈ S and x 6= y, then |x − y| ∈ S , and
(b) If x ∈ S , then x3 − 1007x + 3007 ∈ S . Prove that S is the set of all positive integers.
Solution by Ri hard I. Hess, Ran ho Palos Verdes, CA, USA. Sin e 2007 ∈ S , we have that 20073 − 1007 · 2007 + 3007 ∈ S . By subtra ting 2007 enough times, we nd that 1000 ∈ S . Thus, by property (a), we also nd that 1007 = 2007 − 1000 ∈ S and that 7 = 1007 − 1000 ∈ S . Sin e 6 = 1000 − 7 · 142, we also obtain 6 ∈ S . Thus 1 = 7 − 6 ∈ S . We de ne x1 = 2007 and xi+1 = x3i − 1007xi + 3007. Then lim xi = ∞ .
i→∞
56 [Ed.: Sin e x1 = 2007, it is obvious that xi+1 > xi > 2007, hen e xi is an in reasing sequen e of integers.℄ Now let n be any positive integer. We know that there exists an i su h that xi ∈ S and xi ≥ n. Then, by subtra ting 1 from xi enough times, we nd n ∈ S .
Also solved by GEORGE APOSTOLOPOULOS, Messolonghi, Gree e; SEFKET University of Sarajevo, Sarajevo, Bosnia and Herzegovina; MATTHEW BABBITT, ARSLANAGIC, home-s hooled student, Fort Edward, NY, USA; MICHEL BATAILLE, Rouen, Fran e; CHIP CURTIS, Missouri Southern State University, Joplin, MO, USA; OLIVER GEUPEL, Bruhl, NRW, Germany; WALTHER JANOUS, Ursulinengymnasium, Innsbru k, Austria; KEE-WAI LAU, Hong Kong, China; KATHLEEN E. LEWIS, SUNY Oswego, Oswego, NY, USA; DAVID E. MANES, SUNY at Oneonta, Oneonta, NY, USA; MADHAV R. MODAK, formerly of Sir Parashurambhau College, Pune, India; JOSE H. NIETO, Universidad del Zulia, Mara aibo, Venezuela; JOEL SCHLOSBERG, Bayside, NY, USA; DIGBY SMITH, Mount Royal College, Calgary, AB; ALBERT STADLER, Herrliberg, Switzerland; VASILE TEODOROVICI, Toronto, ON; PETER Y. WOO, Biola University, La Mirada, CA, USA; and the proposer. Hess, Smith, and the proposer pointed out that part (b) ontained a minor error, sin e for x = 4, 5, . . . , 30 the ubi x3 − 1007x + 3007 takes negative integer values. This an be remedied by rephrasing (b) as: If x ∈ S, then x3 − 1007x + 3007 ∈ S.
. [2009 : 43, 45℄ Proposed by Slavko Simi , Mathemati al Institute SANU, Belgrade, Serbia. Let {ci }∞ i=1 be a sequen e of distin t positive integers, and let |q| < 1. Prove that the inequality 3408
∞ X
ci q ci
i=1
1+
∞ X
q ci
≤
q 1−q
i=1
holds for all su h sequen es {ci }∞ i=1 if and only if q ∈
0,
1 2
.
Solution by Mi hel Bataille, Rouen, Fran e, modi ed by the editor. First, suppose that q ∈ 0, 12 and let {ci }∞ i=1 be a sequen e of distin t positive integers. The inequality is equivalent to (1 − q)
∞ X i=1
ci q ci ≤ q +
∞ X
q ci +1 .
(1)
i=1
Both sides are 0 if q = 0, so we suppose that 0 < q ≤ 21 . Hen eforth, we will also suppose that c1 < c2 < c3 < · · · , sin e the series involved are absolutely onvergentPand therefore may be rearranged. Rewriting the left c c +1 side of (1) as c1 qc + ∞ c q − c q , we see it suÆ es to prove i+1 i i=1 1
(a)
c1 q c1 ≤ q
i+1
and
(b)
i
ci+1 q ci+1 −ci q ci +1 ≤ q ci +1
(i = 1, 2, . . .) .
57 Now, (a) is equivalent to qc −1 ≤ c1 , whi h holds sin e qc −1 ≤ 2c 1−1 and 1 2n−1 ≥ n for ea h positive integer n. As for inequality (b), we rewrite it as 1
1
1
q ci+1 −ci −1 ≤
ci + 1 ci+1
.
We have ci+1 − ci − 1 ≥ 0, so it suÆ es to prove that 1 2ci+1 −ci −1
≤
ci+1 2ci+1
≤
ci + 1
, or
ci+1 ci + 1 2ci +1
.
The latter holds be ause ci+1 ≥ ci + 1 ≥ 2 > ln12 , and f (x) = 2xx is h de reasing on the interval ln12 , ∞ . Next, suppose −1 < q < 0. Let ci = 2i, for ea h i = 1, 2, . . .. Observe that the left-hand side of the original inequality is positive, while the righthand side of the original inequality is negative, a ontradi tion. Thus, the inequality does not hold in this ase for all admissible sequen es {ci }∞ i=1 . 1 Lastly, suppose 2 < q < 1. Let ci = i + 1 for ea h i = 1, 2, . . .. Then, c c1 q = 2q 2 > q . Observing that ci+1 = ci + 1 for ea h i, we dedu e that 1
c1 q c1 +
∞ X i=1
ci+1 q ci+1 > q +
∞ X
(ci + 1)q ci +1 ,
i=1
and so (1) does not hold. This ompletes the proof. Also solved by CHIP CURTIS, Missouri Southern State University, Joplin, MO, USA; KEEWAI LAU, Hong Kong, China; MADHAV R. MODAK, formerly of Sir Parashurambhau College, Pune, India; ALBERT STADLER, Herrliberg, Switzerland; and the proposer. There were two in omplete solutions submitted.
. [2009 : 43, 45℄ Proposed by Jose Luis Daz-Barrero, Universitat Polite ni a de Catalunya, Bar elona, Spain. Let a, b, c, and d be positive real numbers. Prove that 3409
ab + bc + ca ab + bd + da ac + cd + da bc + cd + db + 3 + 3 + 3 a 3 + b3 + c3 a + b3 + d3 a + c3 + d3 b + c3 + d3 § 2 ª 2 2 2 2 2 2 a +b c +d a +c b + d2 a 2 + d2 b2 + c2 ≤ min + , + , + . (ab)3/2 (cd)3/2 (ac)3/2 (bd)3/2 (ad)3/2 (bc)3/2
58 Solution by Chip Curtis, Missouri Southern State University, Joplin, MO, USA. By the AM{GM Inequality, a3 + b3 + c3 ≥ 3abc, so that ab + bc + ca
≤
a3 + b3 + c3
1
3
1 a
+
1 b
+
1
c
,
with analogous inequalities holding for the other three terms on the left side of the laimed inequality. Hen e, ab + bd + da ac + cd + da bc + cd + db ab + bc + ca + 3 + 3 + 3 3 3 3 3 3 3 3 a +b +c a +b +d a +c +d b + c3 + d3
≤
1 a
+
1 b
+
1 c
+
1
d
.
(1)
The AM{GM and AM{QM inequalities imply that (ab)1/2 É
a+b ≤ 2 1/2
(ab)
É
≤
a 2 + b2 2
and
a 2 + b2 , respe tively. 2 2
2
(a + b) ≤ a + b
Multiplying a ross these inequalities yields . Hen e,
1 1 a+b a2 + b2 + = ≤ a b ab (ab)3/2
.
Analogous inequalities again hold for the other pairs of variables, thus
1 1 1 1 + + + a b c d
≤
min
a2 + b2 (ab)3/2
+
c2 + d2 a2 + c2 b2 + d2 a2 + d2 b2 + c2 , + , + 3/2 3/2 3/2 3/2 (cd) (ac) (bd) (ad) (bc)3/2
.
The desired inequality now follows from the above inequality and (1). Also solved by MICHEL BATAILLE, Rouen, Fran e; OLIVER GEUPEL, Bruhl, NRW, Germany; and the proposer. One in orre t solution was submitted. A omputer generated solution totaling 228 pages was submitted, whi h due to its length and omplexity ould not be veri ed in the available time.
. [2009 : 43, 46℄ Proposed by Joe Howard, Portales, NM, USA. Let a, b, and c be the sides of triangle ABC , let R be its ir umradius, and let F be its area. Prove that 3410
X bc sin2 A/2
y li
b+c
≥
F 2R
.
59 Similar solutions by George Apostolopoulos, Messolonghi, Gree e; Mi hel Bataille, Rouen, Fran e; Kee-Wai Lau, Hong Kong, China; Albert Stadler, Herrliberg, Switzerland; and Peter Y. Woo, Biola University, La Mirada, CA, USA. Let r and s denote the inradius and semiperimeter of ∆ABC , respe 2 c2 − a 2 A tively. By the Law of Cosines, b +2bc = cos A = 2 cos2 − 1, hen e 2 A A = s(s − a) tan2 2 2
bc sin2
Sin e F
= rs,
.
it follows that the proposed inequality is equivalent to X b+c−a
b+c
y li
tan2
A r ≥ 2 R
.
Using the Law of Sines, we have b+c−a b+c
B
C
A
=
4 sin sin cos sin B + sin C − sin A 2 2 2 = A B−C sin B + sin C 2 cos cos
≥
B C 2 sin sin 2 2
2
2
.
Now, using the last inequality and the well-known and easy to prove identity C A B r = 4R sin sin sin , we have 2 2 2
b+c−a A tan2 ≥ b+c 2
B C A 2 sin sin sin 2 2 2
A 2 · A 2 cos 2
sin
A 2 = · 2R cos2 A 2
sin
r
.
Thus, it suÆ es to prove that A 2 ≥ 2. A 2 cos 2
X sin
y li
sin x To this end, onsider f (x) = cos for x ∈ 0, π2 . An easy al ulation 2x yields f ′′ (x) = (cos x)−4 (sin x) 5 + sin2 x >0, so that f is a onvex fun tion on the interval 0, π2 . From Jensen's inequality,
f
A 2
+f
B 2
that is,
+f
≥ 3f
A/2 + B/2 + C/2 3
π A sin 2 ≥ 3· 6 = 2 , π A 2 2 cos cos 6 2
X sin
y li
C 2
,
60 whi h ompletes the proof. Also solved by ARKADY ALT, San Jose, CA, USA; CAO MINH QUANG, Nguyen Binh Khiem High S hool, Vinh Long, Vietnam; CHIP CURTIS, Missouri Southern State University, Joplin, MO, USA; FRANCISCO JAVIER GARC I A CAPITAN, IES Alvarez Cubero, Priego de Cordoba, Spain; OLIVER GEUPEL, Bruhl, NRW, Germany; WALTHER JANOUS, Ursulinengymnasium, Innsbru k, Austria; THANOS MAGKOS, 3rd High S hool of Kozani, Kozani, Gree e; DUNG NGUYEN MANH, High S hool of HUS, Hanoi, Vietnam; TITU ZVONARU, Comane sti, Romania; and the proposer.
. [2009 :44, 46℄ Proposed by Mihaly Ben ze, Brasov, Romania. Let a, b, and c be positive real numbers su h that
3411
2 32 3 a + b3 + c3 . 33 quadrati s ax2 + bx + c, bx2 + cx + a,
a6 + b6 + c6 <
Prove that at least one of the no real roots.
cx2 + ax + b has
or
Solution by Chip Curtis, Missouri Southern State University, Joplin, MO, USA, modi ed by the editor. We prove that in fa t the on lusion holds for all positive real numbers a, b, and c. Suppose that ea h quadrati has at least one real root. Then we have a2 ≥ 4bc, b2 ≥ 4ac, and c2 ≥ 4ab. Multiplying these inequalities we obtain a2 b2 c2 ≥ 64a2 b2 c2 , whi h is a ontradi tion.
Also solved by MIGUEL AMENGUAL COVAS, Cala Figuera, Mallor a, Spain; GEORGE University of Sarajevo, APOSTOLOPOULOS, Messolonghi, Gree e; SEFKET ARSLANAGIC, Sarajevo, Bosnia and Herzegovina; ROY BARBARA, Lebanese University, Fanar, Lebanon; MICHEL BATAILLE, Rouen, Fran e; OLIVER GEUPEL, Bruhl, NRW, Germany; WALTHER JANOUS, Ursulinengymnasium, Innsbru k, Austria; KEE-WAI LAU, Hong Kong, China; D.J. SMEENK, Zaltbommel, the Netherlands; ALBERT STADLER, Herrliberg, Switzerland; PETER Y. WOO, Biola University, La Mirada, CA, USA; KONSTANTINE ZELATOR, University of Pittsburgh, Pittsburgh, PA, USA; TITU ZVONARU, Comane sti, Romania; and the proposer. 3412. [2009 :44, 46℄ Proposed by Cao Minh Quang, Nguyen Binh Khiem High S hool, Vinh Long, Vietnam. Let a, b, and c be positive real numbers su h that abc = 1. Prove that
X
y li
1 ≤ 1. √ 3 a + 2b3 + 6
Solution by Dung Nguyen Manh, High S hool of HUS, Hanoi, Vietnam. Let x, y, z be positive real numbers su h that xy = a, yz = b, xz = c. By using the AM{GM Inequality we obtain a3 + 2b3 + 6 = ≥
a3 + b3 + 1 + b3 + 1 + 1 + 3
3(ab + b + 1) = 3
x
z
+
y 3(x + y + z) +1 = z z
.
61 Hen e, √ 3 1 3 ≤ a + 2b + 6 of this inequality, we obtain X
y li
p
√
z . 3(x + y + z)
Adding up the y li variants
√ √ √ x+ y+ z
1
≤ È √ a3 + 2b3 + 6 3(x + y + z)
.
(1)
On the other hand, by the Cau hy{S hwarz Inequality we have È √ √ √ x+ y+ z ≤ 3(x + y + z) .
(2)
The result now follows from (2) and (1). Equality holds if and only if a = b = c = 1.
Also solved by GEORGE APOSTOLOPOULOS, Messolonghi, Gree e; SEFKET University of Sarajevo, Sarajevo, Bosnia and Herzegovina; CHIP CURTIS, ARSLANAGIC, Missouri Southern State University, Joplin, MO, USA; OLIVER GEUPEL, Bruhl, NRW, Germany; WALTHER JANOUS, Ursulinengymnasium, Innsbru k, Austria; KEE-WAI LAU, Hong Kong, China; DAVID E. MANES, SUNY at Oneonta, Oneonta, NY, USA; ALBERT STADLER, Herrliberg, Switzerland; PETER Y. WOO, Biola University, La Mirada, CA, USA; and the proposer.
. [2009 : 44, 46℄ Proposed by Vo Quo Ba Can, Can Tho University of Medi ine and Pharma y, Can Tho, Vietnam. Let a, b, c, and d be real numbers in the interval [1, 2]. Prove that 3413
a+b c+d
+
c+d a+b
−
a+c b+d
≤
3 2
.
Solution by Oliver Geupel, Bruhl, NRW, Germany, modi ed by the editor. Sin e the inequality is invariant under the permutation
a b c c d a
d b
,
then without loss of generality we an also assume that b ≤ d. +b c+d a+c Let f (a, b, c, d) = ac + + − . We need to prove that d a+b b+d 3 2
for all a, b, c, d in the interval [1, 2] with will prove more generally that f (a, b, c, d) ≤ 23 in the region
f (a, b, c, d) ≤
D = {(a, b, c, d) ∈ R4 : 1 ≤ b ≤ d ≤ 2
and
b ≤ d.
We
d ≤ a, c ≤ 2b} . 2
Sin e the fun tion f is ontinuous and the region D is ompa t, f attains a maximum in D.
62 For xed b and d, the fun tion f has positive partial derivatives ∂ 2f
=
∂a2
2(c + d) (a + b)3
;
∂2f ∂c2
=
2(a + b) (c + d)3
,
and therefore it is onvex f attains itsomaximum in D at n for a,c > 0. Thus, d d d d , 2 , 2b , 2b, 2 , (2b, 2b) . a point with (a, c) ∈ , 2 2 By multiplying ea h side of the inequality by 8(c + d)(a + b)(b + d), we see that proving the inequality amounts to proving that g(a, c) =
n
for (a, c) ∈ We have
8b3 + 8d3 + 8a2 b − 8a2 c + 16ab2 − 8ac2 − 12ad2 − 12b2 c − 4b2 d − 4bd2 + 8c2 d + 16cd2 − 20abc − 4abd − 20acd − 4bcd ≤ 0
d d , 2 2
,
o d d , (2b, 2b) , 2b , 2b, 2 2
and 1 ≤ b ≤ d ≤ 2.
d d , = 8b3 − 2b2 d − 11bd2 + 5d3 = (b − d)(2b − d)(4b + 5d) ≤ 0 , 2 2 d g , 2b = −16b3 − 8b2 d + 4bd2 + 2d3 = 2(d − 2b)(2b + d)2 ≤ 0 , 2 d g 2b, = 72b3 − 54b2 d − 54bd2 + 18d3 2 = 18 (d2 (d − 2b) + b(b − d)(4b + d) ≤ 0 , g
g(2b, 2b) = −160b3 − 68b2 d + 4bd2 + 8d3
= 8 d3 − (2b)3 + 4bd(d − 2b) − 60b2 d − 96b3 ≤ 0 ,
and the inequality follows. Also solved by GEORGE APOSTOLOPOULOS, Messolonghi, Gree e, ALBERT STADLER, Herrliberg, Switzerland, and the proposer. There were three in omplete solutions submitted.
3414. [2009 : 108, 111℄ Proposed by D.J. Smeenk, Zaltbommel, the Netherlands. As triangle ABC varies, its ir um ir le γ1 (O, R) and its in ir le γ2 (I, r) are xed, where O and I are the respe tive entres and R and r are the respe tive radii. Find the lo us of the ortho entre H of triangle ABC .
Solution by Mi hel Bataille, Rouen, Fran e. We show that the lo us of H is the ir le γ3 (J, R − 2r), where J is the re e tion of O in the point I ; note that O, I and, onsequently, J are xed while the triangle ABC varies.
63 (a) Let N be the entre of the nine-point (or Euler) ir le, and F be the Feuerba h point (that is, the point where the nine-point ir le is tangent to and the in ir le γ2 ). Sin e the radii N F and IF have respe tive lengths R 2
must lie on the ir le with entre I and radius R − r . Sin e N is the 2 midpoint of OH while I is the midpoint of OJ , we must have J H parallel to and twi e the length of IN; in other words, H must lie on the ir le with
entre J and radius 2 R − r = R − 2r . 2 (b) Conversely, let H be an arbitrary point of the ir le γ3 (J, R − 2r). We shall use omplex numbers to show that there exist points A, B , C on the
ir um ir le γ1 (O, R) for whi h the triangle ABC has in ir le γ2 (I, r) and ortho entre H . Without loss of generality we assume that γ1 is the unit ir le (that is, R = 1 and O is represented by the omplex number 0); moreover, we will take I on the real axis. Be ause Euler's formula gives OI 2 = R2 − 2Rr, √ I will be represented by the real number u := 1 − 2r . Be ause we assume that H is on γ3 , it is represented by the omplex number h := 2u + u2 eiθ for some real number θ. Now, let z1 , z2 , z3 denote the omplex roots of the polynomial r, N
P (z) = z 3 − 2u + u2 eiθ z 2 + (u2 + 2ueiθ )z − eiθ .
Sin e P (z) = z(z − u)2 − eiθ (1 − uz)2 , we have for j
z−u is less 1 − uz iθ e = 1 ; |z| > 1, while z |z|
Note that
zj − u 1 − uzj
2
=
eiθ zj
= 1, 2, 3,
.
than or greater than
(1)
(2) 1
a
ording as
|z| < 1
or
onsequently, equation (2) implies that |zj | = 1. Thus, the points A, B , C that orrespond respe tively to z1 , z2 , z3 are on the ir le γ1 = γ1 (O, 1). In addition, sin e z1 + z2 + z3 = h (from (1)), − − → −→ −→ −→ we have OH = OA + OB + OC . We re ognize this last equation to be the ve tor formulation of the theorem that the segment AH is parallel to and twi e as long as the segment joining O to the midpoint of BC , whi h implies that H is the ortho entre of △ABC . It remains to prove that I is its in entre. We denote by L the se ond point where the line AI interse ts γ1 , and represent it by the omplex number ℓ; the omplex equation of AI is then, z + z1 ℓ¯ z = z1 + ℓ. Be ause u (representing the point I ) must satisfy this equation, we have u − z1 ℓ = , iθ
1 − uz1
so that from (2), ℓ2 = ez = z1 zz2 z3 = z2 z3 . Thus, 2 arg ℓ = arg z2 + arg z3 , 1 1 whi h tells us that the perpendi ular bise tor of BC meets γ1 in L; it follows that AI ≡ AL is one of the bise tors of ∠BAC . Similarly, BI and CI
64 are bise tors of ∠CBA and ∠ACB , respe tively. Sin e I is interior to the
ir um ir le γ1 of △ABC , I must be the in entre of △ABC . Comment. I ame a ross the problem in the referen es listed below; however, the onverse, treated above in part (b), was either absent from these sour es or very in omplete. Referen es [1℄ William Gallatly,
The Modern Geometry of the Triangle,
2nd ed. Hodgson
(1913). [2℄ Jos.E. Hofmann, Zur elementaren Dreie ksgeometrie in der komplexen Ebene.
L'Enseignement mathematique
4
(1958) pp. 197-199.
available at [3℄ T. Lales o,
L'Ouvert,
This arti le has been
98 (2000) pp. 1-22; http://irem.u-strasbg.fr/php/articles/98_Nivelle.pdf.
translated into Fren h by Lisiane Nivelle,
La geometrie du triangle.
it is
J. Gabay (2003), p. 21.
Also solved by OLIVER GEUPEL, Bruhl, NRW, Germany; JOHN G. HEUVER, Grande Prairie, AB; MADHAV R. MODAK, formerly of Sir Parashurambhau College, Pune, India; PETER Y. WOO, Biola University, La Mirada, CA, USA; TITU ZVONARU, Comane sti, Romania; and the proposer. Observe that as a onsequen e of the argument in part (b), ea h point H on its ir le γ3 determines three positions for the vertex A: at z1 , z2 , and z3 ; in other words, as the vertex A of the moving triangle travels on e around γ1 , H will travel three times around γ3 . Woo observed that be ause the entroid G of △ABC is on the Euler line two-thirds of the way from O to N , the argument of part (a) also shows that the lo us of G is a ir le whose radius is − r ; its entre is the point two-thirds of the two-thirds that of the lo us of N , namely 23 R 2 way from O to I . Almost all solvers showed that the lo us of ortho entre H was a subset of the ir le γ3 (J, R − 2r) using an argument similar to part (a) of our featured solution. Geupel, however, used omplex numbers; he provided the only solution other than Bataille's to address satisfa torily the onverse problem of showing the lo us to be all of γ3 . It would be ni e if somebody
ould treat this onverse using elementary geometry in the spirit of part (a). The proposer found the problem in the De ember 1912 issue of the Journal de mathematiques el ementaires with a \rather long" proof; he does not mention if the onverse problem was addressed there.
Crux Mathemati orum
with Mathemati al Mayhem
Former Editors / An iens Reda teurs: Bru e L.R. Shawyer, James E. Totten
Crux Mathemati orum
Founding Editors / Reda teurs-fondateurs: Leopold Sauve & Frederi k G.B. Maskell Former Editors / An iens Reda teurs: G.W. Sands, R.E. Woodrow, Bru e L.R. Shawyer
Mathemati al Mayhem
Founding Editors / Reda teurs-fondateurs: Patri k Surry & Ravi Vakil Former Editors / An iens Reda teurs: Philip Jong, Je Higham, J.P. Grossman, Andre Chang, Naoki Sato, Cyrus Hsia, Shawn Godin, Je Hooper
