Какое наибольшее количество не бьющих друг друга королей можно поставить на шахматную доску

Обновлено: 28.04.2024

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

Решение. Чашку можно выбрать пятью способами. Для каждого способа выбрать чашку есть 3 способа выбрать блюдце, потому что выбор блюдца не зависит от выбора чашки. То есть, всего 5 · 3 = 15 способов.

2. В магазине продаются чашки пяти видов, блюдца трех видов и ложки четырех видов. Сколькими способами можно выбрать себе а) чашку, блюдце и ложку; б) два разных предмета?

3. Сколько существует четырехзначных чисел, в записи которых встречаются а) только четные цифры; б) по меньшей мере одна четная цифра?

Указание. а) Сколько цифр чётны? На каждом из 4 мест в числе может быть любая из этих цифр (кроме как на первом месте в числе не может стоять 0).
б) Проще посчитать количество всех четырёхзначных чисел и количество чисел, не удовлетворяющих условию задачи.

Решение. а) 4 · 5 · 5 · 5 = 2 · 5 · 2 · 5 · 5 = 10 · 10 · 5 = 500
б) Четырёхзначных чисел всего 9999 - 1000 + 1 = 9000. Числа, не удовлетворяющие условию задачи, состоят только из нечётных цифр, то есть на каждом из 4 мест в числе должна стоять одна из 5 нечётных цифр (1, 3, 5, 7, 9). Выбрать первую цифру можно 5 способами, для каждого из которых есть по 5 способов выбрать вторую цифру, для каждого из которых есть по 5 способов выбрать третью цифру и по 5 способов выбрать четвёртую цифру, то есть всего 5 · 5 · 5 · 5 = 125 · 5 = (100 + 25) · 5 = 100 · 5 + 25 · 5 = 500 + 125 = 625 способов.

4. Монету бросают трижды. Сколько различных последовательностей орлов и решек может при этом получиться?

Решение. При каждом бросании может быть 2 варианта. То есть, при первом бросании 2 случая, на каждый из них по 2 подслучая (всего 2 · 2 = 4 подслучая), на каждый из подслучаев ещё по 2 подподслучая. Всего будет 2·2·2 = 8 вариантов.

5. Каждую клетку квадратной таблицы 2x2 покрасили в черный или белый цвет. Сколько существует различных раскрасок этой таблицы?

Решение. В каждой из 2х2 = 4 клеток может быть 2 варианта раскраски. То есть, есть 2 варианта раскраски первой клетки, на каждый из них есть по 2 подварианта раскраски второй клетки, на каждый из них по 2 подварианта для третьей и так же для четвёртой клетки. Всего 2·2·2·2 = 16 вариантов.

6. Алфавит племени Мумбо-Юмбо состоит из букв А и У. Словом считается любая последовательность, состоящая не более, чем из 5 букв. Сколько слов в словаре Мумбо-Юмбо?

7. В футбольной команде 11 человек. Сколькими способами можно выбрать а) капитана и заместителя; б) двоих нападающих?

Указание. В пункте а) есть разница в порядке выбора, а в пункте б) — нет. (См. задачи из дополнительного листка)

8. Сколькими способами можно поставить на шахматную доску а) черную и белую ладьи; б) черного и белого королей так, чтобы они не били друг друга? (Ладьи бьют все клетки на своей горизонтали и на своей вертикали, а короли бьют все соседние со своей клетки, в том числе по диагонали.)

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

Указание 2. В пункте б) рассмотрите 3 разных случая в зависимости от количества клеток, на которые можно поставить второго короля.

а) Поставим сначала чёрную ладью. Это можно сделать 8 · 8 = 64 способами. Чтобы белая ладья её не била, надо поставить её в другие горизонталь и вертикаль, то есть свободных для неё горизонталей будет 8 - 1 = 7, и вертикалей тоже 8 - 1 = 7. То есть, поставить белую ладью при уже поставленной чёрной можно 7 · 7 = 49 способами. Так как на каждый из 64 способов поставить чёрную ладью будет 49 способов поставить белую, то всего способов поставить обе будет 64 · 49 = 3136.

б) Поставим сначала чёрного короля. Сколько способов тогда останется для постановки белого? Рассмотрим разные случаи:

Если чёрный король стоит в углу доски, то белого нельзя ставить на 4 клетки, то есть можно поставить на одну из 8·8 - 4 = 60 клеток. Углов в доске 4, то есть таких случаев, когда чёрный король стоит в углу, а белый его не бьёт, 4 · 60 = 240.

Дальше, если чёрный король стоит с краю доски (не в углу), то белого нельзя ставить на 6 клеток, то есть можно ставить на 64 - 6 = 58 клеток. На каждой из 4 сторон доски есть 8 - 2 = 6 клеток, где чёрный король будет стоять с краю, но не в углу, то есть всего таких вариантов растановки обоих королей будет 4 · 6 · 58 = 1392.

Наконец, если чёрный король стоит на внутренней клетке доски (они образуют квадрат со стороной 8 - 2 = 6, поэтому внутренних клеток будет 6 · 6 = 36), то белого можно поставить на одну из 64 - 9 = 55 клеток. Всего вариантов расстановки, где чёрный король стоит на внутренней клетке, будет 36 · 55 = 1980.

Итак, всего подходящих вариантов будет 240 + 1392 + 1980 = (200 + 40) + (1400 - 8) + (2000 - 20) = 1600 + 2000 + (40 - 20 - 8) = 3600 + 12 = 3612

10. Сколько существует пятизначных чисел, в записи которых встречаются только нечетные цифры, причем каждая цифра встречается ровно один раз?

Решение. Нечётных цифр всего пять: 1, 3, 5, 7, 9. На первом месте может стоять одна из 5 цифр, на втором — любая из пяти, кроме первой, то есть любая из 4 цифр, на третьем — любая из пяти, кроме двух уже использованных, то есть любая из 3 цифр, и так далее. Значит, всего 5 · 4 · 3 · 2 · 1 = 5! = 120 таких чисел.

11. Каких семизначных чисел больше — тех, в записи которых есть цифра 1, или тех, в записи которых ее нет?

Указание. Количество чисел с 1 можно не искать: легче найти количество чисел, где нет 1: они просто состоят из остальных цифр, и сравнить его с половиной от количества всех семизначных чисел. Не забудьте, что число не может начинаться с цифры 0.

Задания Д19 C7 № 508207

А) Какое наибольшее число ладей можно поставить на шахматную доску так, чтобы никакие две не били друг друга?

Б) Какое наибольшее число королей можно поставить на шахматную доску так, чтобы никакие два не били друг друга?

В) Какое наименьшее число королей нужно поставить на шахматную доску так, чтобы все свободные клетки оказались под боем?

Г) Какое наибольшее число ферзей можно поставить на шахматную доску так, чтобы никакие два не били друг друга?

а) Ясно, что в каждой строке можно поставить не более одной ладьи. Поэтому ладей не более восьми. Можно, например, поставить их в каждую клетку главной диагонали. Тогда их ровно 8 и никакие две не бьют друг друга.

б) Разобьем доску на 16 квадратов 2 на 2. Ясно, что каждый такой квадрат может содержать не более одного короля. Значит, всего можно разместить не более 16 королей. Пример годится, например, такой: ставим по королю в левый нижний угол каждого из квадратов 2 на 2.

в) Расширим шахматную доску до размеров 9Х9, добавив мысленно вертикаль справа и горизонталь сверху. Разобьем полученную доску на 9 квадратов 3Х3. Поставим в центр каждого из квадратов по королю. Тогда все клетки доски 9Х9, а значит, и исходной доски оказались под боем. Видно, что эти 9 королей попали и на исходную доску, поэтому 9 королей хватит.

Докажем, что 8 королей не хватит. Рассмотрим первые две горизонтали. На них должно располагаться не менее трех королей (иначе какие-то поля первой горизонтали не будут биты). Рассмотрим седьмую и восьмую горизонтали. Аналогично на них должно стоять не менее трех королей. Теперь рассмотрим 4 и 5 горизонтали. На них должно стоять тоже не менее трех королей, иначе не будут биты, например, все поля на 4й горизонтали. Таким образом, королей должно быть не менее 9.

г) Ясно, что в каждой строке можно поставить не более одного ферзя. Поэтому ферзей не более восьми.

Приведем пример: поставим ферзей в клетки

Ответ: а) 8; б) 16; в) 9; г) 8.

— обоснованное решение п. б;

— обоснование в п. в того, что S может принимать все целые значения (отличные от −1 и 1);

Задания Д19 C7 № 508207

А) Какое наибольшее число ладей можно поставить на шахматную доску так, чтобы никакие две не били друг друга?

г) Ясно, что в каждой строке можно поставить не более одного ферзя. Поэтому ферзей не более восьми.

Приведем пример: поставим ферзей в клетки

Ответ: а) 8; б) 16; в) 9; г) 8.

— обоснованное решение п. б;

— обоснование в п. в того, что S может принимать все целые значения (отличные от −1 и 1);

Необходимое условие — закуток Принцип
Постановка задачи. Учитывая шахматную доску 8 × 8, определите максимальное количество королей, которое можно разместить на шахматной доске, чтобы никакие два короля не атаковали друг друга, то есть ни один из королей не находился под контролем. Король может двигаться только на один шаг за раз в любом направлении на шахматной доске (по горизонтали, вертикали и диагонали).

Пояснение —
Согласно принципу Pigeonhole, если у нас n + 1 голубей и у нас n отверстий (или, скорее, клеток), то у нас должно быть одно отверстие (или клетка) с более чем одним голубем.

Например, если у меня было 6 шаров и 5 коробок. Я положил все шары в коробках (любая коробка может иметь любое количество шариков). Тогда принцип «голубиных отверстий» гласит, что независимо от того, как вы поместите шары в коробки, всегда будет хотя бы одна коробка, в которой будет более одного шара. Это очень интуитивный принцип в математике, но проблемы, связанные с этим принципом, так трудно понять.

Итак, вот шахматная доска. Эта проблема имеет какое-либо отношение к принципу «голубиных отверстий»?

Рисунок — шахматная доска 8 × 8

Ответ на эту проблему 16. Но как мы можем прийти к этому решению. В этой загадке следует отметить, что всякий раз, когда у нас есть два короля в квадрате 2 × 2, они всегда проверяются:

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

Мы можем представить квадрат 2 × 2 как отверстие (клетку) для нашего голубя, т.е. королей. Таким образом, площадь 2 × 2 занимает 4 кв. Единицы площади. Общая площадь квадратной шахматной доски составляет 64 квадратных единицы (при условии, что размер шахматной доски составляет 8 единиц × 8 единиц). Итак, у нас есть 64/4 = 16 клеток или ям в этом сценарии.

Мы можем легко разместить по одному королю на этих больших площадях 2 × 2. После завершения 16 королей у нас всегда будет сценарий, в котором два короля располагаются в квадрате 2 × 2 (по принципу голубиных отверстий). Это нарушает наше начальное условие и, следовательно, мы можем иметь максимум 16 королей, которые удовлетворяют вышеуказанному условию.

Рисунок — Возможное решение

Рисунок — еще одно возможное решение

Обобщенная формула —
Даже для квадрата × n размер клетки (квадрат 2 × 2) остается неизменным, и мы можем легко сказать, что когда вы превысите число возможных клеток, у вас обязательно будет два короля в квадрате 2 × 2. Следовательно, максимальное количество клеток определяется как:

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

1. Шахматный конь стоит в левом нижнем углу доски. Может ли он через а) 4; б) 5; в) 1803 хода вернуться на исходное поле?

Решение. в) Нет, так как при каждом ходе конь меняет цвет поля, значит, после нечётного числа ходов он может оказаться только на поле противоположного цвета.

2. Из шахматной доски вырезали две противоположные угловые клетки. Можно ли разрезать оставшуюся часть на доминошки? 3. В каждой клетке треугольной доски размером 7 × 7 × 7 сидит жук. В один прекрасный момент каждый жук переполз на соседнюю по стороне клетку.
а) Докажите, что хотя бы одна клетка оказалась при этом свободной.
б) Какое наименьшее число клеток могло оказаться свободными?
в) Задача-конкурс. Придумайте такое «переползание» жуков, чтобы как можно больше клеток оказались пустыми.

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

4. Можно ли разрезать шахматную доску на доминошки так, чтобы никакие две доминошки не образовали квадрат 2 × 2?

5. Какое наибольшее число а) ладей; б) королей можно расставить на шахматной доске, чтобы они не били друг друга?

Решение. а) Так как в каждом столбце может стоять не больше одной ладьи, то ладей не может быть больше восьми. Восемь ладей можно поставить, например, на одну из диагоналей.
б) Разобьём доску на 16 квадратиков 2 × 2. Тогда в каждом из них может стоять не больше одного короля. Значит, всего на доске не может быть больше 16 королей. 16 королей можно поставить, например, в левых верхних углах таких квадратиков.

6. На каждом поле доски 11× 11 стоит шашка. Настя и Лена играют в такую игру. За один ход можно убрать одну шашку или любую «полоску» из шашек (несколько шашек, расположенных подряд без пропусков в столбце или строке). Проигрывает тот, кто не может сделать ход. Может ли одна из девочек ходить так, чтобы всегда выигрывать, как бы ни старалась её победить соперница? 7. Можно ли разрезать шахматную доску на 15 вертикальных и 17 горизонтальных доминошек?

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

Читайте также: