занятие 7

Тема: Комбинаторика

Перейдем к следующему циклу комбинаторных задач.

     Задача 17. В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?

     Решение. Капитаном может стать любой из 11 футболистов. После выбора капитана на роль его заместителя могут претендовать 10 оставшихся человек. Таким образом, всего есть 11 • 10 = 110 разных вариантов выбора.

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

     Задача 18.  Сколькими способами можно сделать трехцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя шести различных цветов?

     Решение. Цвет для верхней полоски флага можно выбрать шестью различными способами. После этого для средней полоски флага остаётся пять возможных цветов, а затем для нижней полоски - четыре различных цвета. Таким образом, флаг можно сделать 6 • 5 • 4 = 120 способами.

Задача 19. Сколькими способами можно поставить на шахматную доску белую и черную ладьи так, чтобы они не били друг друга?

Решение. Ладья ходит и бьёт по прямой на любые расстояния и во все стороны при отсутствии препятствий (вправо, влево, вперед, назад, но не по диагонали!). Итак, белую ладью можно поставить на любую из 64 клеток. Независимо от своего расположения она бьет 14 полей, да одно поле, на котором она стоит, остается 64 - 15 = 49 полей, на которые можно поставить черную ладью. Значит, всего есть 64 • 49 = 3136 разных способов.

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

Решение. Король в шахматах может перемещаться в любом направлении по вертикали, горизонтали, диагонали, но только на одно поле. Белого короля можно поставить на любое из 64 полей. Однако количество полей, которые он при этом будет бить, зависит от его расположения.

1) если белый король стоит в углу (их 4), то он бьет 4 поля (включая то, на котором стоит). Остается 60 полей, на которые можно поставить черного короля. В расчете для 4-х углов получаем 4 • 60 = 240 полей.

2) если белый король стоит на краю доски, но не в углу (таких полей - 24), то он бьет 6 полей, и для черного короля остается 58 возможных полей, всего 24 • 58 = 1392 поля.

3) если же белый король стоит не на краю доски (таких полей - 36), то он бьет 9 полей, и для черного короля остается 55 возможных полей, а всего 36 • 55 = 1980 полей.

Таким образом, всего есть 240 + 1392 + 1980 = 3612 способов расстановки королей.

Задачи для самостоятельного решения.

Задача 21. Сколькими способами из полной колоды (52 карты) можно выбрать 4 карты разных мастей и достоинств?

Задача 22. На полке стоят 5 книг. Сколькими способами можно выложить в стопку несколько из них (стопка может состоять и из одной книги)?

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

Задача "не в тему №1". Есть 5 монет, из которых 3 настоящих, одна - фальшивая, которая весит больше настоящей, и одна - фальшивая, которая весит меньше настоящей. За три взвешивания определите обе фальшивые монеты.

Задача "не в тему" №2. Какой вопрос нужно задать аборигену (рыцарю или лжецу), чтобы узнать, живет ли у него дома ручной крокодил?

Ответы и решения

Задача 21. Всего в колоде имеется 4 разных масти по 13 карт. Выбрать первую карту определенной масти существует 13 способов, вторую карту - другой масти и другого достоинства - уже 12 способов, третью карту - 11 способов, четвертую - 10 способов. А всего будет 13 • 12 • 11 • 10 = 17160 способов.

Задача 22. Ответ: 5 + 5 • 4 + 5 • 4 • 3 + 5 • 4 • 3 • 2 + 5 • 4 • 3 • 2 • 1 = 325 способов.

Задача 23. Здесь придется сделать 2 оговорки. 1) Ладьи, независимо от цвета, бьют друг друга по правилу, описанному в задаче; 2) Название шахматного поля не имеет значения.

Решение. Первую ладью можно поставить на одну из горизонталей одним из 8 способов, тогда следующую - на другую горизонталь - одним из 7 способов (так, чтобы она не оказалась с предыдущей на одной вертикали), третью ладью - на свободную горизонталь, избегая двух занятых уже вертикалей - 6 способами и т.д. Таким образом, всего получаем 8! = 40320 способов расстановки ладей.

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

По задачам 21-23 хочу напомнить еще раз, что мы применяем метод умножения, который позволяет предусмотреть все возможные ситуации. Например, если при решении задачи 21 у вас возникает вопрос: а если мы выберем сначала не эту, а другую карту данной масти? При использовании метода умножения мы как раз для каждого из 13 выборов предусматриваем все возможности.

Задача "не в тему" №1. 

Мне понравилось решение Алёны Губаревой, публикую его здесь с небольшими поправками.

Решение. Возьмем две монеты и взвесим их, так же делаем с другими двумя монетами. У нас есть два варианта: 

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

Задача "не в тему" №2. Решение. В таких задачах подбирается вопрос, на который и рыцарь, и лжец дадут одинаковый ответ. Таких вопросов много. Например, "Что бы ты сказал, если бы я у тебя спросил, есть ли у тебя дома ручной крокодил?"       

     

Условие                                            Ответы рыцаря                      Ответы лжеца

Крокодил действительно есть       да (просто правда)             да (двойная ложь)

Крокодила нет                                нет (просто правда)           нет (двойная ложь)

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