Число дней, за ко­то­рые Че­бу­раш­ка смо­жет съесть все апель­си­ны, не менее 8 (иначе не опу­сто­шить вось­мую ко­роб­ку), общее число апель­си­нов  — 36, по­это­му то есть

Для того, чтобы по­ка­зать, что все такие на­ту­раль­ные k удо­вле­тво­ря­ют усло­вию за­да­чи, рас­пре­де­лим ко­роб­ки в k групп так, чтобы апель­си­нов в каж­дой груп­пе было по­ров­ну, Ал­го­ритм по­гло­ще­ния апель­си­нов таков: каж­дый день съе­да­ет­ся по од­но­му апель­си­ну из каж­дой груп­пы (не важно, из какой ко­роб­ки). Ис­ко­мое рас­пре­де­ле­ние:

при	1-ая и 8-ая ко­роб­ки; 2-ая и 7-ая ко­роб­ки; 3-ая и 6-ая ко­роб­ки; 4-ая и 5-ая ко­роб­ки
при	1-ая и 8-ая ко­роб­ки; 3-ая и 6-ая ко­роб­ки; 4-ая и 8-ая ко­роб­ки; 7-ая и 5-ая ко­роб­ки
при	1-ая, 8-ая ко­роб­ки; 2-ая и 7-ая ко­роб­ки; 3-ая и 6-ая, 4-ая и 5-ая ко­роб­ки
при	един­ствен­ная груп­па со­сто­ит из всех ко­ро­бок.

Ответ: см. таб­ли­цу.

Возьмём не­ко­то­рую рас­ста­нов­ку ладей, удо­вле­тво­ря­ю­щую усло­вию за­да­чи. Пусть в этой рас­ста­нов­ке есть хотя бы одна ладья, не сто­я­щая на краю доски. Рас­смот­рим край­ние клет­ки доски, сто­я­щие с вы­бран­ной в одной стро­ке и одном столб­це  — всего их 4. Из усло­вия за­да­чи сле­ду­ет, что хотя бы одна из этих кле­ток сво­бод­на, по­это­му вы­бран­ную ладью мы можем пе­ре­ме­стить на эту клет­ку, и рас­ста­нов­ка по-преж­не­му будет удо­вле­тво­рять усло­вию за­да­чи. По­вто­рим про­цесс для всех кле­ток, не сто­я­щих с краю. Из этого можно сде­лать вывод, что су­ще­ству­ет кор­рект­ная рас­ста­нов­ка, в ко­то­рой ладей не мень­ше, чем в ис­ход­ной, но все они стоят на краю доски. По­это­му ладей в любой кор­рект­ной рас­ста­нов­ке не может быть боль­ше ко­ли­че­ства край­них кле­ток, то есть 28.

При­мер на 28 кле­ток: ста­вим всех ладей на край­ние клет­ки доски.

Ответ: на­при­мер на 28 кле­ток, ста­вим всех ладей на край­ние клет­ки доски.

За­ме­тим, что

До­ка­жем те­перь, что

В силу сим­мет­рич­но­сти левой и пра­вой ча­стей не­ра­вен­ства, можно без огра­ни­че­ния общ­но­сти счи­тать, что тогда

При­ме­няя транс­не­ра­вен­ство для на­бо­ров и

по­лу­ча­ем

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

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

Пер­вый тип: каж­дая кла­ви­ша ак­кор­да со­при­ка­са­ет­ся с какой-то дру­гой кла­ви­шей.

По­счи­та­ем все такие ак­кор­ды по груп­пам:

1)  Все кла­ви­ши белые  — 5 ак­кор­дов.

2)  Сред­няя кла­ви­ша чёрная  — 5 ак­кор­дов.

3)  Обе край­ние кла­ви­ши чёрные  — 3 ак­кор­да.

4)  Ровно одна край­няя кла­ви­ша чёрная  — 8 ак­кор­дов.

Всего 21 ак­корд.

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

1)  Все кла­ви­ши белые  — 20 ак­кор­дов.

2)  Со­при­ка­са­ю­щи­е­ся кла­ви­ши белые, остав­ша­я­ся  — чёрная  — 17 ак­кор­дов.

3)  Со­при­ка­са­ю­щи­е­ся кла­ви­ши раз­но­го цвета, остав­ша­я­ся  — белая  — 42 ак­кор­да.

4)  Со­при­ка­са­ю­щи­е­ся кла­ви­ши раз­но­го цвета, остав­ша­я­ся  — чёрная  — 34 ак­кор­да.

Всего 113 ак­кор­дов.

Тогда ко­ли­че­ство ак­кор­дов, кла­ви­ши ко­то­рых не со­при­ка­са­ют­ся, равно Среди таких ак­кор­дов ровно 10, все кла­ви­ши ко­то­рых белые. Зна­чит, ис­ко­мое число ак­кор­дов, ко­то­рые сыг­ра­ет Саша, равно 76.

Ответ: 76.

Рас­смот­рим пря­мо­уголь­ник раз­ме­ром 6 × 2 (6 кле­ток по го­ри­зон­та­ли и 2 клет­ки по вер­ти­ка­ли) и до­ка­жем, что в нём может рас­по­ла­гать­ся не более 4 прин­цесс. Раз­де­лим такой пря­мо­уголь­ник на квад­ра­ты раз­ме­ром За­ме­тим, что в каж­дом таком квад­ра­те может рас­по­ла­гать­ся не более 2 прин­цесс, причём если прин­цес­сы две, то они стоят толь­ко так, как по­ка­за­но на ри­сун­ке 1.

Пред­по­ло­жим, что в каком-то пря­мо­уголь­ни­ке ока­за­лось не менее 5 прин­цесс. Тогда в каких-то двух из его квад­ра­тов 2 × 2 ока­за­лось по 2 прин­цес­сы. Эти квад­ра­ты не могут быть со­сед­ни­ми, так как тогда одна из прин­цесс ока­жет­ся под боем дру­гой (см. рис. 2). Если же эти квад­ра­ты не со­сед­ние, а край­ние (см. рис. 3), то в сред­ний квад­рат нель­зя будет по­ста­вить ни одну прин­цес­су, так как ей будет бить какая-то дру­гая. Сле­до­ва­тель­но, в каж­дом таком пря­мо­уголь­ни­ке может рас­по­ла­гать­ся не более 4 прин­цесс. Доска раз­ме­ром 12 × 12 раз­би­ва­ет­ся на 12 таких пря­мо­уголь­ни­ков, зна­чит, на всю доску можно по­ста­вить не более 48 прин­цесс. При­мер при­ведён на ри­сун­ке 4.

Рис. 1

Рис. 2

Рис. 3

Рис. 4

Ответ: 48 прин­цесс.

Пусть число n  — удач­ное, где   — на­ту­раль­ные сла­га­е­мые. Если пред­по­ло­жить, что то n можно раз­бить в сумму раз­лич­ных на­ту­раль­ных сла­га­е­мых еще одним спо­со­бом:

Таким об­ра­зом,

Далее, если пред­по­ло­жить, что то для n опять можно при­ве­сти дру­гое раз­би­е­ние:

Зна­чит, Про­дол­жая так далее, по­лу­ча­ем

Если то и снова можно скон­стру­и­ро­вать дру­гое раз­би­е­ние.

На­ко­нец, не­труд­но ви­деть, что при или по­лу­ча­ю­щи­е­ся числа 55 и 56 яв­ля­ют­ся удач­ны­ми.

Ответ: 55 и 56.

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

На­зо­вем ряд пол­ным, если в него по­па­ли 4 шашки из 1-й кучки или 4 шашки из вто­рой кучки.

Из пер­вой кучки не более 3 шашек не по­па­дут в пол­ный ряд, и из вто­рой кучки  — тоже не более 3. Но всего в этих двух куч­ках  — более всех шашек, то есть не менее 43. Зна­чит, не менее шашек  — в пол­ных рядах. Тогда пол­ных рядов  — не менее 9. Но всего рядов 8, зна­чит, есть осо­бый ряд, куда по­па­ли по 4 шашки из обеих кучек. Сво­бод­ные поля раз­ных цве­тов лежат по раз­ные сто­ро­ны осо­бо­го ряда, и между собой не со­при­ка­са­ют­ся. Раз­ло­жим на них шашки тре­тьей кучки.

Раз­ло­жим шашки на кучки по цве­там.

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

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

На­зо­вем ряд пол­ным, если в него по­па­ли 4 шашки из 1-й кучки или 4 шашки из вто­рой кучки.

Из пер­вой кучки не более 3 шашек не по­па­дут в пол­ный ряд, и из вто­рой кучки  — тоже не более 3. Но всего в этих двух куч­ках  — более всех шашек, то есть не менее 43. Зна­чит, не менее шашек  — в пол­ных рядах. Тогда пол­ных рядов  — не менее де­вя­ти. Но всего рядов во­семь, зна­чит, есть осо­бый ряд, куда по­па­ли по 4 шашки из обеих кучек. Сво­бод­ные поля раз­ных цве­тов лежат по раз­ные сто­ро­ны осо­бо­го ряда, и между собой не со­при­ка­са­ют­ся. Раз­ло­жим на них шашки тре­тьей кучки.

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

Про­ве­дем на ко­ор­ди­нат­ной плос­ко­сти пря­мую ℓ с урав­не­ни­ем Пара (m, n) удо­вле­тво­ря­ет не­ра­вен­ствам из усло­вия в точ­но­сти тогда, когда точка лежит выше пря­мой ℓ, а точка   — ниже пря­мой ℓ. Это озна­ча­ет, что пря­мая ℓ пе­ре­се­ка­ет клет­ку, ниж­ний левый угол ко­то­рой имеет ко­ор­ди­на­ты (n, m). Оста­ет­ся по­счи­тать, сколь­ко кле­ток она пе­ре­се­ка­ет в квад­ра­те Она пе­ре­се­ка­ет 100 го­ри­зон­таль­ных линий ре­шет­ки и 70 вер­ти­каль­ных

Итого, она пе­ре­се­ка­ет 170 линий ре­шет­ки. По­сколь­ку ℓ не про­хо­дит через узлы ре­шет­ки, кроме точки (0, 0) (это сле­ду­ет из ир­ра­ци­о­наль­но­сти числа то она пе­ре­се­ка­ет 169 кле­ток, у ко­то­рых левый ниж­ний угол при­над­ле­жит ука­зан­но­му квад­ра­ту. Самую первую клет­ку с углом (0, 0) нам счи­тать не нужно, так как по усло­вию на­ту­раль­ные.

Ответ: 169 пар.

Сна­ча­ла до­ка­жем, что боль­ше 13 хо­ро­ших пар по­лу­чить­ся не могло. Назовём число пло­хим, если оно про­стое и не мень­ше 15. Есть всего че­ты­ре пло­хих числа: 17, 19, 23, 29. Ни одно из осталь­ных чисел от 1 до 30 не может де­лить­ся ни на одно пло­хое, а сами пло­хие числа могут де­лить­ся толь­ко на еди­ни­цу (среди осталь­ных). Сле­до­ва­тель­но, мак­си­мум одно из пло­хих чисел даст хо­ро­шую пару с еди­ни­цей, а осталь­ные ми­ни­мум три пло­хих числа «ис­пор­тят» ми­ни­мум 2 пары.

Те­перь рас­смот­рим такие 13 хо­ро­ших пар:

Остав­ши­е­ся 4 числа разобьём на пары, на­при­мер, так: (17, 19), (23, 29). Итого мы имеем ровно 13 хо­ро­ших пар.

Ответ: 13.

По­сколь­ку среди поль­зо­ва­те­лей соц. Сетей ВКон­так­те ис­поль­зу­ют 75%, по­лу­ча­ет­ся, что толь­ко Од­но­класс­ни­ков ис­поль­зу­ет 25%. Кроме того, 65% ис­поль­зу­ют обе сети, зна­чит, всего Од­но­класс­ни­ка­ми поль­зу­ет­ся поль­зо­ва­те­лей соц. Сетей. Эти 90% со­став­ля­ют со­труд­ни­ков фирмы, зна­чит, 100% со­став­ля­ет от всех со­труд­ни­ков. По­это­му те, кто не поль­зу­ют­ся, со­став­ля­ют при­чем их 40 че­ло­век. Сле­до­ва­тель­но, всего со­труд­ни­ков 540.

Ответ: 540.

Пусть в пер­вом ко­шель­ке x пи­аст­ров. Тогда во вто­ром не менее в тре­тьем  — не менее в 10-м не менее Таки об­ра­зом, с одной сто­ро­ны

От­ку­да С дру­гой сто­ро­ны от­ку­да Зна­чит, в пер­вом лежит 9 или 10 пи­аст­ров. Но 9 не может быть, так как тогда в по­след­нем не более 18 и сумма не по­лу­ча­ет­ся 150. Зна­чит, в 1-м 10, во вто­ром  — не менее 11, в 3  — не менее 12, в 4  — не менее 13, в 5 не менее 14 и в 6-м  — не менее 15. Но при 15 сумма по­лу­ча­ет­ся менее 150. Зна­чит, 16. А боль­ше быть не может, так как тогда в по­след­нем ко­шель­ке будет 21.

Ответ: 16.

В пе­ре­се­че­нии каж­дых двух мно­жеств со­дер­жит­ся ровно один эле­мент. Можно до­ка­зать (см. ниже), что в пе­ре­се­че­нии всех 2018 мно­жеств со­дер­жит­ся имен­но этот эле­мент. Тогда сум­мар­ное ко­ли­че­ство эле­мен­тов будет равно

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

Ответ: 88 793.

Най­дем че­ло­ве­ка, у ко­то­ро­го боль­ше всего дру­зей. Пред­по­ло­жим, что их не менее 15 и обо­зна­чим их ко­ли­че­ство как Разо­бьем уча­щих­ся на две груп­пы: в первую вой­дут эти уча­щих­ся. По усло­вию они не могут дру­жить между собой, по­это­му каж­дый из них имеет не более дру­зей. Во вто­рую груп­пу вой­дут остав­ши­е­ся они имеют не более дру­зей каж­дый. Таким об­ра­зом, каж­дая из групп от­пра­вит не более от­кры­ток. Сле­до­ва­тель­но, всего будет от­прав­ле­но не более что не пре­вос­хо­дит 450.

За­ме­тим, что эта ве­ли­чи­на до­сти­жи­ма. Разо­бьем уча­щих­ся на две груп­пы по 15 че­ло­век и пусть каж­дый пред­ста­ви­тель одной из групп дру­жит со всеми пред­ста­ви­те­ля­ми дру­гой груп­пы.

Ответ: 450.

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

Пусть на­шел­ся сту­дент A, у ко­то­ро­го есть трое не­зна­ко­мых B₁, B₂ и B₃. Рас­смот­рим ше­стер­ку сту­ден­тов: A, B₁, B₂, B₃ и еще двоих про­из­воль­ных сту­ден­тов C и D. Их можно рас­се­лить по двум трех­мест­ным ком­на­там, по­это­му A дол­жен ока­зать­ся в одной ком­на­те с C и D и, зна­чит, C и D зна­ко­мы между собой и зна­ко­мы с A. Зна­чит, любые два сту­ден­та, от­лич­ные от B₁, B₂ и B₃, между собой зна­ко­мы. В част­но­сти, если какой-то сту­дент, от­лич­ный от B₁, B₂ и B₃, с кем-то не­зна­ком, то этот кто-то  — один из B₁, B₂ и B₃. Но каж­дый из B_i не зна­ком не более чем с тремя сту­ден­та­ми, по­это­му пар не­зна­ко­мых сту­ден­тов ока­зы­ва­ет­ся не боль­ше де­вя­ти. Зна­чит, в этом слу­чае пар зна­ко­мых сту­ден­тов не мень­ше, чем

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

Ответ: 15 050.

Пусть x, y, z  — ко­ли­че­ство уче­ни­ков в ка­те­го­рии: био­ло­гии, фи­зи­ки, химии. Тогда по усло­вию за­да­чи по­лу­чим си­сте­му урав­не­ний:

Это зна­чит, что ми­ни­маль­ные зна­че­ния могут быть толь­ко:

Ответ: 29.

Remark that group n comprises n consecutive integers; hence the group starts with the number (easy to prove by induction) and ends by because of this, the group starts with 1 977 067 and ends by 1 979 055.

За­ме­тим, что n-ая груп­па со­сто­ит из n по­сле­до­ва­тель­ных на­ту­раль­ных чисел; по­это­му эта груп­па на­чи­на­ет­ся с числа (до­ка­зы­ва­ет­ся по ин­дук­ции) и за­кан­чи­ва­ет­ся чис­лом и, сле­до­ва­тель­но, 1989-ая груп­па на­чи­на­ет­ся с числа 1 977 067, а за­кан­чи­ва­ет­ся чис­лом 1 979 055.

Ответ: на­чи­на­ет­ся с числа 1 977 067, а за­кан­чи­ва­ет­ся чис­лом 1 979 055.

As has been demonstrated in the solution of the problem 4 for the grade, group starts with and ends by hence the sum of this group is In particular,

Из ре­ше­ния за­да­чи 4 для 9 клас­са мы знаем, что n-ая груп­па на­чи­на­ет­ся с числа (до­ка­зы­ва­ет­ся по ин­дук­ции) и за­кан­чи­ва­ет­ся чис­лом и, сле­до­ва­тель­но, сумма этой груп­пы равна По­это­му

Ответ: 3 934 363 329.

The sum of all with odd indexes from 1 до is n⁴. Proof by induction with use of the problem 6691.

Сумма всех групп с не­чет­ны­ми ин­дек­са­ми от 1 до равна n⁴. До­ка­за­тель­ство по ин­дук­ции с ис­поль­зо­ва­ни­ем за­да­чи 6691.

Ответ: n⁴.

Де­ле­ние с остат­ком кучи кон­фет на k детей можно пред­став­лять себе так: мы рас­кла­ды­ва­ем кон­фе­ты на k кучек, ко­то­рые либо оди­на­ко­вы (если оста­ток 0), либо в части кучек кон­фет на 1 боль­ше, чем в осталь­ных (ко­ли­че­ство таких куч равно остат­ку).

Пусть пер­вый ребёнок раз­ло­жит так кон­фе­ты на кучки, рас­по­ло­жив кучи слева на­пра­во по воз­рас­та­нию числа кон­фет в них. Можно счи­тать, что он возьмёт себе пра­вую кучку, если он маль­чик, или левую, если он  — де­воч­ка.

Когда зайдёт сле­ду­ю­щий ребёнок, кон­фе­ты уже будут раз­ло­же­ны на кучки, как если бы он сам делил с остат­ком (ведь и число детей, и число куч умень­ши­лось на 1), и снова маль­чик возьмёт пра­вую кучу, а де­воч­ка  — левую, и т. д. В итоге маль­чи­ки возь­мут все пра­вые кучки в ко­ли­че­стве, рав­ном числу маль­чи­ков, что не за­ви­сит от по­ряд­ка детей в оче­ре­ди.