Пер­вое Ре­ше­ние. Обо­зна­чим a + b + c = λ. Тео­ре­ма Виета поз­во­ля­ет на­пи­сать ку­би­че­ское урав­не­ние, за­ви­ся­щее от па­ра­мет­ра λ, кор­ня­ми ко­то­ро­го яв­ля­ет­ся набор a, b, c, со­от­вет­ству­ю­щий дан­но­му λ:

От­сю­да видно, при любом λ есть ко­рень t = 1, то есть зна­че­ние x = 1 под­хо­дит. Оста­лось до­ка­зать, что нет дру­гих зна­че­ний, яв­ля­ю­щих­ся кор­ня­ми при любом λ (хотя это и так оче­вид­но). В самом деле, t² − (λ − 1)t + (10 − λ) = 0 озна­ча­ет Возь­мем любую пару зна­че­ний λ, при ко­то­рой дис­кри­ми­нант при­ни­ма­ет одно и то же по­ло­жи­тель­ное зна­че­ние, на­при­мер при λ = 10 и λ = −12 имеем t ∈ {0, 9} и t ∈ {−11, −2}  — пе­ре­се­че­ний нет. Итак, ответ x = 1.

Вто­рое ре­ше­ние. Вы­чтем из пер­во­го ра­вен­ства вто­рое, пре­об­ра­зо­вав, по­лу­чим (a − 1)(b − 1)(c − 1) = 0. От­сю­да сле­ду­ет, что одно из a, b, c равно еди­ни­це. Дру­гие x не под­хо­дят, так как трой­ки (a, b, c) = (4, 1, 1) и (a, b, c) = (0, 9, 1) удо­вле­тво­ря­ют усло­вию.

Ответ: 1.

Каж­дый уче­ник вы­пол­ня­ет пе­ре­ста­нов­ку: если он кого-то не­до­люб­ли­ва­ет, то пе­ре­ста­нов­ку, ме­ня­ю­щую его имя и имя того, кого он не­до­люб­ли­ва­ет; иначе пе­ре­ста­нов­ка три­ви­аль­на. Дру­ги­ми сло­ва­ми, ни­ка­кие два имени не ста­нут оди­на­ко­вы­ми после про­хож­де­ния лю­бо­го из уче­ни­ков. И для каж­до­го имени в ре­зуль­та­те есть имя, ко­то­рое при­ве­ло бы к та­ко­му ре­зуль­та­ту. Раз это утвер­жде­ние верно для лю­бо­го от­дель­но­го уче­ни­ка, это же тре­бо­ва­ние верно и для по­сле­до­ва­тель­но­сти уче­ни­ков. Таким об­ра­зом, зная, какое имя долж­но прий­ти в итоге и кто кого не­до­люб­ли­ва­ет, для каж­до­го уче­ни­ка из­вест­на вы­пол­ня­е­мая им пе­ре­ста­нов­ка. Таким об­ра­зом, для каж­до­го уче­ни­ка можно по ре­зуль­та­ту пе­ре­ста­нов­ки, ко­то­рый он дол­жен по­лу­чить, найти, какое имя долж­но было ему прий­ти. Таким об­ра­зом, в об­рат­ном на­прав­ле­нии по це­поч­ке вос­ста­нав­ли­ва­ет­ся, какое имя сле­ду­ет на­пи­сать из­на­чаль­но.

Ответ: сколь­ко угод­но.

Найдём концы диа­го­на­лей, обведённые Гри­шей. Каж­дая диа­го­наль имеет два конца, но не­ко­то­рые концы могут сов­па­дать, но не более двух в одной точке. Таким об­ра­зом, мы по­лу­чим от 3 до 6 вер­шин сто­уголь­ни­ка. Найдём со­от­вет­ству­ю­щее ко­ли­че­ство тре­уголь­ни­ков.

Для трёх вер­шин ко­ли­че­ство тре­уголь­ни­ков равно ко­ли­че­ству спо­со­бов вы­брать три раз­лич­ные вер­ши­ны

Для четырёх вер­шин пара со­сед­них яв­ля­ет­ся cто­ро­ной тре­уголь­ни­ка

(дру­гие две не сов­па­да­ют, а лишь их со­дер­жат). Таким об­ра­зом, ко­ли­че­ство равно

Для пяти вер­шин нужно вы­брать пять вер­шин и среди них одну, ко­то­рая яв­ля­ет­ся вер­ши­ной тре­уголь­ни­ка. Таким об­ра­зом, ко­ли­че­ство равно

Для ше­сти­уголь­ни­ка спо­соб един­ствен­ный после вы­бо­ра шести вер­шин, то есть

Итого, в сумме по­лу­ча­ем

Ответ:

Усло­вия за­да­чи тре­бу­ют, чтобы мышь про­грыз­ла каж­дую ко­роб­ку как ми­ни­мум в двух ме­стах: чтобы по­пасть в нее и чтобы по­ки­нуть её. Таким об­ра­зом, число от­вер­стий не мень­ше удво­ен­но­го числа ко­ро­бок, то есть 2 · (8ⁿ⁺¹ − 1) / 7. По­стро­им путь мыши с таким чис­лом от­вер­стий, при­чем вовсе без ко­ро­бок с про­гры­зен­ны­ми про­ти­во­по­лож­ны­ми стен­ка­ми. Мы будем со­став­лять его из сле­ду­ю­щих ку­соч­ков:

Дан­ный ри­су­нок изоб­ра­жа­ет спо­соб по­се­тить все ко­роб­ки раз­ме­ра 1 дм внут­ри одной ко­роб­ки раз­ме­ра 2 дм, про­гры­зя за­штри­хо­ван­ные места. За­ме­тим, что каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. Если те­перь мы обойдём все ко­роб­ки раз­ме­ра 2 дм в дан­ной ко­роб­ке раз­ме­ра 4 дм в том же по­ряд­ке и с от­вер­сти­я­ми в тех же ме­стах, как по­ка­за­но на ри­сун­ке, об­хо­дя при этом каж­дую ко­роб­ку раз­ме­ра 2 дм опи­сан­ным спо­со­бом, то по­лу­чим обход ко­роб­ки раз­ме­ра 4 дм, при ко­то­ром каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. И так далее: если обой­ти все ко­роб­ки раз­ме­ра 2^k дм в дан­ной ко­роб­ке раз­ме­ра 2^k+1 дм в том же по­ряд­ке и с от­вер­сти­я­ми в тех же ме­стах, как по­ка­за­но на ри­сун­ке, об­хо­дя при этом каж­дую ко­роб­ку раз­ме­ра 2^k дм опи­сан­ным спо­со­бом, то по­лу­чим обход ко­роб­ки раз­ме­ра 2^k+1 дм, при ко­то­ром каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. Чтобы в ре­зуль­та­те по­лу­чить за­мкну­тый путь внут­ри сун­ду­ка, ко­роб­ки раз­ме­ра 2ⁿ⁻¹ можно обой­ти по сле­ду­ю­щей схеме:

Те­перь, в какой бы ко­роб­ке этого за­мкну­то­го пути ни за­ве­лась мышь, она смо­жет про­сле­до­вать по этому пути, по­бы­вав ровно один раз в каж­дой ко­роб­ке, вер­нув­шись в из­на­чаль­ную, и сде­лав ровно по од­но­му от­вер­стию в двух со­сед­них стен­ках каж­дой ко­роб­ки.

Ответ: 2 · (8ⁿ⁺¹ − 1) / 7.

За­ме­тим, что за­ме­на пе­ре­мен­ной x → x + k при любом целом k не ме­ня­ет об­ла­сти зна­че­ний мно­го­чле­на. Тогда, сде­лав за­ме­ну x → x − (квад­рат­ные скоб­ки озна­ча­ют целую часть) можем счи­тать, что любой мно­го­член имеет один из двух видов: x² + q или x² + x + q.

Об­ла­сти зна­че­ний любых двух мно­го­чле­нов раз­но­го вида пе­ре­се­ка­ют­ся: в самом деле, зна­че­ния мно­го­чле­нов x² + q и x² + x + q' сов­па­да­ют при x = q − q'. Зна­чит, мно­го­чле­ны раз­но­го вида брать нель­зя.

Мно­го­чле­нов пер­во­го вида можно вы­брать не боль­ше двух, по­сколь­ку если об­ла­сти зна­че­ний f₁(x) = x² + q и f₂(x) = x² + q' не пе­ре­се­ка­ют­ся, то q − q' = 4k + 2 при не­ко­то­ром k ∈ Z. В самом деле, для не­чет­ной раз­но­сти сво­бод­ных чле­нов q − q' = 2k + 1 имеем f₁(k) = f₂(k + 1). Для де­ля­щей­ся на 4 раз­но­сти сво­бод­ных чле­нов q − q' = 4k имеем f₁(k − 1) = f₂(k + 1). Но если вы­бра­но хотя бы три мно­го­чле­на, то среди по­пар­ных раз­но­стей сво­бод­ных чле­нов хотя бы одна не имеет вид 4k + 2.

Мно­го­чле­нов вто­ро­го вида тоже можно вы­брать не боль­ше двух, по­сколь­ку если об­ла­сти зна­че­ний f₁(x) = x² + x + q и f²(x) = x² + x + q' не пе­ре­се­ка­ют­ся, то q − q' = 2k + 1 при не­ко­то­ром k ∈ Z. В самом деле, для чет­ной раз­но­сти сво­бод­ных чле­нов q − q' = 2k имеем f₁(k − 1) = f₂(k). Опять же, если вы­бра­но хотя бы три мно­го­чле­на, то среди по­пар­ных раз­но­стей сво­бод­ных чле­нов хотя бы одна четна.

Итак, боль­ше двух мно­го­чле­нов вы­брать нель­зя. При­мер для двух: f₁(x) = x² и f₂(x) = x² + 2.

Ответ: 2.

Пусть ∠CAB = x, ∠ABC = y, ∠DCA = z. Пред­по­ло­жим, что точка Q на­хо­дит­ся между A и F, точка P на­хо­дит­ся между C и E (∠FQH = ∠APH). При­ведём два ре­ше­ния за­да­чи.

Пер­вое ре­ше­ние.

Пусть точка M  — се­ре­ди­на HA, ∠AEH = ∠AFH = 90°. Сле­до­ва­тель­но, AFHE  — впи­сан­ный четырёхуголь­ник с цен­тром опи­сан­ной окруж­но­сти в точке M. Тре­уголь­ни­ки EFM и OQP рав­но­бед­рен­ные; ∠EMF = 2∠CAB = 2x; ∠POQ = 2x, от­сю­да тре­уголь­ник EFM по­до­бен QOP.

Четырёхуголь­ни­ки AEHF, AHPQ впи­сан­ные: ∠EFH = ∠EAH = ∠PQH; ∠FEH = ∠FAH = ∠QPH, от­ку­да тре­уголь­ник HEF по­до­бен HPQ.

До­ка­жем, что цик­ли­че­ские четырёхуголь­ни­ки EHFM, PQHO по­доб­ны:

Пусть ∠QHP = то су­ще­ству­ет по­во­рот с цен­тром в точке H с углом по­во­ро­та по ча­со­вой стрел­ке, от­но­ше­ни­ем Этот по­во­рот пе­ре­во­дит EHFM в QOPH.

Точке E, D, F, M лежат на окруж­но­сти де­вя­ти точек тре­уголь­ни­ка ABC (по­сколь­ку четырёхуголь­ни­ки ABDE, ACDF впи­сан­ные; ∠FDB = ∠CAF = x, ∠EDC = ∠BAE = x, ∠EDF = 180° − 2x = 180° − ∠EMF).

