В худшем случае

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

Есть коробка, в которой лежат какие-то предметы. Вам нужно, не заглядывая в эту коробку, вынуть определённые из них.

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

Задача первая. В непрозрачном мешке лежат 6 зелёных и 2 жёлтых шара. Какое наименьшее количество шаров надо вытащить из мешка, чтобы среди них обязательно оказался хотя бы 1 зелёный шар?

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

Известно, что в непрозрачном мешке 6 зелёных и 2 жёлтых шара. Нам необходимо выяснить, какое наименьшее количество шаров надо вытащить из мешка, чтобы среди них обязательно оказался хотя бы 1 зелёный шар.

Очевидно, что в самом худшем случае мы сначала будем вытаскивать только жёлтые шары. То есть вытащив 2 шара, мы не вытащим ни одного зелёного шара.

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

Конечно же, среди этих трёх шаров могут быть и 2, или даже все 3 зелёных шара, но условию задачи это противоречить не будет.

Таким образом, ответе на вопрос задачи: 3 шара.

Друзья, мы выяснили, что из мешка, в котором лежат 6 зелёных и 2 жёлтых шара, в худшем случае придётся вытащить 3 шара, чтобы среди них оказался хотя бы 1 зелёный шар. А какое наименьшее количество шаров надо вытащить из мешка, чтобы среди них обязательно оказался хотя бы 1 жёлтый шар?

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

Тогда ответ на вопрос данной задачи: 7 шаров.

Задача третья. В непрозрачном мешке лежат 6 зелёных и 2 жёлтых шара. Сколько шаров надо вытащить из мешка, чтобы среди них обязательно оказался хотя бы 1 зелёный и хотя бы один жёлтый?

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

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

Ребята, а если из мешка мы сначала вытащим все жёлтые шары и только потом нам попадётся зелёный шар?

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

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

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

В четвёртой задаче выясним, какое наименьшее количество шаров надо вытащить, чтобы среди них наверняка оказались 2 зелёных и 1 жёлтый.

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

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

В ответе записываем самый худший случай: 7 шаров.

В следующей задаче выясним, какое наименьшее количество шаров надо вытащить, чтобы среди них оказались 2 шара одного цвета?

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

Если достанем зелёный шар, то будет 2 шара зелёного цвета. Если достанем жёлтый шар, то будет 2 шара жёлтого цвета.

Ответ: 3 шара.

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

Итак, в самом худшем случае мы достанем 2 носка, и они будут разных цветов, то есть 1 розовый и 1 фиолетовый. Когда достанем третий носок, то у нас уже будет 2 носка одного цвета.

Если третий носок будет розовым, то получится пара розовых носков. Если третий носок будет фиолетовым, то получится пара фиолетовых носков.

Ответ на вопрос данной задачи: 3 носка.

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

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

Потом возьмём ещё 1 ботинок (семнадцатый), и он обязательно окажется парным одному из 16 ранее взятых.

Ребята, также возможен случай, когда сначала будут взяты по 8 ботинок на разные ноги, то есть 8 ботинок на левую ногу и 8 ботинок на правую ногу, но они будут разных цветов. Но и в этом случае семнадцатый ботинок окажется парным одному из тех 16, которые уже взяты.

Таким образом, в ответе запишем: 17 ботинок.

И решим ещё одну задачу. В непрозрачном мешке 55 шаров: 12 жёлтых, 12 зелёных, 12 красных, 12 синих, остальные серые и чёрные. Шары отличаются друг от друга только цветом. Не заглядывая в мешок выбираем шары. Какое наименьшее количество шаров необходимо взять, чтобы среди них было не менее 7 шаров одного цвета?

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

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

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

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

Друзья, на этом время, отведённое на нашу встречу, заканчивается. Пора прощаться. До свидания. До новых встреч.