В темной комнате стоит шкаф

Обновлено: 22.01.2025

Комментарий. Все задачи этого занятия решаются аналогично задачам 0 и 1. Прочитайте решения к этим задачам, а затем решите остальные самостоятельно, применяя похожие рассуждения. Задача 0 решается методом доказательства «от противного». На нем же основан принцип решения задачи 1 и всех последующих. Этот принцип и называется принципом Дирихле (более точную его формулировку мы здесь приводить не будем). 0. В коробке лежат шарики двух цветов. Сколько шариков достаточно наугад вынуть из коробки, чтобы среди них заведомо нашлись два одноцветных?

Ясно, что двух шариков будет недостаточно: может оказаться, что они разных цветов. Поэтому нужно взять не меньше трех шариков.

Докажем, что трех шариков достаточно. Предположим противное (то есть противоположное), а именно, что трех шариков недостаточно (то есть что среди трех шариков может и не найтись двух одноцветных). Если три все шарика разноцветные, то они покрашены в три цвета. Но в коробке есть шарики только двух цветов. Это противоречие означает, что наше предположение было неверным. А стало быть, среди трех шариков всегда найдутся два одноцветных

1. а) Семерых кроликов посадили в шесть клеток. Докажите, что есть клетка, в которой оказалось хотя бы два кролика. б) Семерых кроликов посадили в три клетки. Докажите, что есть клетка, в которой оказалось хотя бы три кролика.

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

б) Предположим, что это не так, то есть что в каждой клетке оказалось не больше двух кроликов. Тогда всего кроликов могло быть не больше 3·2=6. Но по условию задачи их было 7. Полученное противоречие показывает, что наше предположение было неверным. Стало быть, на самом деле найдется клетка, в которой оказалось хотя бы три кролика.

Замечание. При решении следующих задач полезно каждый раз понимать, кто (или что) выполняет роль «клеток», а кто (или что) роль кроликов. Однако, выяснив это, не ссылайтесь на решения предыдущих задач, а проводите аналогичные рассуждения заново. 2. В лесу растет миллион лиственниц. Известно, что на каждой из них не более 400 000 иголок. Докажите, что в лесу найдутся по крайней мере три лиственницы с одинаковым числом иголок. 3. За победу в математической регате команда из четырех человек получила 10 конфет. Дети поделили конфеты между собой, не разламывая их. Определите, всегда ли верны ли следующие утверждения: а) «кому-то досталось по крайней мере 2 конфеты»; б) «кому-то досталось по крайней мере 3 конфеты»; в) «по крайней мере двум людям досталось по крайней мере по две конфеты»; г) «каждому досталась хотя бы одна конфета»; д) «кому-то досталась ровно две конфеты»; е) «кому-то досталась ровно одна конфета». 4. В ящике лежат шары: 5 красных, 7 синих и 1 зеленый. Сколько шаров надо вынуть, не глядя, чтобы среди них наверняка оказалось 2 шара одного цвета? 5. а) В темной комнате стоит шкаф, в ящике которого лежат 24 черных и 24 синих носка. Какое минимальное число носков следует взять из шкафа, чтобы из них заведомо можно было составить по крайней мере одну пару носков одного цвета? б) Сколько надо взять носков, чтобы заведомо можно было составить хотя бы одну пару носков черного цвета? в) Как изменится решение задачи, если в ящике лежат 12 пар черных и 12 пар синих ботинок и требуется составить пару одного цвета (как в пункте а) и пару черного цвета (как в пункте б)? 6. а) В школе 400 учеников. Верно ли, что хотя бы двое их них родились в один день года? б) Верно ли, что в группе из 10 человек всегда найдутся двое, родившиеся в один день недели? в) Верно ли, что в классе из 25 человек всегда найдутся трое, родившиеся в одном и том же месяце (не обязательно в один год)? 7. В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки только одного сорта. Найдутся ли 9 ящиков с яблоками одного и того же сорта? 8. В классе 30 человек. Андрей сделал в диктанте 13 ошибок, а остальные — меньше. Докажите, что по крайней мере три ученика сделали равное количество ошибок.

