19.22 Оценка + пример

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

Это мы провели оценку, то есть доказали что больше 21 уголка вырезать точно не получится. Но это нам не гарантирует, что мы сможем врезать 21 уголок, поэтому мы должны привести пример, как можно вырезать 21 уголок из клетчатого квадрата .

Вот пример:
 

Пусть в зале рядов, тогда число стульев в зале равно

– для некоторого натурального . Так как число простое, то один из множителей и должен делиться на .

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

Такой вот кинозал...

Пусть , где – число камней в каждой куче после того, как кучи упорядочили по возрастанию числа камней в них. То есть . Тогда (следует из условия), .
Пусть мы взяли первую кучу и раскладываем из нее камни по остальным кучам так, чтобы количество в них стало одинаковым. Тогда, так как во всех кучах разное количество камней, наилучший исход (наименьшее количество камней в 1-ой куче) для нас будет таким: ничего не класть в 8-ую кучу, положить 1 камень в 7-ую, 2 камня в 6-ую, 3 камня в 5-ую, 4 камня в 4-ую, 5 камней в 3-ю и 6 камней во 2-ую. Следовательно, в первой куче должно быть как минимум камней. То есть . Следовательно, и т.д., .
Утверждаем, что наименьшее возможное количество камней в большой куче – 28. Приведем пример: пусть у нас есть 8 куч камней, в которых 21, 22, 23, 24, 25, 26, 27, 28 камней соответственно.
Разложение 1-ой кучи по остальным мы уже продемонстрировали выше. Аналогично можно проверить, что это условие выполняется для любой другой кучи: после разложения камней в оставшихся семи кучах будет по 28 камней.

Пусть – сумма чисел в -ой строке ( пробегает натуральные значения от до ). Пусть – сумма чисел в -ом столбце ( пробегает натуральные значения от до ). Пусть также – сумма всех чисел таблицы.

Тогда, учитывая тот факт, что слагаемые в сумме можно складывать в любом порядке, получим:

Из последнего равенства получаем следующие оценки:

откуда следует, что существуют и такие, что

Пример для может быть таким: , , все числа в таблице равны :

Минимальное значение, которое может принимать , равно . Тогда количество ям не может быть больше , ведь – пятизначное число.

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

В случае, когда количество ям равно , последняя буква в слове обязательно соответствует цифре , которая у Паши запрещена, следовательно, количество ям не превосходит .

При этом в случае, когда и количество ям равно , получаем: , что подходит по условию.

Таким образом, если Паша правильно решит поставленную задачу, он получит ответ .

Каждый слон простреливает целиком любую диагональ, на которой он находится. Найдём количество попарно параллельных диагоналей на Ваниной доске. Их . Таким образом, количество слонов не может превышать (иначе какие-то два слона оказались бы на одной диагонали и били бы друг друга).

Можно ли расставить слонов так, чтобы условие задачи было выполнено? Заметим, что слон, стоящий на чёрной клетке, ходит только по чёрным клеткам, а слон, стоящий на белой клетке, ходит только по белым клеткам. Если можно расставить слонов, то найдутся не менее слонов, стоящих на клетках одного цвета (пусть для примера это будет чёрный цвет). Но тогда можно поставить и слонов на белые клетки, для этого достаточно вертикально приподнять всех слонов, стоящих на чёрных клетках, затем повернуть под ними доску на (вокруг точки пересечения диагоналей квадратной доски) и опустить слонов.

Если слоны, стоявшие до поворота доски на чёрных клетках, не били друг друга, то и после поворота доски они не будут бить друг друга. При этом слоны, стоящие на чёрных клетках, никак не связаны со слонами, стоящими на белых клетках (“они живут в разных мирах”). Тогда можно поставить на доску не менее чёрных слонов и не менее белых слонов так, что все они не будут бить друг друга, но такого быть не может, следовательно, наше предположение неверно и на такой доске можно расставить не более слонов так, чтобы они не били друг друга.

слонов можно расставить, например, так: ставим слонов в каждую клетку верхней горизонтали, затем в каждую клетку нижней горизонтали, кроме угловых.

