« В ХУДШЕМ СЛУЧАЕ»

«В ХУДШЕМ СЛУЧАЕ» - такова формулировка темы 

занятия №4. 

    Довольно часто в задачах, где требуется доказать какое-либо утверждение, 

    можно рассмотреть самый неудобный, худший случай, в котором 

    утверждение кажется наиболее «подозрительным». И если мы докажем 

    утверждение в этом худшем случае, то тем более оно будет верно 

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

    - правильно определить этот худший случай. 

       В последней международной олимпиаде по основам наук (математика) 

       для учащихся 6 класса были целых 2 задачи по нашей теме.

Рассмотрим решения нескольких задач.

     №1. В непрозрачном мешке лежат 5 белых и 2 черных шара.

    а) Какое наименьшее число шаров надо вытащить из мешка, 

    чтобы среди них обязательно оказался хотя бы один белый шар? 

      (Заглядывать в мешок нельзя!)

     Какой случай здесь самый худший? Очевидно, тот, когда мы будем 

    вытаскивать только черные шары. В этом случае, даже вытащив 

    2 шара, мы не вытащим белого шара. Но если мы вытащим 3 шара, 

     то тогда уж точно из трех шаров по крайней мере один шар будет белым.   

     Дополнительный вопрос: какое наименьшее число шаров надо 

     вытащить из мешка, чтобы среди них обязательно оказался   

     хотя бы один черный шар?

    (Подумали сами? Конечно же, ответ в этом случае: 6 шаров.)

    б) Сколько шаров надо вытащить, чтобы среди них обязательно 

    оказался хотя бы один белый и хотя бы один черный?  

     Худшим здесь будет случай, когда мы сначала будем вытаскивать 

    одни белые шары и только потом попадется черный шар. 

    Поэтому потребуется вытащить 5+1=6 шаров. Отметьте, 

    что случай, когда попадаются одни черные шары, «лучше», 

    поскольку уже третий шар окажется белым. Выбор «худшего» 

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

    в) Какое наименьшее число шаров надо вытащить, чтобы 

    среди них наверняка оказались 3 белых и 1 черный шар?  

     В худшем случае мы сначала вытащим все белые шары, и затем 

     лишь пойдут черные. Тогда придется вытащить 5+1=6 шаров. 

    (Убедитесь, что в случае, когда сначала идут черные, а потом  

      белые шары, число вытаскиваемых шаров будет меньше.)

      г) Сколько шаров надо вытащить, чтобы среди них оказались 

       2 шара одного цвета?

      Худший случай – когда сначала попадаются шары разных цветов. 

     Это возможно, если мы вытащим 2 шара. А если вытащим третий,     

    то уже будем иметь 2 шара одного цвета.

 

    №2. На карточках выписаны все двузначные числа. Сколько карточек 

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

      а) на 2; б) на 7; в) на 2 или на 7?

    а) В худшем случае, выбирая не глядя карточки с числами от 10 до 99 

    включительно, мы сначала будем иметь только нечетные числа – их 45, 

    и поэтому 6-е число будет обязательно четным.

          Ответ: 46 карточек.

      б) Среди всех 90 двузначных чисел имеется всего 13 чисел, делящихся 

     на 7 (убедитесь в этом сами). То есть в худшем случае мы возьмем 

     сначала 90-13=77 чисел, 

       не делящихся на 7, но 78-е число уже точно будет делиться на 7.

     Ответ: 78 карточек.

     в) Среди 90 двузначных чисел имеется 13 чисел, кратных 7, и 45 чисел, 

    которые делятся на 2. Но среди этих чисел есть 7 таких (убедитесь в этом сами),      

    которые делятся и на 2, и на 7. Поэтому чисел, делящихся или на 2, или на 7, 

        будет 45+13-7=51. 

        Следовательно, среди 90 двузначных чисел не делятся ни на 2, ни на 7 

     оставшиеся 90 – 51=39 чисел. 

    Нужно взять 39 + 1=40 карточек.

     Ответ: 40 карточек.

      При решении большинства олимпиадных задач высокого уровня 

      используются специальные методы, как правило, не рассматриваемые 

      в школе на уроках. 

     К числу одного из таких методов можно отнести