В темной комнате стоит шкаф

1. Восемь кроликов посадили в семь клеток. Докажите, что есть клетка, в которой оказалось по крайней мере два кролика.

Решение. Если бы ни в какой клетке не было двух кроликов, то всего их было бы не больше, чем клеток, то есть, максимум 7. Но кроликов 8, противоречие.

2. За победу в математической регате команда из 4 человек получила 10 конфет. Дети поделили конфеты между собой, не разламывая их. Определите, верны ли следующие утверждения: а) "кому-то досталось по крайней мере 2 конфеты"; б) "кому-то досталось по крайней мере 3 конфеты"; в) "двум людям досталось по крайней мере две конфеты"; г) "каждому досталась хотя бы одна конфета".

а) Если бы никому не досталось две конфеты, то конфет всего было бы не больше 4. Но их 10, противоречие.

б) Если бы никому не досталось три конфеты, то конфет всего было бы не больше 2·4 = 8. Но их 10, противоречие.

в, г) Теоретически, все конфеты мог забрать, например, один человек.

3. а) В темной комнате стоит шкаф, в котором лежат 24 чёрных и 24 синих носка. Какое минимальное количество носков нужно взять из шкафа, чтобы из них заведомо можно было составить по крайней мере одну пару носков одного цвета? б) Какое минимальное количество носков нужно взять, чтобы заведомо можно было составить хотя бы одну пару носков черного цвета? в) Как изменится решение задачи, если в ящике лежат 12 пар чёрных и 12 пар синих ботинок и требуется составить пару одного цвета (как в пункте а) и пару черного цвета (как в пункте б)? Ботинки, в отличие от носков, бывают левыми и правыми.

а) Если взять только два носка, то они могут оказаться разных цветов, и составить из них пару не получится. А из трёх носков два точно будут одного цвета.

б) Если взять 25 носков, то 24 из них могут оказаться синими, и составить чёрную пару не получится. Если же взять 26 носков, то синих среди них не может быть больше 24 синих, поэтому точно будут два чёрных.

в) Если взять 24 ботинка, то все они могут оказаться левыми, и составить пару из них не получится. Разобьём мысленно все 48 ботинок на пары. Пар будет 24. Если взять 25 ботинок, то два из них точно будут из одной пары.
Если взять 36 ботинок, то 24 из них могут оказаться синими, а остальные 12 — левыми чёрными, и составить из них чёрную пару не получится. Если взять 37 ботинок, то хотя бы 13 из них будут чёрными, а значит, будет точно хотя бы один чёрный левый и хотя бы один чёрный правый.

4. В лесу растут миллион ёлок. Известно, что на каждой из них не более 600000 иголок. Докажите, что есть две ёлки с одинаковым количеством иголок.

Решение. У ёлки может быть 0, 1, 2, . 600000 иголок. 600001 возможный вариант, а ёлок больше (1000000). Значит, какой-то вариант точно повторяется, т.е. найдутся две ёлки с одинаковым количеством иголок.

Решение. Если такого класса нет, то учеников в школе не может быть больше, чем 33·30 = 990 < 1000, противоречие.

6. В квадратном ковре со стороной 4 метра моль проела 15 дырок. Докажите, что из этого ковра можно вырезать коврик со стороной 1 метр, в котором дырок не будет.

Решение. Разобьём ковёр на 16 маленьких ковриков размером 1×1. Так как дырок всего 15, хотя бы один квадратик окажется без дырок. Его и можно вырезать.

7. В финальном матче школьного чемпионата по баскетболу команда 5А забила 9 мячей. Докажите, что найдутся два игрока этой команды, забившие поровну мячей. (В команде по баскетболу 5 игроков.)

