Тема Высшая проба

Высшая проба - задания по годам → .01 Высшая проба 2015 и ранее

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела высшая проба

Разделы подтемы Высшая проба - задания по годам

Высшая проба 2015 и ранее

Высшая проба 2016

Высшая проба 2017

Высшая проба 2018

Высшая проба 2019

Высшая проба 2020

Высшая проба 2021

Высшая проба 2022

Высшая проба 2023

Высшая проба 2024

Высшая проба 2025

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#72110

Найдите все натуральные числа $n$ , такие, что число $n2+ 77n$ является точным квадратом натурального числа.

Источники: Высшая проба - 2015, задача 9.6(см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

В уравнениях с целыми числами полезно приводить выражение к виду (что-то)*(что-то)=число, попробуйте сделать что-то в этом духе

Подсказка 2

В условии фигурируют квадраты чисел. Какую ФСУ требуется применить к квадратам чтобы получить разложение на скобки?

Подсказка 3

Выделите полный квадрат с n и распишите разность квадратов.

Подсказка 4

Вы получили уравнение: (2n-2q+77)(2n+2q+77)=77². Осталось перебрать варианты. Как можно упростить перебор?

Подсказка 5

Заметим, что: 2n-2q+77 < 2n+2q+77. Осталось разобрать случаи!

Показать ответ и решение

Решим уравнение $n2+ 77n =q2$ в натуральных числах. Преобразуем левую часть следующим образом:

2 77 772 772- 2 n + 2⋅2 ⋅n+ 4 − 4 = q

Теперь запишем уравнение в виде

77 772 (n +-2 )2− q2 = 4-

Домножим равенство на $4$ и разложим левую часть на множители через разность квадратов:

(2n − 2q+ 77)(2n+ 2q +77)= 772

Осталось перебрать возможные варианты. Для упрощения перебора заметим, что

2n − 2q+ 77< 2n +2q+ 77

Следовательно, для скобочек возможны следующие варианты: $1$ и $2 77 ,$ $7$ и $2 7⋅11,$ $11$ и $2 7 ⋅11,$ $49$ и $121.$ Осталось разобрать каждый случай и написать ответ.

Ответ:

$1444,175,99,4$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#79880

Действительные числа $x,y,z$ выбираются так, что выполняются равенства

xy+ yz+ zx= 4,xyz = 6

Докажите, что при любом таком выборе значение выражения

( 3 )( 3 ) ( 3 ) xy− 2(x+y) yz −2 (y+ z) zx− 2(z+x)

является одним и тем же числом, и найдите это число.

Подсказки к задаче

Подсказка 1

Попробуем преобразовать каждую из скобок по отдельности. Какие слагаемые участвуют в первой скобке? Как их найти из условия?

Подсказка 2

xy = 6/z, x+y = (4-xy)/z. Тогда чему равна первая скобка?

Подсказка 3

Каждую скобку можно записать как 3/2 от частного произведения двух переменных и третьей переменной. Осталось красиво преобразовать две другие скобки. Теперь понятно, как снова применить условие!

Показать ответ и решение

Решение №1

Из условия следует, что $x, y, z$ — ненулевые числа. Из данных равенств получаем

6 4− xy 4 xy xy = z, x+ y =--z--= z − z-

Подставляя это в первую скобку, получаем

3 6 3( 4 xy) 3xy xy −2(x+ y)= z − 2 z −-z = 2z-

Аналогично со второй и третьей скобкой. В итоге данное выражение преобразуется в

3xy-⋅ 3yz-⋅ 3zx-= 27xyz-= 81 2z 2x 2y 8 4

_________________________________________________________________________________________________________________________________________________________________________________

Решение №2

Домножим числитель и знаменатель на $xyz$ и получим

(xy− 3(x+ y))⋅z⋅(yz− 3(y+ z)) ⋅x ⋅(zx− 3(z+x))⋅y -----2--------------2xyz-----------2--------=

( 3 ) ( 3 )( 3 ) = -xyz−-2(xz-+yz)-⋅xyz−-2(xy-+xz)-⋅xyz−-2(yz-+xy) 6

Из условия получаем, что $xz +yz = 4− xy,$ $xy+ xz = 4− yz,$ $yz+ xy =4 − xz.$ Подставляя это в последнее выражение, получаем

(6− 32(4− xy))⋅(6− 32(4 − yz))⋅(xyz− 32(4− xz)) ------------------6-------------------=

( 3 ) ( 3 ) ( 3 ) 3 3 3 = 6-− 6+-2xy-⋅6-− 6+-2yz-⋅-6− 6-+2xz-=-2xy-⋅2yz-⋅2xz= 6 6

= 9-⋅x2y2z2 =-9⋅62 = 81 16 16 4

Ответ:

$81 4$

Ошибка.
Попробуйте повторить позже

Задача 3#67085

В выражении

( 2)( 3) ( 13)( 14)( 1000)18 (1 +x) 1+ x 1+ x ...1 +x 1 +x 1+ x

раскрыли все скобки и привели подобные слагаемые. Сколько слагаемых получилось?

Источники: Высшая проба - 2014, 9.10 (см. www.hse.ru)

Подсказки к задаче

Подсказка 1

Разберёмся отдельно с произведением (1+х)...(1+х^14). Из каждой скобки (1+х^i) мы берём либо 1, либо x^i. Тогда какие степени при раскрытие скобок мы можем получить?

Подсказка 2

Все суммы, где числа от 1 до 14 либо не участвуют, либо участвуют один раз. То есть эти степени лежат в промежутке [0,14+...+1] = [0, 105]. А все ли суммы можно получить из этого диапазона?

Подсказка 3

Оказывается, да... Доказать в общем виде... Хм. Ну не, звучит страшно. А если по порядку? Например, сначала для 0, потом для 1. А потом для остальных?...

Подсказка 4:

Верно! Намёк на индукцию. Придумайте переход самостоятельно (он несложный)). А на что мы ещё не обращали внимания? Мы забыли про скобку (1+x^1000)^18.

Подсказка 5:

По биному Ньютона это сумма x^(1000k), где k = 0,1,2,...,18, со страшными коэффициентами (C-шки). То есть степени из первых 14 скобок это числа из множества А = 0, …, 105 а из последней в 18 степени это числа из множества B = 0, 1000, …, 18000. Тогда какой вывод можно сделать?

Подсказка 6:

Что степени x в итоговом выражении — это всевозможные суммы одного числа из А и другого из B. Дальше остаётся совсем немного (понять, что случаи не пересекаются) Вы справитесь! Успехов!

Показать ответ и решение

Заметим, что в задаче по сути спрашивается, какие степени $x$ мы можем получить, после раскрытия всех скобок. Рассмотрим для начала первые $14$ скобок. Докажем, что после их перемножения появятся степени $x$ от 0 до $1+2 +⋅⋅⋅+ 14= 105.$ Ясно, что $0$ степень, а также $1$ степень мы можем получить. Пусть мы может получить степень $p,$ тогда пусть для получения этой степени мы из скобок взяли степени $n1 < n2 < ⋅⋅⋅< nk.$ Если $p⁄= 105,$ то существует $ni :ni+ 1< ni+1$ или свободная степень $1.$ Тогда мы точно сможем получить $p+1 x .$ Понятно, что степень, большую $105$ получить невозможно. Теперь вспомним про оставшиеся $18$ скобок. Пусть из первых $14$ скобок мы получили $m x ,$ тогда из оставшихся мы можем получить $19$ степеней: $m m+1000 m+2⋅1000 m+18⋅1000 x ,x ,x ...x .$ Так как $105< 1000,$ то для каждой степени, полученной после перемножения первых $14$ скобок, будет порождаться новая серия степенй после перемножения оставшихся скобок. Действительно, каждый показатель из $m m+1000 m+2⋅1000 m+18⋅1000 x ,x ,x ...x .$ дает свой уникальный остаток $l$ при делении на $1000(l≤ 105 <1000).$ Тогда ответ $19⋅106= 2014.$

Ответ:

$2014$

Ошибка.
Попробуйте повторить позже

Задача 4#94021

Пусть $p> 2$ — натуральное число, не делящееся на $3.$ Рассмотрим все целые числа $a,a ,...,a 1 2 k$ из интервала $(− p,p) 22$ такие, что $ai ≡ p (mod 3)$ для всех $i=1,2,3,...,k.$ Докажите, что произведение

p− a1 p− a2 p− ak -|a1|-⋅-|a2|-⋅...⋅-|ak|-

является натуральной степенью тройки.

Подсказки к задаче

Подсказка 1

Рассмотрим, например, p - a₁. Выделим из него максимальную степень тройки. То есть представим в виде p - a₁ = k₁b₁, где k₁ — степень тройки, а b₁ не делится на 3. Если так сделать для всех i, то получится, что нужно разделить произведение степеней тройки и каких-то чисел b₁b₂..., не делящихся на 3, на произведение чисел, не делящихся на 3, |a₁a₂...|. Если доказать, что эти произведения равны, то все получится. Как можно это сделать?

Подсказка 2

Чисел b₁... столько же, сколько чисел a₁... Попробуем доказать, что на самом деле они равны. Для этого сначала исследуем числа |a₁|... Можно ли доказать, что они различны?

Подсказка 3

Верно! Они не равны, поскольку тогда мы бы получили, что какие-то два из них противоположны, что означало бы, что 2p делится на 3, что по условию неверно. А можно ли теперь доказать, что |a₁|... — на самом деле и есть все числа в интервале (0;p/2), не делящиеся на 3.

Подсказка 4

Верно! Если возьмем число t, не делящееся на 3 в промежутке (0;p/2), то либо t, либо -t совпадает с p по модулю 3. А, если вспомнить определение чисел a₁..., то получится, что t или -t с одним из них совпадает. А тогда и получится нужное утверждение. А можно ли теперь и про числа b₁... доказать то же самое?

Подсказка 5

Легко проверить, что все b₁... лежат в интервале (0;p/2). А можно ли теперь проверить, что все они различны?

Подсказка 6

Предположим, что какие-нибудь два из этих чисел совпали и обозначим их e и f, а соответствующие им числа из a₁, ... g и h. Как мы знаем, g и h различны. Тогда что можно сказать о величине (p - g)/(p - h)?

Подсказка 7

Верно! Мы предположили, что e = f, а поскольку g и h различны, можно считать, что p - g > p - h. Тогда это отношение не меньше трех. С другой стороны, поскольку g и h — числа из промежутка (-p/2;p/2) получаем, что это отношение строго меньше трех. Тогда все числа b₁... различны. Как теперь доказать, что эти числа являются ровно теми числами, которые не делятся на 3 из промежутка (0; p/2)?

Подсказка 8

Возьмем некоторое t, не делящееся на 3, из промежутка (0;p/2). Тогда можно указать такую степень тройки k, что p - kt тоже число из промежутка (0;p/2), при этом p - kt имеет тот же остаток, что и p при делении на 3. Какой вывод можно сделать?

Подсказка 9

Верно! Тогда p - kt является одним из чисел a₁... Тогда и t является одним из чисел b₁. Как теперь доказать, что значение искомого выражения является степенью тройки?

Показать доказательство

Ясно, что все $|a | i$ принадлежат интервалу $(0,p) 2$ и различны, поскольку если $a = −a , i j$ то $a +a = 0, i j$ откуда $2p ≡0 (mod 3),$ что неверно по условию задачи.

Еще заметим, что каждое число, не делящееся на $3,$ из интервала $p (0,2)$ совпадает с одним из $|ai|.$ Действительно, пусть $p t∈ (0,2)$ и $t$ не делится на $3.$ Тогда либо $t≡ p (mod 3),$ либо $− t≡ p (mod 3).$ Тогда одно из чисел $± t$ совпадает с $ai,$ откуда получаем, поскольку $t> 0$ , что $t= |ai|.$ Тогда получаем, что множество всех $|ai|$ совпадает с множеством всех чисел из интервала $p (0;2),$ не делящихся на $3.$

Пусть $c 3 i$ — максимальная степень тройки, делящая $(p− ai).$ Поскольку $p ≡ai (mod 3),$ имеем $ci > 0.$ Пусть $c p− ai = 3ibi,$ где $bi$ не делится на $3.$ Заметим, что все $bi$ лежат в интервале $p (0,2),$ поскольку $p p − 2 < ai < 2$ и, следовательно $p−ai p 0< -3ci-< 2.$ Докажем, что все $bi$ различные. Предположим противное: $bi = bj$ для некоторых $i,j.$ Мы знаем, что $p− ai ⁄= p− aj,$ поэтому $ci ⁄= cj.$ Пусть $ci >cj$ Тогда

ci pp−− aai-= 33cjbbi≥ 3 j j

С другой стороны,

p−-ai< 3p∕2-< 3 p− aj p∕2

Таким образом, мы получаем противоречие, и $bi ⁄= bj$ для всех $i,j.$ Докажем теперь, что любое число, не делящееся на $3$ из интервала $p (0,2)$ совпадает с одним из $bi.$ Действительно, пусть $p t∈ (0,2),$ $3⁄|p.$ Тогда существует такое $c,$ что $c p 3p t⋅3 ∈(2,2 ),$ следовательно, $c p p p− t⋅3 ∈(−2,2)$ и при этом $c p− t⋅3 ≡p (mod 3).$ Тогда $c p− t⋅3 = ai$ при некотором $i.$ Но тогда $c p − t⋅3 = ai,$ откуда $t= bi.$

Итак, множество всех чисел $bi$ совпадает с множеством всех чисел, не делящихся на $3$ в интервале $p (0,2),$ поэтому совпадает с множеством $|ai|.$

Тогда имеем

c1+c2+...+ck p− a1-⋅ p− a2-⋅...⋅ p−-ak-= 3-----⋅b1b2...bk= 3c1+c2+...+ck |a1| |a2| |ak| |a1||a2|...|ak|

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

Ошибка.
Попробуйте повторить позже

Задача 5#70311

В остроугольном треугольнике $ABC$ проведены высоты $AA ,BB ,CC 1 1 1$ . На стороне $AB$ выбрана точка $P$ так, что окружность, описанная около треугольника $PA1B1$ , касается стороны $AB$ . Найдите $PC1$ , если $PA = 30$ и $P B = 10$ .

Подсказки к задаче

Подсказка 1

Становится ясно, что нам придётся считать отрезки. По условию нам даны отрезки касательных, тогда какой прямой нам не хватает, чтобы воспользоваться известным равенством для окружности?

Подсказка 2

Нам необходима секущая! Давайте проведем ее через известные точки и начнём считать.

Подсказка 3

Проведите A₁B₁ до пересечения с AB в точке K и обозначьте KB = x. Что можно сказать про A₁B₁AB?

Подсказка 4

A₁B₁AB лежат на одной окружности, так что для них тоже можно воспользоваться равенством произведения отрезков секущих!

Подсказка 5

KA₁* KB₁ = KA * KB. KP² = KA₁* KB₁. Отсюда мы можем выразить x! Но ведь нам нужно было найти PC₁…было бы очень полезно найти еще одну окружность, в которой PC₁ был бы частью отрезка секущей.

Подсказка 6

Обратите внимание на окружность, проходящую через середины сторон и основания высот!

Показать ответ и решение

$PIC$

Продлим отрезки $AB$ и $B1A1$ до пересечения в точке $K$ и обозначим длину $KB = x$ .

Так как произведения отрезков секущих, проведенных из одной точки, равны: $KA1 ⋅KB1 = KA ⋅KB.$ А также квадрат отрезка касательной равен произведению отрезков секущей, проведенной из той же точки, поэтому $KP 2 = KA1 ⋅KB1.$ Следовательно $KP 2 = KA ⋅KB$ . Выразив эти отрезки через $x$ получим $x= 5$ и $KP = 15$ .

Отметим $M$ — середину стороны $BA$ . Основания высот $A1, B1, C1$ и точка $M$ лежат на одной окружности(Окружность девяти точек). Тогда $KC1⋅KM = KA1⋅KB1$ по свойству отрезков секущих, проведенных из одной точки $K$ .

А также имеем $KP 2 = KA1 ⋅KB1$ . И так как $KP = 15, KM =25$ , получаем $KC1⋅25= 225 =⇒ KC1 = 9 =⇒ PC1 = 6.$

Ответ: 6

Ошибка.
Попробуйте повторить позже

Задача 6#80164

В классе $12$ учеников. Их нужно разбить на две группы (первую и вторую), состоящие из чётного числа учеников. Сколькими способами это можно сделать?

Подсказки к задаче

Подсказка 1

Во-первых, в условии сделан акцент на то, что группы имеют номера, то есть порядок групп нам важен. Начнём с малого. Как посчитать количество способов выбрать в первую группу двух учеников, а во вторую 10?

Подсказка 2

Заметим, что выбрав двух в первую группу, 10 во вторую определяются однозначно. Значит нужно просто посчитать количество способов выбрать 2 учеников из 12. Как это сделать?

Подсказка 3

Верно, с помощью числа сочетаний. То есть этих способов ровно C из 12 по 2. Теперь, по аналогии, осталось посчитать сколько способов выбрать 4 из 12, 6 из 12, 8 из 12 и 10 из 12.

Подсказка 4

Делаем это также с помощью числа сочетаний!

Показать ответ и решение

Если в первой группе $2x$ человек, $x∈ [1;5],$ то количество способов разбиения учеников в этом случае равно $C2x 12$ (выбрали $2x$ человек в одну группу, остальных — во вторую). Значит, чтобы получить ответ, нужно просуммировать полученную цешку при $x ∈[1;5]:$

2 4 6 8 10 2 4 6 C12+ C12+C12+ C12+ C12 = 2(C12+ C12)+ C12 = 2046

Ответ:

$C2 + C4 +C6 +C8 + C10= 2046 12 12 12 12 12$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#64855

Найдите все пары взаимно простых натуральных чисел $a$ и $b$ такие, что $2a2 +3b2$ делится на $2a+3b.$

Подсказки к задаче

Подсказка 1

Пусть m = 2а+3b. Тогда отсюда выражается, например, 2а, которое при возведении в квадрат превращается в 4а^2. А у нас в изначальном выражении есть 2а^2, значит таким образом мы сможем узнать что-то о соотношении b и m. Аналогично узнаем про число а и m.

Подсказка 2

Верно, и 15b^2 кратно m, и 10a^2. Используя понимание взаимной простоты чисел а и b мы должны осознать, какие простые делители есть у m.

Подсказка 3

Могут ли простые делители числа m входить в него больше, чем в первой степени? Получив ответ на этот вопрос, мы найдем единственно возможные варианты числа m = 2а+3b и проверим их, помня, что работаем с натуральными числами.

Показать ответ и решение

