ВСЕРОССИЙСКАЯ ИНТЕРНЕТ-ОЛИМПИАДА "МУЛЬТИМАТИКА"

Задачи Первого тура олимпиады и решения к ним

Логические задачи и принцип Дирихле 5-6 класс

Логические задачи и принцип Дирихле 3-4 классы

 

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

Задача 1.

В детском саду проводили день именинника. За круглым праздничным столом разместились 100 детей. Стулья, на которых разместились гости, были расставлены аккуратно (на равном расстоянии друг от друга). Больше половины детей, сидящих за столом, были мальчики. Гость праздника Незнайка высказал со сцены несколько предположений:

 

  • За столом 51 мальчик и 49 девочек.

  • Напротив каждой девочки обязательно сидит мальчик.

  • Найдется хотя бы один мальчик, напротив которого сидит тоже мальчик.

  • Найдется девочка, напротив которой тоже будет сидеть девочка.

 

Помогите Незнайке понять, какие его предположения точно верные. 

 

Ответ: 3

 

Решение.

1) В первом утверждении мальчиков действительно больше чем девочек, но мы не можем быть уверены в их точном количестве. Утверждение неверное.

 

2) Девочки могут сидеть как напротив мальчиков, так и напротив друг друга. Если девочек четное количество, то они могут сидеть только напротив друг друга. Утверждение неверное.

 

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

 

4) Конечно, такая расстановка может существовать (напротив девочки окажется тоже девочка), но существует и случай, когда напротив каждой девочки сядет мальчик (и мальчики еще останутся), мы не знаем какой из этих случаев произойдет. Утверждение неверное.

Задача 2.

В поле резвятся 7 козлят. По крайней мере, два из них вздумали убежать в лес погуляти. Какие утверждения могут оказаться верными?

 

  • В лес убежали ровно 2 козлика.

  • В лес могли убежать от 2 до 7 козликов (любое количество от двух до 7).

  • В лес убежал только один козлик.

  • В лес убежали все козлики.

  • В лес убежали 5 козликов.

 

Ответ: 1245

 

Решение.

Фраза «по крайней мере 2» означает, что в лес могли убежать 2 и больше козликов. Поэтому верными утверждениями могут оказаться утверждения под номерами 1, 2, 4 и 5.

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

 

Очевидно, если у вас есть две клетки и три кролика, то их можно посадить либо всех в одну клетку, и тогда в ней окажется «по крайней мере, два кролика»; либо посадить одного в одну, а два других в другую (именно в ней окажется «по крайней мере, два кролика»).

 

В любом случае такая клетка найдется. Решая задачи, вы должны представить, что вы будете считать «клетками», а что «кроликами».

Задача 3.

В группе 13 учеников. Верно ли, что найдутся, по крайней мере, двое, отмечающие свой день рождения в одном месяце? Соотнесите, что (кого) в этой задаче можно считать «клетками», а что (кого) ‑ «кроликами»? Примените принцип Дирихле и ответьте на вопрос задачи.

 

Ответ: Ученики – кролики (их 13), месяцы – клетки (их 12). Да.

 

Решение.

Так как месяцев в году 12, то в случае равномерного распределения дней рождения школьников, имея 12 человек, получим по одному дню рождения в месяц, тогда 13-ый человек точно окажется третьим в каком-то месяце. Может оказаться так, что в каком-то месяце будет больше трех именинников (они будут распределены по месяцам неравномерно).

Задача 4.

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

 

Ответ: 25.

 

Решение.

Так как месяцев в году 12, то в случае равномерного распределения дней рождений школьников, имея 24 человека, получим по два дня рождения в месяц, 25-ый человек точно окажется третьим в каком-то месяце.

Задача 5.

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

 

Ответ: 8.

 

Решение.

8 ладей поставить на шахматную доску можно (например, по диагонали от а1 к h8). Так как всего на доске 8 рядов, то при наличии более 8 ладей на один из рядов попадет не менее двух ладей, которые будут бить друг друга. В этой задаче «клетки» - ряды, а «кролики» - ладьи.

Задача 6.

Бабушка летом заготовила для внуков варенье: 10 банок клубничного, 12 банок абрикосового и 7 банок вишневого варенья. Для лучшего хранения она запечатала все варенье в непрозрачные банки, но при этом забыла их подписать. Какое наименьшее количество банок надо взять, чтобы среди них точно была банка с абрикосовым вареньем?

 

Ответ: 18.

 

Решение.

Исходя из принципа наихудшего варианта, сначала могут попадаться банки с клубничным и вишневым вареньем, их всего 17, а 18-я банка наверняка будет уже с абрикосовым вареньем.

Задача 7.

«Машины страшилки». В темной-темной комнате стоит черная-черная коробочка, а в ней лежат темные-темные носочки: 6 темно синих, 12 темно коричневых и 4 темно серых. Темный человек засовывает темную ручечку в коробочку и достает… носочки! Сколько носков нужно достать, чтобы наверняка оказалось хотя бы два носка одного цвета?

 

Ответ: 4.

 

Решение.

Исходя из принципа наихудшего варианта, сначала могут попадаться разноцветные носки, всего 3 цвета, а 4-ый носок наверняка совпадет по цвету с одним из ранее вытащенных.

Задача 8.

Вася Копейкин – любитель путешествовать и считать мелкие деньги. Приехав в некоторую страну, он узнал, что денежной единицей этой страны является бамс, при этом существуют разменные монеты достоинством 50, 25, 10, 5 и 1 бамсик. У Васи были с собой 1 бамс, а также по одной монете в 50, 25, 10 и 5 бамсиков. Он попросил местного жителя разменять ему хотя бы одну из монет. К сожалению, местный житель не смог этого сделать, так как каждый раз ему не хватало каких-то монет. Какая наибольшая сумма бамсиков была у местного жителя?

 

Ответ: 129.

 

Решение.

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

 

По 50 бамсиков может быть только одна монета (иначе 1 бамс можно было бы разменять).

 

По 25 бамсиков может быть только тоже одна монета (иначе 50 бамсиков можно было бы разменять).

 

По 10 бамсиков может быть 4 монеты (иначе 50 бамсиков можно было бы разменять).

 

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

 

По 1 бамскику может быть четыре монеты (иначе 5 бамсиков можно было бы разменять).

 

Итого: 50 + 25 + 10 × 4 + 5 + 9 = 129 бамсиков мелкими монетами.

Задача 9.

Играют в одной песочнице Саша и Женя (мальчик и девочка).

 

 

«Я – девочка», говорит ребенок с темными волосами.

 

«Я – мальчик», говорит ребенок со светлыми волосами.

 

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

1. Первый сказал неправду, а второй ‑ правду.

2. Второй сказал неправду, а первый ‑ правду.

3. Оба ребенка сказали неправду.

4. По данным задачи однозначный вывод сделать нельзя.

 

Выберите верный ответ из четырех предложенных.

 

Ответ: 3.

 

Решение.

 

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

 

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

Задача 10.

Из каюты капитана пиратов пропала карта острова сокровищ. Подозрение пало на Билла, Роджера и Пью. На допросе они заявили:

 

Билл: Я не брал карту. Карту взял Роджер.

 

Роджер: Не брал я эту карту. Пью тоже ни причём.

 

Пью: Клянусь, капитан, Роджер не виновен. Карту стащил Билл.

 

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

 

Ответ: Роджер.

 

Решение.

 

Переберем все случаи:

 

Пусть карту украл Билл. Оценим (истинные или ложные) высказывания каждого из пиратов.

Билл: оба раза солгал. Роджер: оба раза сказал правду. Пью: оба раза сказал правду. Случай не удовлетворяет условию.

 

Пусть карту украл Роджер. Билл: оба раза сказал правду. Роджер: Один раз солгал, один раз сказал правду. Пью: оба раза солгал. Случай удовлетворяет условию.

 

Пусть карту украл Пью. Этот вариант следует проверять, чтобы понять: ответ в задаче однозначный или возможны разные варианты ответа. Билл: один раз сказал правду, один раз солгал. Роджер: один раз сказал правду, один раз солгал. Пью: один раз сказал правду, один раз солгал. Случай не удовлетворяет условию. Заметим, что истинность и ложность высказываний Пью можно не проверять, так как ранее уже получено, что Билл и Роджер один раз сказали правду, а второй – солгали.

Логические задачи и принцип Дирихле 3-4 класс

Логические задачи и принцип Дирихле 5-6 классы

 

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

Задача 1.

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

 

Ответ: 0.

 

Решение.

Фраза «по крайней мере 2…» означает, что в лес могли убежать 2 и больше козликов. Допускается, что в лес убегут все 7 козликов. Значит, утверждать наверняка, что хотя бы один останется, мы не можем, то есть не побегут в лес наверняка 0 козлят, возможно, и больше.

Задача 2.

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

1. В лагерь приехали меньше пяти одноклассников.

2. В лагерь приехали не более пяти одноклассников.