Решение. Предположим, что такие два игрока не найдутся. Тогда все пять игроков забили разное количество мячей. Пусть первый игрок ничего не забил, второй забил один мяч, третий — два, четвёртый — три, пятый — четыре. Тогда всего игроки забили 10 мячей. Если же кто-то забил больше, чем мы предположили, то и всего мячей было забито больше. Но поскольку по условию игроки забили 9 мячей, наше предположение неверно. Значит, есть два игрока, забившие поровну.

8. Верно ли, что в вашей аудитории есть по крайне мере два человека, имеющие одинаковое число друзей в этой аудитории? Верно ли это для любой аудитории Малого мехмата?

Решение. Да, верно. Проведём рассуждения сразу для любой аудитории.
Пусть в аудитории n человек, и у всех из них разное количество друзей. Друзей может быть 0, 1, 2, . ( n − 1). Всего n возможных вариантов. А так как человек тоже n , то все эти варианты используются. Значит, есть человек, у которого 0 друзей, т. е. который ни с кем не дружит. И есть человек, у которого ( n − 1) друг, т.е. который дружит со всеми. Однако этого быть не может, т.к. эти два человека должны одновременно и дружить, и не дружить друг с другом. Получаем противоречие. Значит, два человека с одинаковым количеством друзей всегда найдутся.

Дополнительные задачи

9. Каждая клетка таблицы 2011×2011 покрашена в один из 2010 цветов. За ход можно взять строку или столбец и, если там есть две клетки одного цвета, перекрасить эту строку или столбец в этот цвет. Всегда ли можно за несколько ходов покрасить всю таблицу в один цвет?

Решение. Возьмём любую строку. Так как цветов 2010, а клеток в строке — 2011, есть по крайней мере две клетки одного цвета. Значит, мы можем перекрасить всю строку в этот цвет. Воспользуемся этим и покрасим каждую строку в какой-нибудь цвет. Теперь у нас есть 2011 строк, покрашенные в 2010 цветов. Значит, по крайней мере две строки покрашены в один цвет (допустим, красный). То есть, в любом столбце есть две красные клетки. Покрасим все столбцы в красный цвет — все клетки доски будут покрашены в один цвет.

10. Можно ли клетки доски 5×5 покрасить в четыре цвета так, чтобы клетки, стоящие на пересечении любых двух строк и любых двух столбцов, были покрашены не менее, чем в три цвета?

Решение. Нельзя.
Предположим, что существует раскраска таблицы 5×5, удовлетворяющая условию. Рассмотрим эту таблицу.

В каждом столбце найдется цвет, в который покрашены по крайней мере две клетки этого столбца. Назовем такой цвет преобладающим для данного столбца (возможно, у какого-то столбца будет два преобладающих цвета). Аналогично, какой то цвет (назовем его 1) будет преобладающим для двух столбцов. Поскольку от перестановки строк и столбцов ничего не зависит, будем считать, что это столбцы a и b. Также можем считать, что в первом столбце цветом 1 покрашены клетки a4 и a5. Тогда клетки b4 и b5 должны быть покрашены какими-то двумя различными цветами, отличными от цвета 1. Пусть они покрашены цветами 2 и 3, а поскольку цвет 1 — преобладающий для столбца b, можем считать, что клетки b2 и b3 покрашены цветом 1. Рассмотрим клетку a3. Выбрав 3 и 4 строку и столбцы a и b, мы получим, что клетка a3 не может быть покрашенной цветами 1 и 3. Выбрав 3 и 5 строку и столбцы a и b, мы получим, что клетка a3 не может быть покрашенной цветами 1 и 2. То есть клетка a3 покрашена цветом 4. Но из аналогичных рассуждений мы получаем, что и клетка a2 покрашена цветом 4. То есть квадрат, состоящий из клеток a3, a2, b3 и b2, покрашен в два цвета — противоречие.

Парные носки

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

Ответ: Обычно на вопрос задачи дают неправильный ответ: 25 носков. Если бы в задаче спрашивалось, сколько носков следует взять из ящика, чтобы среди них было по крайней мере 2 носка различного цвета, то правильный ответ действительно был бы таким: 25 носков. Но в нашей задаче речь идет о том, чтобы среди взятых из ящика носков по крайней мере 2 носка были одного цвета, поэтому правильный ответ задачи иной: 3 носка. Если я возьму из ящика 3 носка, то они либо все будут одного цвета (и в этом случае я заведомо смогу выбрать из них по крайней мере 2 носка одного цвета), либо 2 носка будут одного цвета, а третий носок другого, что позволит мне также составить пару одноцветных носков.

Понимаю,что мужчины не учитывают такую важную деталь, как то, что носки бывают разные: на правую ногу, и левую)))) соответсвенно пара это один правый, другой левый, плюс одного цвета))
допустим вытащили 12 красных но все правые, потом 12 синих но все левые, итого 24, а пары то искомой и нет, значит надо вытянуть 25 носок ))))

Оставлен admin Сб, 05/08/2010 - 02:28

Первый раз слышу, чтобы левый и правый носок чем-то отличались

Оставлен Гость Чт, 05/20/2010 - 17:29

ну если носки заносить до дырочек на больших пальцах, то тогда отличаются))))

Оставлен Гость Сб, 10/09/2010 - 15:07

а вы попробуйте в носках одних и тех же ходить неделю . поймете разницу . условие надо корректировать " в ящике лежат 48 ЧИСТЫХ носков" так политкорректнее будет =)

Оставлен Юлька Пт, 10/22/2010 - 06:09

легкотня, я за несколько секунд догадалась

Оставлен Гость Втр, 11/15/2016 - 20:52

Условие не правильно! В следствии человеческой физиологии парные вещи отличаются друг от друга! Да, вполне возможно надеть правый ботинок на левую ногу и так ходить. Некоторые, носят перчатки и не различают на правые или левые! Действительно, штампованные тонкие носки, трудно различить на правые или левые! Но вот шерстяные связанные носки достаточно хорошо различаются на правые или левые! Можно конечно, носить и трусы, и финки задом на перёд, и чувствовать себя достаточно комфортно! Но тем не менее, парная одежда и обувь у нас в России различается на правую и левую. Задачка иностранная, у них немного другое мышление! Как рассказывал Задорнов про велосипеды! На складе 12 рам и 24 колеса, сколько на складе велосипедов? Ответ по-русски: "Ни одного!". Ответ по-американски: "12"! У нас разное этническое мышление! И в условие обязательно надо было уточнить, что составление пар должно без учёта дифференциации!

Оставлен человек Пнд, 05/22/2017 - 21:37

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

Оставлен Гость Пт, 05/21/2010 - 23:30

я тоже с левыми и правыми решал))

Оставлен Гость Втр, 06/01/2010 - 09:58

Не надо хитрить.

Оставлен Vold Пт, 06/18/2010 - 07:02

не бывает у нормальных мужчин левых и правых носков. и у нормальных женщин тоже. это вам не перчатки.

Оставлен itachi Вс, 07/04/2010 - 19:15

Оставлен itachi Вс, 07/04/2010 - 19:16

то есть носки не различаются на правые и левые

Оставлен Гость Пт, 08/13/2010 - 09:43

как множно ответить 25.

Оставлен Гость Пт, 08/13/2010 - 16:39

Кто такой умный? Купите носки, и найдите отличие между правым и левым. Их нет! Или вы перчатки на ноги надеваете?

Оставлен YURACIK Втр, 10/12/2010 - 19:12

Есть отличие от правых и левых носков! Не знаю какие ты носки покупаеш - но у меня правый и левый носки отличаются! Хоть я и одеваюка попало, но факт тчо они отличаются.

Оставлен Артем Чт, 06/13/2019 - 16:41

ПОКУПАЕШ? - ЭТО НАЗВАНИЕ МАГАЗИНА? ДА, МОЖЕТ ТАМ И ОТЛИЧАЮТСЯ.