ПРИНЦИП ДИРИХЛЕ.

(     Дирихле Петер Густав Лежён (1805-1859гг.) – немецкий математик, 

     иностранный член-корреспондент Петербургской АН (1837г.). Основные труды 

     по аналитической теории чисел, теории функций, математической физике.)

    Если 101 зайца рассадить в 100 клеток, то по крайней мере в одной клетке 

    будет 2 зайца. Понятно почему: в худшем случае, если бы в каждой клетке 

     сидело не больше 1 зайца, то в 100 клетках их было бы не больше 100.  

       А если бы было 35 клеток и 743 зайца, то что можно было бы утверждать?

    743:35=21(ост. 8). Значит, в худшем случае, если бы в каждой клетке сидело 

     по 21 зайцу, то еще 8 зайцев резвилось бы на свободе. Следовательно, если

      рассадить в клетки всех зайцев, то по крайней мере в одной клетке будет 

    сидеть не меньше 22 зайцев. Эти подсчеты с зайцами и клетками в 

    действительности связаны с важным математическим утверждением – 

    так называемым принципом ДИРИХЛЕ, точная формулировка 

    которого, конечно, другая.

    Принцип Дирихле выражает соотношение между элементами двух множеств. 

       Существует несколько формулировок этого 

    принципа. Самая популярная следующая: «Если в п клетках сидит   

     т зайцев, причем т >п, то хотя бы в одной клетке сидят по крайней 

   мере, два зайца». ( Подрастёте, поумнеете – рассмотрим ещё 

4 формулировки. Сегодняшнее знакомство – это только начало 

   работы с принципом Дирихле»).         

    Задачка. Плоскость раскрашена в 2 цвета. Можно ли всегда 

   найти 2 точки, расположенные на расстоянии 1 метра друг от друга, 

    окрашенные в одинаковый цвет?

     Решение. Так как цветов – 2, то надо рассмотреть фигуру, в которой       

    точек больше 2. Лучше всего для этого подойдет равносторонний 

    треугольник со стороной 1 метр. У него 3 вершины. Принимая вершины 

    треугольника за «зайцев», а цвета за «клетки», имеем: 3>2. Тогда 

п   о принципу Дирихле найдутся 2 вершины треугольника, 

    расположенные на расстоянии 1 метра друг от друга, окрашенные в один  

    цвет. Что и требовалось доказать.

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

    №1. Есть 3 ключа от трёх дверей с разными замками. Достаточно ли трёх 

    проб, чтобы подобрать ключи к дверям? (В ответе напишите «да» 

     или «нет»). 5 баллов.

     №2. В мешке лежат 10 белых и 10 черных шаров. Они тщательно 

     перемешаны и неразличимы на ощупь. Какое наименьшее число шаров

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

     два шара: 1) одного цвета; 2) разного цвета; 3) белого цвета? 

      (В ответе указать только количество шаров). 15 баллов.

        №3. В ящике комода, который стоит в тёмной комнате, лежат 10 пар 

     коричневых и 10 пар чёрных перчаток одного размера, не скрепленных 

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

     оказалась пара перчаток одного цвета? (В ответе указать только 

     количество перчаток). 10 баллов.

     №4. В классе 26 учащихся. Докажите, что среди них найдутся хотя бы 

     3 учащихся, которые отмечают день рождения в одном месяце. 

     (Приведите очень краткие рассуждения). 10 баллов.

      №5. В классе 29 учащихся. Петя Иванов сделал в диктанте 

      13 ошибок, остальные ученики – меньше. Докажите, что в классе  

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

      (Приведите краткие рассуждения). 10 баллов.

Желаю Вам успешной работы над заданием №4.