Пусть точка R₁ лежит между B и D так, что ∠R₁HD = по­это­му тре­уголь­ни­ки HQF и R₁HD по­доб­ны, по­это­му четырёхуголь­ни­ки DFME и R₁QOP также по­доб­ны.

По­сколь­ку четырёхуголь­ник DFME впи­сан­ный, то R₁QOP также цик­ли­чен. Из этого сле­ду­ет, что точки R и R₁ сов­па­да­ют. Тре­уголь­ни­ки DEF и RPQ по­доб­ны, то

Рас­смот­рим два цик­ли­че­ских четырёхуголь­ни­ка ACDF и ABDE: ∠BFD = ∠AFE = ∠ACB = z, ∠DFE = 180° − 2z. Тре­уголь­ни­ки DEF и RPQ по­доб­ны, ∠RQP = 180° − 2z. По­сколь­ку CR  — ка­са­тель­ная к окруж­но­сти тре­уголь­ни­ка PQR; ∠CRP = ∠RQP = 180° − 2z.

Таким об­ра­зом, в тре­уголь­ни­ке CPR имеем ∠CPR = z, CR = PR. Ана­ло­гич­но BR = QR:

что и тре­бо­ва­лось до­ка­зать.

Вто­рое ре­ше­ние.

Впи­шем тре­уголь­ник BQH в окруж­ность и эта окруж­ность будет пе­ре­се­кать пря­мую BC в точке R₃ (точка R₃ не сов­па­да­ет с точ­кой B). По­сколь­ку четырёхуголь­ни­ки APHQ и BQHR₃ впи­сан­ные, то ∠PHQ = 180° − ∠PAQ и ∠QHR₃ = 180° − ∠QBR³. Так же под­ра­зу­ме­ва­ет­ся, что ∠PHR₃ = 360° − ∠PHQ − ∠QHR₃ = 180° − ∠ACB. Сле­до­ва­тель­но, CPHR₃ также впи­сан­ный. Мы толь­ко что уста­но­ви­ли част­ный слу­чай тео­ре­мы Ми­ке­ля.

По­сколь­ку BQHR₃ и CR₃HP впи­сан­ные, по­лу­ча­ем, что ∠QR₃H = ∠QBH = 90° − ∠BAC и ∠HR₃P = ∠HCP = 90° − ∠BAC. Сле­до­ва­тель­но, ∠QR₃P = 180° − 2∠BAC = 180° − 2x. Ана­ло­гич­но имеем ∠PQR = 180° − 2z и ∠R3PQ = 180° − 2y. Как было по­ка­за­но в пер­вом ре­ше­нии, тре­уголь­ник DEF имеет такие же углы. Сле­до­ва­тель­но, тре­уголь­ник R₃PQ по­до­бен тре­уголь­ни­ку DEF. За­ме­тим, что ∠POQ + ∠PR₃Q = 2x + 180° − 2x = 180°, а это зна­чит, что точка R₃ лежит на окруж­но­сти тре­уголь­ни­ка OPQ ⇒ R₃ = R. За­кон­чить до­ка­за­тель­ство как в пер­вом ре­ше­нии.

Пер­вое Ре­ше­ние. Обо­зна­чим a + b + c = λ. Тео­ре­ма Виета поз­во­ля­ет на­пи­сать ку­би­че­ское урав­не­ние, за­ви­ся­щее от па­ра­мет­ра λ, кор­ня­ми ко­то­ро­го яв­ля­ет­ся набор a, b, c, со­от­вет­ству­ю­щий дан­но­му λ:

От­сю­да видно, при любом λ есть ко­рень t = 1, то есть зна­че­ние x = 1 под­хо­дит. Оста­лось до­ка­зать, что нет дру­гих зна­че­ний, яв­ля­ю­щих­ся кор­ня­ми при любом λ (хотя это и так оче­вид­но). В самом деле, t² − (λ − 1)t + (10 − λ) = 0 озна­ча­ет Возь­мем любую пару зна­че­ний λ, при ко­то­рой дис­кри­ми­нант при­ни­ма­ет одно и то же по­ло­жи­тель­ное зна­че­ние, на­при­мер при λ = 10 и λ = −12 имеем t ∈ {0, 9} и t ∈ {−11, −2}  — пе­ре­се­че­ний нет. Итак, ответ x = 1.

Вто­рое ре­ше­ние. Вы­чтем из пер­во­го ра­вен­ства вто­рое, пре­об­ра­зо­вав, по­лу­чим (a − 1)(b − 1)(c − 1) = 0. От­сю­да сле­ду­ет, что одно из a, b, c равно еди­ни­це. Дру­гие x не под­хо­дят, так как трой­ки (a, b, c) = (4, 1, 1) и (a, b, c) = (0, 9, 1) удо­вле­тво­ря­ют усло­вию.

Ответ: 1.

Не­фор­маль­но го­во­ря, про­бле­ма в этой за­да­че не в том, чтобы найти путь вы­чис­ле­ний, при­во­дя­щий к от­ве­ту; а в том, чтобы найти путь к от­ве­ту, про­хо­дя­щий через не слиш­ком боль­шое ко­ли­че­ство про­ме­жу­точ­ных вы­чис­ле­ний. По­ка­жем, как это сде­лать.

Как из­вест­но, пло­щадь тре­уголь­ни­ка, об­ра­зо­ван­но­го век­то­ра­ми и равна Если точка дви­жет­ся рав­но­мер­но и пря­мо­ли­ней­но, то ее ко­ор­ди­на­ты за­ви­сят от вре­ме­ни t как Тогда ве­ли­чи­на как функ­ция от t яв­ля­ет­ся мно­го­чле­ном вто­рой сте­пе­ни. Вы­бе­рем ось вре­ме­ни так, чтобы ноль был в се­ре­ди­не от­рез­ка на­блю­де­ния, а на­чаль­ный и ко­неч­ный мо­мен­ты имели ко­ор­ди­на­ты −1 и 1 со­от­вет­ствен­но. Обо­зна­чим Ко­ор­ди­на­ты точек B и C в се­ре­ди­не от­рез­ка на­блю­де­ния легко счи­та­ют­ся, это (12, 10) и (15, 14) со­от­вет­ствен­но. Итак,