Оставлен Гость Пт, 08/13/2010 - 16:42

Если ты наденешь носок на левую ногу, то это будет левый носок. А если ты его снимешь и наденешь на правую ногу, то он тут же станет правым!

Оставлен Кря Пнд, 09/27/2010 - 18:53

В темной комнате не видно цвета, так что бери два носка

Оставлен Бад Пт, 02/11/2011 - 08:59

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

Оставлен Гость Пт, 03/18/2011 - 20:21

Ольга, даже если решать с левыми и правыми, то 25 носков не понадобится.
у нас 24 носка красные 24 синие, значит по 12 пар. берём 12 носков тогда мы вытенем либо 6 левых 6 правых одного цвета тогда точно будет пара, либо несколько правых одного цвета несколько правых другого несколько левых одного и несколько левых другого тогда тоже найдётся пара, либо 6 правых одного цвета 6 правых другого (или все левые без разницы главное то, что они одинаковы)тогда в шкафу останется 6 левых одного и 6 левых другого (или правых соответственно) тогда нам нужно вытащить один носок и он окажется либо левым одного цвета или левым другого а правые у нас в руках уже есть значит пара будет. Вывод - наименьшее число - 13 носков.

Как же называется эта книга?

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

Столь странное противоречие объясняется тем, что между рубежами, завоеванными современной математикой, и традиционно читаемыми «устоявшимися» курсами математики существует разрыв, красочно описанный замечательным представителем этой науки, педагогом и популяризатором Гуго Штейнгаузом: «В математике несравненно явственней, чем в других дисциплинах, ощущается, насколько растянуто шествие всего человечества. Среди наших современников есть люди, чьи познания в математике относятся к эпохе более древней, чем египетские пирамиды, и они составляют значительное большинство. Математические познания незначительной части людей дошли до эпохи Средневековья, а уровня математики XVIII века не достигает и один на тысячу… Но расстояние между теми, кто идет в авангарде, и необозримой массой путников все возрастает, процессия растягивается, и идущие впереди отдаляются все более и более. Они скрываются из виду, их мало кто знает, о них рассказывают удивительнейшие истории. Находятся и такие, кто просто не верит в их существование».

«Растянутость шествия всего человечества» особенно ощутима, когда речь заходит не о рецептурной, алгоритмической, а об «идейной» стороне математики.

С незапамятных времен математические рассуждения считаются общепризнанным эталоном доказательности, достойным всяческого подражания (достаточно упомянуть «Этику» Спинозы, «изложенную на геометрический манер», или «Математические начала натуральной философии» Ньютона). Строгость математических доказательств, непреложность получаемых с их помощью выводов, незыблемость математических истин вошли в поговорку. Но прописные истины, подобно разменной монете, от частого употребления стираются и теряют в весе. Доверять им по меньшей мере неосмотрительно, а получить достоверную информацию о действительном положении вещей нелегко не только для человека далекого от математики, но и для математика, не занимающегося специально проблемами оснований математики и математической логики. Те, кто, желая похвалить обоснованность чьей-либо аргументации, с легкостью называют ее математически строгой и безупречной, как правило, не в состоянии объяснить, что означает «доказать», почему доказательство «доказывает», или ответить, всякое ли утверждение можно доказать или опровергнуть. Подобные вопросы способны поставить в тупик и несравненно более искушенного в математике нематематика, который умеет вычислить значение истинности таких высказываний, как «Речка движется и не движется», или импликации «“Если” гром не грянет, “то” мужик не перекрестится», знает, чем исключающее «или» (Либо пан, либо пропал) отличается от неисключающего (Надобно либо уменье, либо везенье, «а лучше всего и то, и другое»), постиг различие между причинно-следственной связью и импликацией и усвоил немало других премудростей алгебры логики.

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

Предлагаемая вниманию читателя книга американского ученого Рэймонда М. Смаллиана, известного своими работами в области математической логики, опровергает известные слова Пифагора о том, что в математику нет царской дороги. Перед ее читателем открывается редкая, чтобы не сказать уникальная, возможность проникнуть в существо одного из величайших достижений математической логики нашего века – в доказательство знаменитой теоремы Гёделя о неполноте. По занимательности, динамичности и напряженности действия книга Смаллиана не уступает лучшим образцам приключенческого жанра. Намного превосходя по глубине научного содержания большинство научно-популярных произведений и даже отдельные сугубо научные издания, книга Смаллиана помогает читателю совершить головокружительное восхождение от «дурацких штучек» (как автор называет элементарные логические задачи, не требующие для своего решения ничего, кроме находчивости, внимания и здравого смысла) к одной из вершин современной математической логики, на покорение которой обычно приходится затрачивать немало сил и средств. Попутно автор знакомит читателя со своенравной Порцией и ее не менее своенравными прапра…правнучками до N-го колена, проницательным инспектором Крэгом, искусными мастерами Челлини и Беллини, приглашает побывать на островах, населенных рыцарями, неизменно говорящими правду, и столь же неукоснительно лгущими лжецами, побывать в замке графа Дракулы Задунайского и, пережив множество увлекательных приключений, завершить необычайное путешествие на гёделевых и дважды гёделевых островах.

С непостижимой ловкостью фокусника (не все ученые коллеги автора знают, что в годы аспирантуры он выступал в этом качестве на профессиональной эстраде) Смаллиан демонстрирует новые, порой весьма неожиданные варианты известных задач, изобретает необычайно изящные головоломки собственной конструкции, раскрывая перед читателем логику «во всем ее блеске и великолепии».

Профессор Смаллиан умеет неопровержимо доказать, что либо он, либо читатель не существует, причем неизвестно, какая из альтернатив истинна! Чтобы постичь столь высокое искусство доказательства, необходимо внимательно прочитать его книгу. Поэтому пока мы ограничимся утверждением (с истинностью которого не может не согласиться даже тот, кто не читал книги), что книга Смаллиана с неуловимо исчезающим названием «Как же называется эта книга?» (попробуйте объяснить кому-нибудь, как она называется, и вы поймете, что имеется в виду) попадет в руки либо читателю, интересующемуся математикой, либо читателю, для которого математика не представляет ни малейшего интереса (хотя заранее неизвестно, какая альтернатива уготована тому или иному экземпляру книги). С неменьшей уверенностью можно утверждать, что и тот и другой прочитают ее с интересом и пользой.

Посвящается Линде Ветцель и Джозефу Бевандо, чьи мудрые советы были для меня неоценимы

Я хочу от души поблагодарить…

Прежде всего моих добрых друзей Роберта и Ильзу Коуэн и их десятилетнюю дочь Ленору, прочитавших рукопись этой книги и высказавших множество полезных советов. (В частности, Ленора угадала правильный ответ на ключевой вопрос главы 4: существует ли Трулюлю в действительности или его выдумал Шалтай-Болтай?)

Выражаю свою искреннюю признательность Григу и Мелвину Фиттингамт (авторам чудесной и полезной книги «Во славу простых вещей») за их интерес к моей работе и за то, что они обратили на нее внимание Оскара Коллиера из издательства «Прентис-холл». Думаю, что мне следует особо поблагодарить Мелвина за то, что он возник в этой книге (опровергнув своим появлением мое доказательство того, что он никак не мог бы появиться!).

Работать с Оскаром Коллиером и другими сотрудниками издательства «Прентис-холл» для меня было удовольствием. Миссис Илене Макгрэт, перепечатавшая рукопись книги, высказала много полезных советов, которые я с благодарностью принял. Выражаю признательность Дороти Лахман, весьма изобретательно находившей нужные детали и оттенки.

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

В темной комнате стоит шкаф

В темной комнате стоит шкаф

Дополнительные задачи

Парные носки

Комментарии