3. В лагерь приехали не менее трех одноклассников.

4. В лагерь приехали более трех одноклассников.

5. В лагерь приехали меньше трех одноклассников.

 

Ответ: 123.

 

Решение.

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

 

Очевидно, если у вас есть две клетки и три кролика, то их можно посадить либо всех в одну клетку, и тогда в ней окажется «по крайней мере, два кролика»; либо посадить одного в одну, а два других в другую (именно в ней окажется «по крайней мере, два кролика»).

 

В любом случае такая клетка найдется. Решая задачи, вы должны представить, что вы будете считать «клетками», а что «кроликами».

Задача 3.

В группе 25 учеников. Верно ли, что найдутся, по крайней мере, трое, отмечающие свой день рождения в одном месяце? Соотнесите, что (кого) в этой задаче можно считать «клетками», а что (кого) ‑ «кроликами»? Примените принцип Дирихле и ответьте на вопрос задачи.

 

Ответ: Ученики – кролики (их 25), месяцы – клетки (их 12). Да.

 

Решение.

Так как месяцев в году 12, то в случае равномерного распределения дней рождения школьников, имея 24 человека, получим по два дня рождения в месяц, 25-й человек точно окажется третьим в каком-то месяце. Возможно, что найдется месяц, в котором будет более трех именинников.

Задача 4.

Какое наименьше число учеников должно быть в школе, имеющей 30 классов, для того чтобы в ней обязательно был класс, в котором не меньше 28 учеников?

 

Ответ: 811.

 

Решение.

Рассмотрим «наихудший случай» - ни в одном классе нет 28 и более учеников, максимально возможное число учеников. Тогда 811-ый человек точно окажется 28-м в каком-то классе. (Так может случиться, что при меньшем числе учеников найдется класс, в котором не меньше 28 человек, но это не наверняка, в случае 811 человек это событие наверняка произойдет).

Задача 5.

Бабушка летом заготовила для внуков варенье: 10 банок клубничного, 12 банок абрикосового и 7 банок вишневого варенья. Для лучшего хранения она запечатала все варенье в непрозрачные банки, но при этом забыла их подписать. Какое наименьшее количество банок надо взять, чтобы среди них точно были три банки с одинаковым вареньем?

 

Ответ: 7.

 

Решение.

Исходя из принципа наихудшего варианта, сначала могут попадаться 2 банки с одним вареньем, две ‑ с другим, и еще две ‑ с третьим. Следующая (седьмая) банка позволит подобрать три банки с одинаковым вареньем.

Задача 6.

«Машины страшилки». В темной-темной комнате стоит черная-черная коробочка, а в ней лежат темные-темные носочки: 6 темно синих, 12 темно коричневых и 4 темно серых. Темный человек засовывает темную ручечку в коробочку и достает… носочки! Сколько носков нужно достать, чтобы наверняка оказалось хотя бы по два носка каждого цвета?

 

Ответ: 20.

 

Решение.

Исходя из принципа наихудшего варианта, сначала могут попадаться только два цвета носков, причем тех цветов, которых больше по количеству: 12+6=18, а следующие два носка образуют пару третьего цвета. Итого 20.

Задача 7.

В очереди за мороженым стоят четыре человека. Семен находится между Борисом и Машей. Маша стоит перед двумя другими детьми, Дима занимает место перед Машей. Кто в очереди первый, второй, третий и четвертый?

 

Ответ:  1 – Дима; 2 – Маша; 3 – Семен; 4 - Борис.

 

Решение.

Так как Маша стоит перед двумя другими детьми, а Дима перед ней, то первый – Дима, а вторая Маша. Семен между Борисом и Машей, значит, Семен – третий, а Борис – четвертый.

Задача 8.

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

Четыре записки были прикреплены к шкафчику, холодильнику, хлебнице и плите. Вот их содержание:

 

На шкафчике: «Обед либо в холодильнике, либо в хлебнице».

 

На холодильнике: «Обед либо в шкафчике, либо в духовке».

 

На хлебнице: «Обеда здесь нет».

 

На плите: «Обед здесь, в духовке».

 

Где на самом деле Миша должен искать обед?

 

Ответ: В хлебнице.

 

Решение.

1.     Допустим, обед в шкафчике. Тогда записки на холодильнике и хлебнице верные. По условию правда только на одной записке.

2.     Допустим, обед в холодильнике. Тогда верны тоже две записки: на шкафчике и на хлебнице.

3.     Допустим, обед в духовке. Верны три записки: на холодильнике, на хлебнице и на плите.