От­ку­да

Ми­ни­мум квад­рат­но­го трех­чле­на до­сти­га­ет­ся в точке

Итак, мы видим, что ми­ни­мум вы­ра­же­ния попал на от­ре­зок на­блю­де­ния, кроме того он по­ло­жи­те­лен, то есть мо­дуль равен вы­ра­же­нию под мо­ду­лем. Итого, ис­ко­мая пло­щадь сна­ча­ла умень­ша­лась от 44 до 8, потом росла от 8 до 24, таким об­ра­зом при­ни­мая целые зна­че­ния раза.

Ответ: 53.

Легко по­нять, что если точка яв­ля­ет­ся кон­цом для хотя бы одной сто­ро­ны ше­сти­уголь­ни­ка, она яв­ля­ет­ся кон­цом для двух или для трёх сто­рон: боль­ше, чем 3, быть не может по­то­му что все углы равны 120°.

Да­вай­те не­мно­го по­ри­су­ем. Пред­ста­вим себе, что в каж­дую точку, яв­ля­ю­щу­ю­ся кон­цом для трёх сто­рон ше­сти­уголь­ни­ка, мы по­ста­ви­ли точку крас­ным фло­ма­сте­ром. А каж­дый путь по сто­ро­нам ше­сти­уголь­ни­ков от крас­ной точки до крас­ной точки мы об­ве­ли синим фло­ма­сте­ром. Таким об­ра­зом, синие линии идут по сто­ро­нам ше­сти­уголь­ни­ков и через вер­ши­ны, из ко­то­рых вы­хо­дит толь­ко две сто­ро­ны (иными сло­ва­ми, ко­то­рые яв­ля­ют­ся вер­ши­на­ми ровно для од­но­го ше­сти­уголь­ни­ка). За­ме­тим, что синие линии не пе­ре­се­ка­ют­ся иначе, чем в своих кон­цах, яв­ля­ю­щих­ся крас­ны­ми точ­ка­ми. Легко по­нять, что если точка яв­ля­ет­ся кон­цом для хотя бы одной сто­ро­ны ше­сти­уголь­ни­ка, она яв­ля­ет­ся кон­цом для двух или для трёх сто­рон: боль­ше чем 3 быть не может по­то­му что все углы равны 120°.

Таким об­ра­зом, мы по­лу­чи­ли изоб­ра­же­ние муль­ти­гра­фа на плос­ко­сти. Для него верна фор­му­ла Эй­ле­ра F − E + V  =  2, где F, E, V  — ко­ли­че­ства гра­ней, рёбер и вер­шин со­от­вет­ствен­но. По­сколь­ку все вер­ши­ны имеют сте­пень 3, 3V  =  2E. Кроме того F = n + 1, по­сколь­ку это все ше­сти­уголь­ни­ки и внеш­няя грань. Из этих трёх урав­не­ний вы­во­дит­ся E  =  3n − 3. Пройдём по внеш­не­му циклу. При этом мы шли по всем n ше­сти­уголь­ни­кам, зна­чит, при n > 1 не менее чем n раз ме­ня­ли ше­сти­уголь­ник, по ко­то­ро­му идем (вни­ма­ние: этот утвер­жде­ние не­вер­но, если n = 1: так и хо­ди­ли по од­но­му ше­сти­уголь­ни­ку, ни разу его не по­ме­няв). Зна­чит, во внеш­нем цикле не менее n ребер, зна­чит, в осталь­ном графе не боль­ше 2n − 3 рёбер. Каж­дое из них со­сто­ит ровно из од­но­го от­рез­ка, быв­ше­го сто­ро­ной для двух ше­сти­уголь­ни­ков, по­сколь­ку внут­ри мно­го­уголь­ни­ка не может быть точек, яв­ля­ю­щих­ся кон­ца­ми ровно для двух от­рез­ков сто­рон. Зна­чит, внут­ри не боль­ше 4n − 6 сто­рон ше­сти­уголь­ни­ков, скле­ен­ных по парам, зна­чит, на гра­ни­це лежит не менее 2n + 6 сто­рон.

Ответ: 2n + 6 при n ≥ 2, 6 при n = 1

При­ведём три­го­но­мет­ри­че­ское ре­ше­ние. До­ста­точ­но до­ка­зать, что

Тогда по тео­ре­ме Чевы пря­мые A₀A₁, B₀B₁, C₀C₁ пе­ре­се­ка­ют­ся в одной точке.

Пусть без огра­ни­че­ния общ­но­сти пря­мая a пе­ре­се­ка­ет внут­рен­ность тре­уголь­ни­ка ABC. Обо­зна­чим углы тре­уголь­ни­ка через α, β, γ, а угол B₀AA₁ через φ. Тогда углы AC₀A₁ и AB₀A₁ равны β и γ со­от­вет­ствен­но.

При­ме­няя тео­ре­му си­ну­сов к тре­уголь­ни­кам AB₀A₁ и AC₀A₁, по­лу­ча­ем

Ана­ло­гич­но, поль­зу­ясь ра­вен­ством вер­ти­каль­ных углов, по­лу­ча­ем

Ана­ло­гич­но

По­сколь­ку α + β − φ = π − (γ + φ), при пе­ре­мно­же­нии трёх вы­пи­сан­ных ра­венств все члены со­кра­тят­ся и мы по­лу­чим 1.

Те­перь пе­ре­пи­шем то же ре­ше­ние в тер­ми­нах про­ек­тив­ной гео­мет­рии. Про­стым от­но­ше­ни­ем трёх точек P, Q, R на одной пря­мой на­зо­вем такое число x, что Обо­зна­чим

До­ста­точ­но до­ка­зать, что

Тогда по тео­ре­ме Чевы пря­мые A₀A₁, B₀B₁ и C₀C₁ пе­ре­се­ка­ют­ся в одной точке.

Двой­ным от­но­ше­ни­ем пря­мых p, q, r, s на­зо­вем число где знак плюс берётся, если r и s рас­по­ло­же­ны в одной паре вер­ти­каль­ных углов от­но­си­тель­но p и q, а знак минус  — иначе.

Про­ведём через вер­ши­ны тре­уголь­ни­ка A, B, C пря­мые p, q, r, па­рал­лель­ные про­ти­во­по­лож­ным сто­ро­нам a', b', c' тре­уголь­ни­ка ABC. Тогда, как из­вест­но, равно двой­но­му от­но­ше­нию пря­мых (a, p; c', b'). Ана­ло­гич­но и равны двой­ным от­но­ше­ни­ям (b, q; a', c') и (c, r; b', a'). Но из па­рал­лель­но­сти

Остаётся до­ка­зать, что

Здесь участ­ву­ют двой­ные от­но­ше­ния одной и той же четвёрки пря­мых, но взя­тых в раз­ных по­ряд­ках. Обо­зна­чим Из­вест­но, что при пе­ре­ста­нов­ке пря­мых c' и b' двой­ное от­но­ше­ние x за­ме­ня­ет­ся на а при пе­ре­ста­нов­ке пря­мых a' и b'  — на 1 − x. Зна­чит, и По­лу­ча­ем

что и тре­бо­ва­лось.

За­ме­тим, что за­ме­на пе­ре­мен­ной x → x + k при любом целом k не ме­ня­ет об­ла­сти зна­че­ний мно­го­чле­на. Тогда, сде­лав за­ме­ну x → x − (квад­рат­ные скоб­ки озна­ча­ют целую часть) можем счи­тать, что любой мно­го­член имеет один из двух видов: x² + q или x² + x + q.

Об­ла­сти зна­че­ний любых двух мно­го­чле­нов раз­но­го вида пе­ре­се­ка­ют­ся: в самом деле, зна­че­ния мно­го­чле­нов x² + q и x² + x + q' сов­па­да­ют при x = q − q'. Зна­чит, мно­го­чле­ны раз­но­го вида брать нель­зя.

Мно­го­чле­нов пер­во­го вида можно вы­брать не боль­ше двух, по­сколь­ку если об­ла­сти зна­че­ний f₁(x) = x² + q и f₂(x) = x² + q' не пе­ре­се­ка­ют­ся, то q − q' = 4k + 2 при не­ко­то­ром k ∈ Z. В самом деле, для не­чет­ной раз­но­сти сво­бод­ных чле­нов q − q' = 2k + 1 имеем f₁(k) = f₂(k + 1). Для де­ля­щей­ся на 4 раз­но­сти сво­бод­ных чле­нов q − q' = 4k имеем f₁(k − 1) = f₂(k + 1). Но если вы­бра­но хотя бы три мно­го­чле­на, то среди по­пар­ных раз­но­стей сво­бод­ных чле­нов хотя бы одна не имеет вид 4k + 2.

Мно­го­чле­нов вто­ро­го вида тоже можно вы­брать не боль­ше двух, по­сколь­ку если об­ла­сти зна­че­ний f₁(x) = x² + x + q и f²(x) = x² + x + q' не пе­ре­се­ка­ют­ся, то q − q' = 2k + 1 при не­ко­то­ром k ∈ Z. В самом деле, для чет­ной раз­но­сти сво­бод­ных чле­нов q − q' = 2k имеем f₁(k − 1) = f₂(k). Опять же, если вы­бра­но хотя бы три мно­го­чле­на, то среди по­пар­ных раз­но­стей сво­бод­ных чле­нов хотя бы одна четна.

Итак, боль­ше двух мно­го­чле­нов вы­брать нель­зя. При­мер для двух: f₁(x) = x² и f₂(x) = x² + 2.

Ответ: 2.

Будем ре­шать чуть обобщённую за­да­чу, а имен­но: за­фик­си­ру­ем на­ту­раль­ное m и будем ис­кать все n, для ко­то­рых в любом из m мно­жеств все остат­ки раз­лич­ны. Ин­декс j про­бе­га­ет зна­че­ния

Для на­ча­ла до­ка­жем, что все n, не де­ля­щи­е­ся на про­стые числа мень­шие либо рав­ные m + 1, под­хо­дят. Рас­смот­рим пе­ре­ста­нов­ку τ: i → (m + 1)i mod n (здесь мы поз­во­лим себе воль­ность счи­тать, что остат­ки идут от 1 до n, а не от 0 до n – 1 как обыч­но). По­сколь­ку n вза­им­но про­сто с m + 1, остат­ки не по­вто­ря­ют­ся. Зна­чит, по прин­ци­пу Ди­ри­х­ле, каж­дый оста­ток встре­ча­ет­ся ровно один раз. Ана­ло­гич­но, каж­дый оста­ток встре­ча­ет­ся ровно один раз и в каж­дом из мно­жеств

До­ка­жем, что пе­ре­ста­нов­ки с тре­бу­е­мы­ми свой­ства­ми не су­ще­ству­ет если и Пред­по­ло­жим об­рат­ное, за­фик­си­ру­ем наи­мень­шее такое p и обо­зна­чим через k мак­си­маль­ную сте­пень p, на ко­то­рую де­лит­ся n.

Спер­ва рас­смот­рим слу­чай p  =  2. За­ме­тим что

фор­му­ла легко до­ка­зы­ва­ет­ся по ин­дук­ции. Тогда сумма n чисел, да­ю­щих остат­ки 1, 2, ..., n, срав­ни­ма с по мо­ду­лю n. По­счи­та­ем двумя спо­со­ба­ми оста­ток суммы по мо­ду­лю n. С одной сто­ро­ны, все сла­га­е­мые дают раз­ные остат­ки, зна­чит, сумма С дру­гой сто­ро­ны, по тем же со­об­ра­же­ни­ям у суммы от­дель­но такой оста­ток, и у суммы такой же, зна­чит, их раз­ность имеет оста­ток 0. За­ме­тим, что

по­сколь­ку n + 1 не­чет­ное а не де­лит­ся на 2^k. Пред­по­ло­же­ние при­ве­де­но к про­ти­во­ре­чию.

По­про­бу­ем по­лу­чить ре­ше­ние в том же духе для про­из­воль­но­го p. Не­боль­шой до­гад­кой, ко­то­рую нужно сде­лать на этом этапе ре­ше­ния, будет то, что счи­тать надо сумму p  — 1-х сте­пе­ней. Сла­бой под­сказ­кой в эту сто­ро­ну яв­ля­ет­ся то, что p – 1  =  1 для двой­ки p  =  2, и в этом же слу­чае сра­бо­тал под­счет суммы пер­вых сте­пе­ней. Го­раз­до более силь­ной  — то что p  — 1-е сте­пе­ни по мо­ду­лю p ведут себя про­сто  — это 1 если число не равно нулю, 0, если равно.

Итак, далее счи­та­ем что обо­зна­чим

Лемма 1. За­ме­тим, что и До­ста­точ­но до­ка­зать этот факт для по­сколь­ку

Для S(p^k) про­ве­дем ин­дук­цию по k. При k  =  1 утвер­жде­ние сле­ду­ет из Малой тео­ре­мы Ферма: среди сла­га­е­мых p – 1 еди­ни­ца и один ноль. Пусть до­ка­за­но для k, до­ка­жем для k + 1. Тогда

Все срав­не­ния по мо­ду­лю p^k+1.

Те­перь для каж­до­го j: рас­смот­рим сумму

Рас­кро­ем все сте­пе­ни по би­но­му Нью­то­на, по­лу­чим сла­га­е­мые вида

С дру­гой сто­ро­ны, все члены в S_j(n)  — это пе­ре­став­лен­ные в каком-то по­ряд­ке остат­ки по мо­ду­лю n чле­нов суммы S(n), то есть Итак, мы хотим найти такой набор α_j, чтобы до­мно­жив на него срав­ни­мо­сти и сло­жив мы смог­ли бы прий­ти к про­ти­во­ре­чию. Сде­лать это по­мо­жет вто­рая лемма.

Лемма 2. Су­ще­ству­ют такие целые числа α₁, ..., α_p – 1, что

Сна­ча­ла по­ка­жем, как из этой леммы вы­ве­сти остав­шу­ю­ся часть утвер­жде­ния за­да­чи. Рас­смот­рим срав­ни­мость

С одной сто­ро­ны, если рас­крыть все S_j по би­но­му Нью­то­на, и со­брать вме­сте члены вида то по Лемме 2 перед каж­дым чле­ном ко­эф­фи­ци­ент, рав­ный нулю по мо­ду­лю p^k. Тогда:

Вспом­нив, что видим, что все члены вида со­кра­ти­лись с пра­вой ча­стью, итак

Но пер­вая скоб­ка не де­лит­ся на p по Лемме 2, а S(n) не де­лит­ся на p^k по Лемме 1. Оста­лось до­ка­зать лемму 2. Спер­ва от­ме­тим, что если вме­сто на­бо­ра целых чисел α_j уда­лось по­до­брать набор ра­ци­о­наль­ных чисел β_j, таких что их зна­ме­на­те­ли не де­лят­ся на p, все срав­ни­мо­сти из усло­вия леммы за­ме­ни­лись на ра­вен­ства, а по­след­нее вы­ра­же­ние равно це­ло­му числу, не де­ля­ще­му­ся на p  — то лемма до­ка­за­на, до­ста­точ­но все β_j за­ме­нить на срав­ни­мые с ними по мо­ду­лю p^k целые числа. Срав­ни­мость опре­де­ле­на кор­рект­но по­сколь­ку зна­ме­на­те­ли не де­лят­ся на p.

Те­перь оста­лось взять

Чи­та­те­лю оста­ет­ся упраж­не­ние до­ка­зать (на­при­мер, по ин­дук­ции, по­сколь­ку про­сто­та p здесь уже не важна), что во всех усло­ви­ях Леммы 2, кроме по­след­не­го, по­лу­ча­ет­ся 0, а в по­след­нем

Ответ: все n, не де­ля­щи­е­ся ни на 2, ни на 3, ни на 5.

За­ме­тим, что при любом k верно ра­вен­ство k² − (k + 1)² − (k + 2)² + (k + 3)² = 4. По­это­му вся сумма равна 1 + 504 · 4 + 2018² = 4074341.

Ответ: 4074341.

Каж­дый уче­ник вы­пол­ня­ет пе­ре­ста­нов­ку: если он кого-то не­до­люб­ли­ва­ет, то пе­ре­ста­нов­ку, ме­ня­ю­щую его имя и имя того, кого он не­до­люб­ли­ва­ет; иначе пе­ре­ста­нов­ка три­ви­аль­на. Дру­ги­ми сло­ва­ми, ни­ка­кие два имени не ста­нут оди­на­ко­вы­ми после про­хож­де­ния лю­бо­го из уче­ни­ков. И для каж­до­го имени в ре­зуль­та­те есть имя, ко­то­рое при­ве­ло бы к та­ко­му ре­зуль­та­ту. Раз это утвер­жде­ние верно для лю­бо­го от­дель­но­го уче­ни­ка, это же тре­бо­ва­ние верно и для по­сле­до­ва­тель­но­сти уче­ни­ков. Таким об­ра­зом, зная, какое имя долж­но прий­ти в итоге и кто кого не­до­люб­ли­ва­ет, для каж­до­го уче­ни­ка из­вест­на вы­пол­ня­е­мая им пе­ре­ста­нов­ка. Таким об­ра­зом, для каж­до­го уче­ни­ка можно по ре­зуль­та­ту пе­ре­ста­нов­ки, ко­то­рый он дол­жен по­лу­чить, найти, какое имя долж­но было ему прий­ти. Таким об­ра­зом, в об­рат­ном на­прав­ле­нии по це­поч­ке вос­ста­нав­ли­ва­ет­ся, какое имя сле­ду­ет на­пи­сать из­на­чаль­но.

