30
КВАНТ 2017/№1
Птичка вылетает!
РАССМОТРИМ НЕСКОЛЬКО ЗАДАЧ, предлагавшихся на кружках Малого мехмата для 6 класса. В каждой задаче для обоснования ответа нужно привести пример, удовлетворяющий условию, и доказать, что этот пример нельзя улучшить. Задача 1. В фотоателье залетели 50 птиц – 18 скворцов, 17 трясогузок и 15 дятлов. Каждый раз, как только фотограф щелкнет затвором фотоаппарата, какая-то одна из птичек улетит (насовсем). Какое наибольшее число кадров сможет сделать фотограф, чтобы быть уверенным: у него в ателье останутся птицы всех трех видов? Эта задача простая: если фотограф сделает 15 кадров, то может случиться, что улетят все дятлы и останутся только скворцы и трясогузки. Если же кадров всего 14, то птиц любого вида не может улететь больше 14 – значит, хотя бы по одной останется. Ответ: 14. Мы здесь решили двойственную задачу: какого наименьшего количества кадров достаточно птицам, чтобы «обыграть» фотографа (сделать так, чтобы его условие не выполнялось). Если кадров хотя бы 15, то у коварных птиц есть «стратегия» (улетают вседятлы), если 14 или меньше – стратегии нет. Взглянем с этой точки зрения на более сложную задачу. Задача 2. В фотоателье залетели 50 птиц – 18 скворцов, 17 трясогузок и 15 дятлов. Каждый раз, как только фотограф щелкнет затвором фотоаппарата, какая-то одна из птичек улетит (насовсем). Какое наибольшее число кадров сможет сделать фотограф, чтобы быть уверенным: в ате-
лье останется не меньше 10 птиц какого-то одного вида? Птицам здесь нужно сделать численность каждого вида меньше 10. Для этого должны улететь хотя бы 9 скворцов, хотя бы 8 трясогузок и хотя бы 6 дятлов – всего не менее 23 птиц. Значит, если кадров 22, то стратегии нет, и фотограф может быть уверен, что его условие не нарушится. Если же кадров хотя бы 23, то уверенности уже нет. Ответ: 22. И, наконец, еще одна вариация. Задача 3. В тех же условиях определите, какое наибольшее число кадров может сделать фотограф, чтобы быть уверенным: в ателье останется не меньше 11 птиц какого-то одного вида и не меньше 10 – какогото другого. Здесь фотограф «гонится за двумя зайцами» (хочет, чтобы сразу выполнялись два условия), и птицам, чтобы обыграть его, достаточно «убить» хотя бы одного из них. Переводя с заячьего языка на птичий – либо сделать так, чтобы птиц каждого вида было не больше 10, либо разрешить, чтобы птиц какого-то вида было сколько угодно, но тогда каждого из остальных видов должно быть не больше 9. Посмотрим, какая из стратегий экономнее с точки зрения количества улетевших птиц. В первом случае должны улететь «лишние» 8 скворцов, 7 трясогузок и 5 дятлов – всего 20 птиц. Во втором случае нам нужно выбрать тот вид, на который мы не накладываем ограничений по численности. Ясно, что это должны быть скворцы – их больше всего. Тогда должны улететь как минимум 8 трясогузок и 6 дятлов – всего