4.     Допустим, обед в хлебнице. Верна записка только на шкафчике.

Задача 9.

Рассмотрим пять произвольных различных натуральных чисел. Какие утверждения будут точно верными при любом наборе этих чисел?

1. Среди этих чисел есть как четные, так и нечетные.

2. Всегда можно выбрать три числа, сумма которых делится на 3.

3. Если сумма этих чисел нечетна, то и произведение тоже нечетно.

4. Если сумма этих чисел четна, то и произведение тоже четно.

5. Всегда из этих чисел можно выбрать два числа, разность которых будет делиться на 4.

 

Подсказка. Рассмотрите остатки чисел при делении на 3 и на 4. Какими они могут быть в каждом случае?

 

Ответ: 245.

 

Решение.

Утверждение 1 неверно (все числа могут быть одинаковой четности).

Утверждение 2 верно. Если среди пяти чисел присутствуют все три числа, которые дают различные остатки при делении на 3, то, взяв три числа с различными остатками (0, 1 и 2), мы найдем три числа, которые в сумме дают число, делящееся на 3. Будем считать, что среди наших пяти чисел встречаются числа, дающие всего два различных остатка. Значит, по принципу Дирихле из пяти чисел можно выбрать три, дающие одинаковые остатки при делении на 3 (так как имеется лишь два различных остатка среди наших пяти чисел). Их сумма, очевидно, делится на 3.

Утверждение 3 неверно. Может быть 4 четных числа и одно нечетное. Их сумма нечетна, а произведение четно.

Утверждение 4 верно. Четная сумма возможна, когда нечетных чисел нет вообще или их ровно 2, или их ровно 4 (сумма двух нечетных чисел дает четный результат). Значит, обязательно среди пяти произвольных чисел есть четное число. Тогда произведение тоже четно.

Утверждение 5 верно. При делении на 4 возможны только 4 различных остатка: 0, 1, 2 или 3. Значит, какие-то два числа точно будут иметь одинаковые остатки. Их разность будет делиться на 4.

 

В этой задаче «клетки» - это возможные остатки при делении, а «кролики» - произвольные пять чисел.

Задача 10.

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

 

Алиса: я живу в Лондоне, как и Боб, а Патрик живет в Париже.

Боб: я живу в Берлине, Шульц – тоже. Патрик живет в Париже.

Патрик: Я, как и Алиса, не живу во Франции; Мария же живет в Мадриде.

Мария: Мой отец живет в Лондоне, мать – в Париже, а я живу с бабушкой в Марселе.

Шульц: Алиса приехала из Лондона, Боб – тоже, а я живу в Марселе.

 

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

 

Примечание. Марсель и Париж – это города Франции, Мадрид – в Испании, Берлин – в Германии и Лондон – в Англии.

 

Ответ:

Алиса - Лондон

Патрик - Париж

Боб – Берлин

Шульц - Марсель

Мария - Мадрид.

 

Решение.

1) Допустим, что Патрик живет не в Париже. Тогда Алиса и Боб третий раз говорили неправду, а первые их два высказывания верны. Возникает противоречие (Алиса утверждает, что Боб живет в Лондоне, а Боб заявляет, что он живет в Берлине). Значит, предположение неверно.

 

2) Итак, Патрик живет в Париже (это верно). Тогда третье заявление Алисы верное, а из первых двух следует, что либо она сама живет в Лондоне, тогда Боб – не в Лондоне; либо наоборот, Боб – в Лондоне, а Алиса не в Лондоне. Тогда из заявления Шульца следует, что он живет в Марселе.

 

3) В высказывании Патрика ложью является то, что он не живет во Франции, так как ранее установлено, что он живет в Париже (столице Франции). Тогда его последнее высказывание верно, т.е. Мария живет в Мадриде.

 

4) Так как Шульц живет в Марселе (п. 2), то второе высказывание Боба ложно, значит, первое истинно, т.е. Боб живет в Берлине.

 

5) Тогда Алиса живет в Лондоне (см. выводы в п. 2).

Контактная информация:

Для вопросов по курсам БЕСПЛАТНЫЙ НОМЕР

8-800-707-04-94

Режим работы:

Пн-Пт: с  6-00 по 15-00 по московскому времени

Наши координаты:

644024, г. Омск, ул. Куйбышева, 56, офис 11

Тел./факс: +7 (3812) 490-633

E-mail: 490-633@mail.ru, isoti-it@mail.ru

 

​©  НОУ "ИСОТИ", 2015.

Разработка сайта: ООО "ЦИТО"

Wix Hit Counter

Контактная форма