а) Если на доске записано 4 числа, оканчивающихся на 1, то их сумма чётна, так как сумма чётного количества нечётных чисел чётна.

Если на доске записано 26 чётных чисел, то их сумма чётна, так как сумма любого количества чётных чисел чётна.

Таким образом, сумма всех 30 чисел также будет чётной. Но число 771 нечётно, значит, ответ на пункт отрицательный.

б) Рассмотрим сумму 30 наименьших натуральных чисел таких, что 13 из них оканчиваются на 1, а остальные 17 — чётные.

По формуле суммы арифметической прогрессии 17 последовательных чётных чисел имеем:

Запишем сумму 13 наименьших оканчивающихся на 1 чисел :

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

в) Пусть на доске записано чисел, оканчивающихся на 1. Тогда на этой же доске записано чётных чисел.

Запишем сумму первых чисел как сумму суммы единиц и наименьших натуральных последовательных чисел, кратных 10:

Запишем сумму первых наименьших натуральных чётных чисел:

Сумма по условию:

Найдём нули левой части через формулу дискриминанта:

По методу интервалов получаем .

Определим положение левой границы отрезка.

Раз , то Тогда:

Так как , то Однако если чётно, то (как показано в пункте а)) мы встречаем противоречие, поэтому на самом деле

Пример для

а) Разобьем шахматную доску на клеток как показано на рисунке
 

 

Так как всего квадратов 16 штук, то минимальное количество закрашенных клеток 16 (так как если мы закрасим всего 15 клеток, то в каком то из 16 квадратов не будет закрашенной клетки).

Это была оценка, то есть доказательство того, что меньше 16 клеток закрасить мы не сможем.

Пример того, как это можно сделать ниже:
 

 

б) Воспользуемся разбиением шахматной доски из пункта а).

Заметим, что если в каком-то из 16 квадратов будет закрашена только 1 клетка, то в этом квадрате обязательно будет уголок из трех клеточек, в котором не будет закрашенной клетки. Поэтому в каждом из 16 квадратов должно быть как минимум 2 закрашенные клетки, то есть всего 32 закрашенные клетки.

Это была оценка, то есть доказательство того, что меньше чем 32 клетки закрасить нам не удастся.

Пример для 32 на рисунке ниже:
 

а) Первый разрез разрезает блин ровно на две части.

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

Третий разрез также может пройти по каждой из имеющихся теперь частей не более, чем один раз. Таким образом, после третьего разреза количество частей не превосходит восьми.

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

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

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

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

б) Решение для частей приведено ниже:
 

По формуле суммы арифметической прогрессии сумма первых последовательных натуральных чисел равна

а) Рассмотрим наименьшую возможную сумму двадцати различных натуральных чисел, не содержащую простых чисел. Она состоит из первых 20 непростых чисел натурального ряда. Наибольшим из таких чисел будет число 30. Действительно, среди чисел от 1 до 30 ровно 10 простых:

Тогда, исключив их, мы получим ровно чисел. Найдем их сумму:

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

б) В пункте а) мы доказали, что наименьшая сумма 20 различных натуральных чисел, не содержащая простых, равна 336. Тогда очевидно, что наименьшая сумма двадцати различных натуральных чисел, содержащих ровно одно простое, получается заменой наибольшего числа из суммы на наименьшее простое, то есть заменой числа 30 на 2:

Снова получили, что наименьшая сумма, удовлетворяющая условию, превосходит 280, значит, такого быть не могло.

в) Из пунктов а) и б) следует, что на доске написано как минимум два простых числа (если меньше — противоречие). Допустим, на доске оказалось написано ровно два простых числа и Тогда сумма на доске не меньше чем где — наименьшая возможная сумма 18 различных натуральных чисел, ни одно из которых не простое. Сумма состоит из первых 18 непростых чисел натурального ряда. Наибольшим из таких чисел будет число 27. Действительно, среди чисел от 1 до 27 ровно 9 простых:

Тогда, исключив их, мы получим ровно чисел. Найдем их сумму:

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

Приведём пример, когда на доске написано три простых числа 3, 7 и 19:

Их сумма равна