Ответ: сколь­ко угод­но.

До­стро­им тре­уголь­ник ABC до пря­мо­уголь­ни­ка ABCD и вы­бе­рем на его сто­ро­не CD точку P так, что AP па­рал­лель­но CM. Тогда PC = AD, DP = CN, и пря­мо­уголь­ные тре­уголь­ни­ки ADP и CPN равны, причём ∠DAP = ∠CPN. По­это­му ∠APD + ∠CPN = 90° и ∠APN = 90°, то есть APN  — рав­но­бед­рен­ный пря­мо­уголь­ный тре­уголь­ник. Зна­чит, ∠PAN = 45° и, в силу па­рал­лель­но­сти пря­мых AP и CM, ост­рый угол между пря­мы­ми AN и CM тоже со­став­ля­ет 45 гра­ду­сов.

Ответ: 45°.

Легко по­нять, что если точка яв­ля­ет­ся кон­цом для хотя бы одной сто­ро­ны ше­сти­уголь­ни­ка, она яв­ля­ет­ся кон­цом для двух или для трёх сто­рон: боль­ше, чем 3, быть не может по­то­му что все углы равны 120°.

Да­вай­те не­мно­го по­ри­су­ем. Пред­ста­вим себе, что в каж­дую точку, яв­ля­ю­щу­ю­ся кон­цом для трёх сто­рон ше­сти­уголь­ни­ка, мы по­ста­ви­ли точку крас­ным фло­ма­сте­ром. А каж­дый путь по сто­ро­нам ше­сти­уголь­ни­ков от крас­ной точки до крас­ной точки мы об­ве­ли синим фло­ма­сте­ром. Таким об­ра­зом, синие линии идут по сто­ро­нам ше­сти­уголь­ни­ков и через вер­ши­ны, из ко­то­рых вы­хо­дит толь­ко две сто­ро­ны (иными сло­ва­ми, ко­то­рые яв­ля­ют­ся вер­ши­на­ми ровно для од­но­го ше­сти­уголь­ни­ка). За­ме­тим, что синие линии не пе­ре­се­ка­ют­ся иначе, чем в своих кон­цах, яв­ля­ю­щих­ся крас­ны­ми точ­ка­ми. Легко по­нять, что если точка яв­ля­ет­ся кон­цом для хотя бы одной сто­ро­ны ше­сти­уголь­ни­ка, она яв­ля­ет­ся кон­цом для двух или для трёх сто­рон: боль­ше чем 3 быть не может по­то­му что все углы равны 120°.

Таким об­ра­зом, мы по­лу­чи­ли изоб­ра­же­ние муль­ти­гра­фа на плос­ко­сти. Для него верна фор­му­ла Эй­ле­ра F − E + V  =  2, где F, E, V  — ко­ли­че­ства гра­ней, рёбер и вер­шин со­от­вет­ствен­но. По­сколь­ку все вер­ши­ны имеют сте­пень 3, 3V  =  2E. Кроме того F = n + 1, по­сколь­ку это все ше­сти­уголь­ни­ки и внеш­няя грань. Из этих трёх урав­не­ний вы­во­дит­ся E  =  3n − 3. Пройдём по внеш­не­му циклу. При этом мы шли по всем n ше­сти­уголь­ни­кам, зна­чит, при n > 1 не менее чем n раз ме­ня­ли ше­сти­уголь­ник, по ко­то­ро­му идем (вни­ма­ние: этот утвер­жде­ние не­вер­но, если n = 1: так и хо­ди­ли по од­но­му ше­сти­уголь­ни­ку, ни разу его не по­ме­няв). Зна­чит, во внеш­нем цикле не менее n ребер, зна­чит, в осталь­ном графе не боль­ше 2n − 3 рёбер. Каж­дое из них со­сто­ит ровно из од­но­го от­рез­ка, быв­ше­го сто­ро­ной для двух ше­сти­уголь­ни­ков, по­сколь­ку внут­ри мно­го­уголь­ни­ка не может быть точек, яв­ля­ю­щих­ся кон­ца­ми ровно для двух от­рез­ков сто­рон. Зна­чит, внут­ри не боль­ше 4n − 6 сто­рон ше­сти­уголь­ни­ков, скле­ен­ных по парам, зна­чит, на гра­ни­це лежит не менее 2n + 6 сто­рон.

Ответ: 2n + 6 при n ≥ 2, 6 при n = 1

Имеет место один из двух слу­ча­ев.

А)  Пусть оба наи­мень­ших де­ли­те­ля p и q  — про­стые числа. Тогда про­стым будет число r = (n/p + n/q) − (p + q), и pqr = (p + q)(n − pq). По­сколь­ку числа p + q и pq вза­им­но про­сты, по­лу­ча­ем r = p + q, от­ку­да p = 2 и n = 4q. Но тогда в силу вы­бо­ра q по­лу­ча­ем q = 3 и n = 12.

Б)  Пусть наи­мень­шие де­ли­те­ли имеют вид p и p², где p про­стое. Этот слу­чай раз­би­ра­ет­ся ана­ло­гич­но.

За­ме­ча­ние. Воз­мож­на си­ту­а­ция, когда число имеет всего три соб­ствен­ных де­ли­те­ля. Тогда упо­мя­ну­тая в усло­вии раз­ность есть раз­ность между наи­боль­шим и наи­мень­шим из соб­ствен­ных де­ли­те­лей. Но любое число с тремя соб­ствен­ны­ми де­ли­те­ля­ми есть сте­пень про­сто­го p⁴, а раз­ность p³ − p про­стым чис­лом быть не может.

Ответ: 12 (2, 3, 4, 6).

Усло­вия за­да­чи тре­бу­ют, чтобы мышь про­грыз­ла каж­дую ко­роб­ку как ми­ни­мум в двух ме­стах: чтобы по­пасть в нее и чтобы по­ки­нуть её. Таким об­ра­зом, число от­вер­стий не мень­ше удво­ен­но­го числа ко­ро­бок, то есть 2 · (8ⁿ⁺¹ − 1) / 7. По­стро­им путь мыши с таким чис­лом от­вер­стий, при­чем вовсе без ко­ро­бок с про­гры­зен­ны­ми про­ти­во­по­лож­ны­ми стен­ка­ми. Мы будем со­став­лять его из сле­ду­ю­щих ку­соч­ков:

Дан­ный ри­су­нок изоб­ра­жа­ет спо­соб по­се­тить все ко­роб­ки раз­ме­ра 1 дм внут­ри одной ко­роб­ки раз­ме­ра 2 дм, про­гры­зя за­штри­хо­ван­ные места. За­ме­тим, что каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. Если те­перь мы обойдём все ко­роб­ки раз­ме­ра 2 дм в дан­ной ко­роб­ке раз­ме­ра 4 дм в том же по­ряд­ке и с от­вер­сти­я­ми в тех же ме­стах, как по­ка­за­но на ри­сун­ке, об­хо­дя при этом каж­дую ко­роб­ку раз­ме­ра 2 дм опи­сан­ным спо­со­бом, то по­лу­чим обход ко­роб­ки раз­ме­ра 4 дм, при ко­то­ром каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. И так далее: если обой­ти все ко­роб­ки раз­ме­ра 2^k дм в дан­ной ко­роб­ке раз­ме­ра 2^k+1 дм в том же по­ряд­ке и с от­вер­сти­я­ми в тех же ме­стах, как по­ка­за­но на ри­сун­ке, об­хо­дя при этом каж­дую ко­роб­ку раз­ме­ра 2^k дм опи­сан­ным спо­со­бом, то по­лу­чим обход ко­роб­ки раз­ме­ра 2^k+1 дм, при ко­то­ром каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. Чтобы в ре­зуль­та­те по­лу­чить за­мкну­тый путь внут­ри сун­ду­ка, ко­роб­ки раз­ме­ра 2ⁿ⁻¹ можно обой­ти по сле­ду­ю­щей схеме:

Те­перь, в какой бы ко­роб­ке этого за­мкну­то­го пути ни за­ве­лась мышь, она смо­жет про­сле­до­вать по этому пути, по­бы­вав ровно один раз в каж­дой ко­роб­ке, вер­нув­шись в из­на­чаль­ную, и сде­лав ровно по од­но­му от­вер­стию в двух со­сед­них стен­ках каж­дой ко­роб­ки.

Ответ: 2 · (8ⁿ⁺¹ − 1) / 7.

Для крат­ко­сти ко­ман­ду влево будем обо­зна­чать Л, впра­во – П, вверх – В, вниз – Н. Чтобы робот вер­нул­ся в ис­ход­ное по­ло­же­ние не­об­хо­ди­мо и до­ста­точ­но, чтобы ему было от­да­но ко­манд Л столь­ко же, сколь­ко и ко­манд П, а ко­манд В – столь­ко же, сколь­ко и Н. Пусть k –ко­ли­че­ство ко­манд Л в по­сле­до­ва­тель­но­сти. Под­счи­та­ем ко­ли­че­ство N_k ис­ко­мых по­сле­до­ва­тель­но­стей для k от 0 до 2.

 ·  По­сле­до­ва­тель­ность со­сто­ит толь­ко из ко­манд В и Н. Так как их по­ров­ну, то на 2 ме­стах из 4 долж­на быть ко­ман­да В, а на остав­ших­ся двух – Н. Вы­брать 2 места из 4 можно спо­со­ба­ми. Сле­до­ва­тель­но,

 ·  Каж­дая из ко­манд Л, П, В, Н встре­ча­ет­ся в по­сле­до­ва­тель­но­сти ровно 1 раз. Число пе­ре­ста­но­вок из 4 эле­мен­тов равно 4!. По­это­му

 ·  Здесь две Л, две П и нет ко­манд В и Н. Две ко­ман­ды Л можно раз­ме­стить спо­со­ба­ми. Зна­чит,

Таким об­ра­зом, ис­ко­мое число по­сле­до­ва­тель­но­стей равно

Ответ: 36.

На пря­мой, про­ве­ден­ной через две раз­лич­ные точки A и D, от­ме­тим точки B и как на ри­сун­ке. Раз­де­лим раз­вер­ну­тые углы и DCB (ко­то­рые сле­ду­ет пред­став­лять себе от­ло­жен­ны­ми сна­ча­ла в верх­нюю, а затем и в ниж­нюю по­лу­плос­кость от­но­си­тель­но пря­мой AD) на три рав­ные части. По­лу­чим в ре­зуль­та­те пря­мые, об­ра­зу­ю­щие угол 60° с пря­мой AD и пе­ре­се­ка­ю­щи­е­ся в точ­ках K и Пусть O  — точка пе­ре­се­че­ния AD и Угол BKO равен, оче­вид­но, 30°. Раз­де­лив его на три части, по­лу­чим тре­бу­е­мый угол. По­стро­е­ние вы­пол­не­но.

Ответ: см. рис.