Заметим, что $4a2− 9b2 = (2a+ 3b)(2a − 3b) ≡ 0, 2a+3b$ отсюда $4a2 − 9b2− 2(2a2+3b2)=− 15b2 ≡ 0 2a+3b$ и $4a2− 9b2+ 3(2a2+ 3b2)= 10a2 ≡ 0. 2a+3b$ Пусть $2a+ 3b$ содержит некоторый делитель $d,$ который взаимно прост с $10$ и $15$ — тогда на это число должны делиться $a2$ и $b2,$ что невозможно, поскольку $(a2,b2)= 1.$ Отсюда $2a +3b$ делится только на $2,3,5$ (из простых чисел). Если какое-то простое число $p$ входит в него большей степени $q > 1,$ то $pq−1$ делит $a2$ и $b2,$ значит, степень каждого простого не больше первой. То есть $2a+ 3b$ может принимать значения $1,2,3,5,6,10,15,30.$ Первые три невозможны, пятёрка даёт нам $a= b= 1,$ что подходит. Пятый случай также невозможен, в шестом $a =b =2,$ условие взаимной простоты не выполнено. Для $15$ есть случаи $a =b =3$ и $a= 6,b= 1,$ нам подойдёт только второй. Для $30$ получаем $(3,8),(6,6),(9,4)$ — подойдут первый и третий случаи. Остаётся выписать ответ.

Ответ:

$(1,1),(6,1),(3,8),(9,4)$

Ошибка.
Попробуйте повторить позже

Задача 8#89286

Найдите все пары взаимно простых натуральных чисел $a$ и $b$ такие, что $a2+3b2$ делится на $a+ 3b$ .

Подсказки к задаче

Подсказка 1

Давайте найдём какое-нибудь выражение, которое точно делится на (a + 3b) и может быть нам полезно в данной задаче. Нам отлично подойдёт a² + 3ab. И правда! Выражение a² + 3b² - a² - 3ab легко сворачивается в 3b(b - a), а также оно должно делиться на (a + 3b).

Подсказка 2

С помощью алгоритма Евклида легко доказать, что (b, a+3b) = 1 ≥ 3*(b - a) делится на (a + 3b). Теперь необходимо сравнить между собой a и b и рассмотреть разные случаи

Подсказка 3

Если a = b, то с учётом взаимной простоты двух чисел, этот случай очевиден. Если же b > a, то решений также не будет по понятным причинам. Остаётся единственный содержательный случай — a > b.

Показать ответ и решение

Заметим, что $a2+3ab$ делится на $a+ 3b$ тогда

2 2 2 3b(b− a)= a +3b − a − 3ab

(добавили и вычли $a2$ ) делится на $a+ 3b,$ так как $(b,a)= 1,$ тогда $(b,a+3b)= 1,$ то есть $3(b− a)$ делится на $a+ 3b.$

Если $b> a,$ то

3(b− a)<3b< 3b+a

при этом они все больше $0,$ откуда следует противоречие.

Если $b= a,$ то это может быть только при $a= b= 1$ иначе $(a,b) >1.$

Если $a> b,$ то так как $3(a− b)$ делится на $a+ 3b,$ то $3(a− b)= k⋅(a+ 3b),$ где $k≤ 2,$ иначе будет противоречие.

Разберем $2$ случая.

(a) Если $k= 1,$ тогда $2a =6b,$ то есть $a= 3b.$ Если $b⁄=1,$ то возникает противоречие с взаимной простотой, значит, $a =3,b= 1.$

(b) Если $k= 2,$ тогда $a= 9b.$ Если $b⁄= 1,$ то возникает противоречие с взаимной простотой, значит, $a= 9,b= 1.$

Итого получили следующие пары ${a,b} :{1,1},{3,1},{9,1}$

Ответ: {1,1}, {3,1}, {9,1}

Ошибка.
Попробуйте повторить позже

Задача 9#105212

Класс из $20$ учеников разделён на две половины так, что каждый школьник из первой половины дружит ровно с шестью одноклассниками, а каждый школьник из второй половины дружит ровно с четырьмя одноклассниками. Найдите число таких различных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся.

Подсказки к задаче

Подсказка 1

Давайте попробуем посчитать количество троек, которые нам не подходят! Что можно сказать о людях в них?

Подсказка 2

В неподходящих тройках ровно 2 человек, которые дружат с ровно 1 человеков из тройки. А можем ли мы посчитать, сколько таких особых учеников во всех тройках в сумме (для разных троек особые ученики могут повторяться)?

Подсказка 3

Если мы возьмём конкретного ученика, то как "собрать" для него тройку, в который он — особый?

Подсказка 4

Нужно взять ровно 1 человека из не знакомых с ним и одного знакомого! Тогда несложно посчитать, сколько же всего у нас особых учеников ;)

Показать ответ и решение

Общее число троек учеников равно $C3 = 1140. 20$ Вычислим все неподходящие тройки, то есть такие, в которых не все три ученика дружат друг с другом, но какие-то двое обязательно дружат. Пусть $(a,b,c)$ — такая неподходящая тройка, тогда в ней есть ровно два особых ученика, каждый из которых дружит ровно с одним из оставшихся. Значит, посчитав количество особых учеников во всех тройках и разделив на два, мы получим количество неподходящих троек.

Если ученик из первой половины класса, то он будет особым в $(20− 6− 1)⋅6 =78$ тройках, если он из второй половины, то он будет особым в $(20− 4− 1)⋅4= 60$ тройках. Значит, количество особых учеников в тройках равно $78⋅10+60⋅10= 1380,$ а количество подходящих троек равно $1140− 1380∕2= 450.$

Ответ:

450

Ошибка.
Попробуйте повторить позже

Задача 10#69409

Во время матча “ЦСКА” - “Реал” пришедший с шахматного кружка Незнайка задумался: при каком наибольшем $n$ на шахматное поле $8× 8$ можно поставить $n$ коней, $n$ королей и $1$ футбольный мяч (занимает одну клетку, но бить не умеет) так, чтобы не было фигуры, стоящей под боем другой фигуры? Помогите ему решить эту задачу.

Источники: Высшая проба - 2007, 11.6

Подсказки к задаче

Подсказка 1

В задачах на ходы необычных фигур полезно бывает выделить области, в которых мы точно сможем оценить количество фигур. Какие несложные фигуры для разбиения можно выбрать?

Подсказка 2

На квадраты 2*2! Сколько королей и коней можно поставить в каждую из них? Квадраты с королями рассмотреть несложно, а о расположении коней нужно подумать. Какое их взаимное расположение внутри квадрата допустимо?

Подсказка 3

Заметим, что кони и короли стоят в разных квадратах, а случай двух коней у границы отданного квадрата требует отдельного рассмотрения. Осталось лишь точно оценить количество коней в квадратах и построить пример!

Показать ответ и решение

Предположим, что на поле можно разместить фигуры при $n≥ 12$ , тогда можно разместить и при $n= 12$ . Разобьём поле на 16 квадратов $2× 2$ , тогда ровно в 12 из них будут стоять по 1 королю («к»), а в 4 других - 12 коней-лошадей («л») и 1 мяч, т.е. 13 фигур, значит, пустых квадратов быть не должно. Соответственно, квадраты будем называть к-квадраты и л-квадраты. Заметим, что если хотя бы в одном из л-квадратов две «л» стоят у общей стороны с другим квадратом, то этот соседний квадрат не будет содержать «к», значит, он должен быть л-квадратом, но тогда в сумме в этих двух квадратах разместится не более 4 фигур, т.к. клетки прямоугольника $2× 4$ разбиваются на пары в виде хода «л», а во всех 4 л-квадратах разместится не более $4+ 2⋅4= 12$ фигур, а должно быть 13. Кроме того, не существует л-квадратов с 4 «л» (аналогичные рассуждения). Значит, в каждом л-квадрате будет ровно 3 «л» и никакие 2 «л» не могут стоять парой у общей стороны с другим квадратом, следовательно, такие л-квадраты находятся в углах поля $8 ×8$ и 3 «л» стоят с краю всего поля, причём в одном из них ещё стоит и мяч.