а) В гирлянде может быть 20 красных лампочек, например, если среди первых 40 лампочек чередуются синие и красные, а остальные 10 лампочек являются синими.

б) Докажем, что в гирлянде не может быть 41 красная лампочка. Разобьём 50 лампочек на десять подряд идущих групп по 5 лампочек в каждой.

Если бы в каждой группе была как минимум одна синяя лампочка, то всего синих лампочек было бы не менее 10, но если в гирлянде 41 красная лампочка, то синих лампочек всего 9. Значит, найдется группа, в которой нет синих лампочек. Но тогда подряд идет пять красных лампочек, а значит, есть красная лампочка, которая не соседствует с синей.

в) Подсчитаем, какое наименьшее количество синих лампочек должно быть в гирлянде.

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

Также заметим, что лампочки с номерами 49 и 50 не могут оказаться красными одновременно, так как тогда у 50-ой лампочки не будет синей лампочки рядом.

Итак, синих лампочек в гирлянде должно быть не менее 17. Значит, в гирлянде может быть не больше 33 красных лампочек.

По рассуждениям можно построить пример такой гирлянды с 33 красными лампочками. Лампочки с номерами, которые дают остаток 2 при делении на 3, то есть с номерами будут синими, а остальные лампочки — красными.

а) Суммарная масса вещей в килограммах в пакетах у Вани равна

Заметим, что масса каждого пакета кратна 3, следовательно, масса любого числа пакетов также будет кратна 3. Значит, в любой рюкзак поместится число пакетов, суммарная масса которых кратна 3. Тогда суммарная масса в каждом рюкзаке не превосходит не 29 кг, а 27 кг. Но Следовательно, семь таких пакетов разместить не удастся.

б) Суммарная масса вещей в килограммах в пакетах равна

Если рюкзаков 3 и в каждом не более 38 кг, то всего уместится не более кг. Тогда в два рюкзака должно поместиться ровно по 38 кг, а в третий — 37 кг.

Переберем все варианты, какими пакетами можно набрать 37 кг:

1.

кг, тогда остаются пакеты по 6, 14, 15, 19, 22 кг. Пакет в 22 кг должен попасть в один из двух оставшихся рюкзаков, где должно быть суммарно 38 кг, но среди пакетов нет пакета такой массы, который бы в сумме с 22 кг дал 38 кг. Если с пакетом массой 22 кг будет лежать хотя бы два других, то их общая масса будет не меньше кг. Следовательно, в этом случае ничего не получается.

2.

кг. Тогда остаются пакеты по 6, 12, 14, 19, 25 кг. Пакет в 25 кг должен попасть в один из двух оставшихся рюкзаков, где должно быть суммарно 38 кг, но среди пакетов нет пакета такой массы, который бы в сумме с 25 кг дал 38 кг. Если с пакетом массой 25 кг будет лежать хотя бы два других, то их общая масса будет не меньше кг. Следовательно, в этом случае ничего не получается.

3.

кг. Тогда остаются пакеты по 14, 15, 22, 25 кг. Пакет в 25 кг должен попасть в один из двух оставшихся рюкзаков, где должно быть суммарно 38 кг, но суммарная масса пакета в 25 кг и любого другого из оставшихся не меньше кг. Следовательно, в этом случае ничего не получается.

Других вариантов набрать 37 кг пакетами с данными массами нет, значит, Ваня не сможет разложить такие пакеты по трем рюкзакам.

в) Суммарная масса вещей в килограммах в пакетах равна

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

Пакет в 21 кг должен попасть в один из рюкзаков, но среди других пакетов есть только один пакет такой массы, который бы в сумме с 21 кг дал 28 или 29 кг — это пакет массой 7 кг. Тогда пакеты массой в 7 и 21 кг обязаны лежать в одном рюкзаке, значит, остальные рюкзаки должны весить по 29 кг.

Рассмотрим пакет массой 19 кг. Среди оставшихся пакетов нет таких, которые бы в сумме с 19 кг дали бы 29 кг. Следовательно, в этом случае ничего не получается.

Пусть Тогда распределим пакеты по рюкзакам следующим образом: