Ухтышка -задача, головоломка, загадка, ответ на которую или решение которой вызывает возглас "Ух ты!". К сожалению, решив "ухтышку" один раз, ты не испытаешь такой же вау-эффект при решении задачи с таким же принципом. Можно сказать, что эти загадки одноразовые, но при всём при этом они учат решающего, что, вероятно, путь решения находится за пределами картины миры решателя.
Задача 030. Имеются чашечные весы без гирь и 9 одинаковых по внешнему виду монет. Одна из монет фальшивая, причем неизвестно, легче она настоящих монет или тяжелее (настоящие монеты одного веса). Сколько надо сделать взвешиваний, чтобы определить фальшивую монету?
Решение:
Поскольку мы не знаем, легче или тяжелее фальшивая монета настоящих, то определение этого будет нам стоить одного лишнего взвешивания.
Вначале разделим монеты на три кучки по три монеты в каждой. Поскольку фальшивая монета только одна, то она окажется в одной из кучек, а в двух других будут только настоящие монеты. Поэтому кучка с фальшивой монетой будет отличаться по весу от двух других, которые будут весить одинаково. Определим сначала кучу, в которой находится фальшивая монета.
Положим первую и вторую кучку на разные чашки весов.
Возможны два случая:
ПЕРВЫЙ СЛУЧАЙ. Чашки весов уравновешены. Значит, эти кучки весят одинаково и в них нет фальшивой монеты. Следовательно, фальшивая монета находится в третьей кучке. Снимаем все монеты с весов — они настоящие — и откладываем их в сторону. Берем две монеты из третьей кучки и кладем их на разные чашки весов. Опять возможны два случая:
а) Чашки весов уравновешены. Значит, на весах настоящие монеты, а фальшивой является третья монета. За два взвешивания мы определили, какая из монет фальшивая, но не определили, легче она или тяжелее настоящих. Если это надо, то третьим взвешиванием мы это легко делаем.
б) Одна из чашек оказалась ниже другой. Значит, фальшивая монета на весах, но неизвестно на какой стороне. Третьим взвешиванием мы можем определить, на какой чашке весов находится фальшивая монета, и даже узнать, легче она или тяжелее настоящей.
Предположим, для определенности, что левая чашка весов оказалась выше, а правая ниже. Снимем с правой чашки монету и положим туда третью (настоящую) монету. Если чаши весов уравновесятся, то снятая монета фальшивая и она тяжелее настоящих. Если же левая чашка так и останется выше правой, то фальшивая монета в левой чашке, и она легче настоящих.
ВТОРОЙ СЛУЧАЙ. Одна из чашек оказалась ниже другой. Значит, фальшивая монета в одной из этих кучек. Вторым взвешиванием мы можем определить, в какой именно кучке находится фальшивая монета, и даже узнать, легче она или тяжелее настоящей. Предположим, для определенности, что левая чашка весов оказалась выше, а правая ниже.
Снимем с правой чашки монеты и положим туда монеты из третьей кучки. Если чаши весов уравновесить, то фальшивая монета в снятой кучке, и она тяжелее настоящих. Если же левая чашка так и останется выше правой, то фальшивая монета в левой чашке, и она легче настоящих. Третьим взвешиванием из трех монет легко, аналогично предыдущей задаче, находим фальшивую.
Таким образом, за три взвешивания мы определили фальшивую монету и даже узнали, легче она или тяжелее настоящих.
Ответ: не более трех.
Задача 031. Мария помогает отцу укладывать плитку на пол прямоугольной комнаты для игр. Всего у них ушло ровно 2005 квадратных плиток двух цветов — черного и белого. Периметр в одну плитку шириной был полностью черным. Остальная плитка имела белый цвет. Сколько белых плиток потребовалось, чтобы покрыть пол?
Решение:
Если сделать рисунок, то мы получим два прямоугольника, где если размеры внутреннего прямоугольника x и y, то ширина внешнего равна x+2, а длина — y +2. Естественная реакция — представить полученную информацию алгебраически в форме уравнения:
(x + 2) (y +2) = 2005.
Выполнив умножение и упростив это уравнение, мы получим:
xy + 2y + 2x + 4 = 2005
xy + 2y + 2x = 2001.
Мы получили одно уравнение с двумя неизвестными, и нам нужно найти xy. Это тупик, а не решение.
Подойдем к имеющейся информации с другой стороны и рассмотрим все возможности. Количество плиток, равное 2005, можно разложить на множители только двумя путями: либо 1 × 2005, либо 5 × 401. Это дает два возможных размера искомого прямоугольника. Первую ситуацию можно отбросить, поскольку при ширине в одну плитку для белых плиток места нет.
Следовательно, в игровой комнате должно быть 5 × 401 плиток. Поскольку снаружи выполнена «рамка» шириной в одну плитку, размеры внутреннего прямоугольника из белых плиток на две плитки меньше в каждом направлении. Если уменьшить каждое направление на две плитки, то количество белых плиток для внутреннего прямоугольника составит: 3×399=1197.
Таким образом, для покрытия пола было использовано 1197 белых плиток.
Задача 032. Из 81 монеты одна фальшивая, она легче остальных. Можно ли при помощи четырех взвешиваний на чашечных весах без гирь определить, какая монета фальшивая? Сколько потребуется взвешиваний для 80 монет? А сколько потребуется взвешиваний для n монет (n — произвольное число)?
Решение:
Следует разделить монеты на три кучки. Определить, в какой из них находится фальшивая монета, и эту кучку разделить опять на три кучки и т. д. Рассмотреть случаи, когда две кучки весят одинаково и не одинаково.
Разложим монеты на три равные кучки по 27 монет каждая.
Сначала сравним вес двух кучек. Если они весят одинаково, то фальшивая монета в третьей кучке. Если нет, то фальшивая монета в более легкой кучке. Таким образом, за одно взвешивание мы можем определить, в какой из трех кучек находится фальшивая монета.
Теперь разделим эту кучку на три равные кучки по 9 монет и повторим процедуру. Определив кучку с фальшивой монетой, разделим ее на три кучки (по 3 монеты) и за одно взвешивание определим кучку с фальшивой монетой. Теперь из трех монет мы за одно взвешивание определим фальшивую монету. В результате нам потребовалось 4 взвешивания.
Если монет было бы 80, то их надо было бы разбить на три кучки так: две кучки по 27 и одну c 26 монетами. Определить, в какой из них находится фальшивая монета, и т. д. В итоге нам также потребовалось бы 4 взвешивания.
Заметим общую закономерность.
1) Если количество монет не превосходит 3, то нужно 1 взвешивание. Если количество монет больше 3, но не превосходит 32, то нужно 2 взвешивания.
2) Если количество монет больше 32, но не превосходит 33, то нужно 3 взвешивания.
3) Если количество монет больше 33, но не превосходит 34, то нужно 4 взвешивания.
Получаем, что, действуя аналогичным образом при количестве монет, равном n, где 3𝑘−1<𝑛≤3𝑘, мы произведем k взвешиваний.
Ответ: Да; 4; k, где 3𝑘−1<𝑛≤3𝑘.
Задача 033. (Смекалка кузнеца Хечо). Назад тому лет 300 жил в Грузии князь злой и надменный. Была у князя дочь-невеста, Дариджан по имени. Обещал князь свою Дариджан в жены богатому соседу, а она полюбила простого парня, кузнеца Хечо. Попытались было Дариджан и Хечо убежать в горы от неволи, но поймали их слуги князевы.
Рассвирепел князь и решил назавтра казнить обоих, на ночь же приказал их запереть в высокую, мрачную, заброшенную, недостроенную башню, а вместе с ними еще и служанку Дариджан, девочку-подростка, которая помогала им бежать.
Не растерялся в башне Хечо, осмотрелся, поднялся по ступенькам в верхнюю часть башни, в окно выглянул — прыгать невозможно, разобьешься. Тут заметил Хечо около окна забытую строителями веревку, перекинутую через заржавленный блок, укрепленный повыше окна. К концам веревки были привязаны пустые корзины, к каждому концу — по корзине. Хечо вспомнил, что при помощи этих корзин каменщики поднимали вверх кирпич, а вниз спускали щебень, причем, если вес груза в одной корзине превышал вес груза в другой примерно на 5 — 6 кг, то корзина довольно плавно опускалась на землю; другая корзина в это время поднималась к окну.
Хечо на глаз определил, что Дариджан весит около 50 кг, служанка не более чем 40 кг. Свой вес Хечо знал — около 90 кг. Кроме того он нашел в башне цепь весом в 30 кг. Так как в каждой корзине могли поместиться человек и цепь или даже 2 человека, то им всем троим удалось спуститься на землю, причем спускались они так, что ни разу вес опускающейся корзины с человеком не превышал веса поднимающейся корзины более чем на 10 кг.
Как они выбрались из башни?
Решение:
1. Сначала «пленники» положили цепь (30 кг) в корзину и отправили ее вниз.
2. В поднявшуюся наверх пустую корзину села девочка-служанка (40 кг) и опустилась вниз; в то же время корзина с цепью поднялась вверх.
3. Хечо вынул цепь и посадил в корзину Дариджан (50 кг). Дариджан опустилась вниз, поднимая вверх служанку-девочку.
4. Дариджан вышла из корзины на землю, а девочка из поднявшейся корзины — в башню.
5. В освободившуюся наверху корзину Хечо снова положил цепь и вторично опустил ее на землю.
6. На земле в корзину с цепью села Дариджан (50 + 30 = 80 кг), а в поднявшуюся корзину сел Хечо (90 кг).
7. Хечо спустился, вышел из корзины на землю, а Дариджан вышла из поднявшейся корзины в башню. Цепь она оставила в поднявшейся корзине.
8. Цепь в третий раз опустилась на землю.
9. В поднявшуюся корзину снова села девочка (40 кг) и опустилась на землю, поднимая цепь (30 кг).
10. Дариджан вынула цепь, села в корзину (50 кг) и опустилась вниз, поднимая вверх девочку (40 кг). Дариджан вышла на землю, а девочка в башню.
11. Девочка положила в корзину цепь и опять опустила ее на землю, затем сама села в поднявшуюся пустую корзину и опустилась вниз, поднимая цепь наверх.
12. «Приземлившись», девочка присоединилась к ожидающим ее Дариджан и Хечо, а цепь в последний раз упала на землю.
Все трое благополучно укрылись в горах от свирепого князя.
Задача 034. Веб-сайт просит пользователя создать восьмизначный пароль, содержащий только цифры, где каждая цифра используется только один раз. Определите: сколько существует различных возможных паролей?
Решение:
Для создания такого пароля разрешается применять только цифры – 10 символов. Каждая цифра должна использоваться только один раз. Значит, для определения количества паролей необходимо использовать формулу размещения без повторений:
Тогда, количество размещений из 8 цифр, выбранных из 10, составляет 1814400 паролей
Ответ: 1814400 паролей, содержащих только цифры, где каждая цифра используется только один раз.
Задача 035. Какое наибольшее число полей на доске 8х8 можно закрасить в черный цвет так, чтобы в любом уголке из трех полей было по крайней мере одно не закрашенное поле?
Решение:
Если разбить шахматную доску на квадраты 2х2, то в каждом квадрате можно закрасить максимум две клетки. Значит, максимальное число закрашенных клеток 32. Это максимальное значение достигается при обычной шахматной раскраске.
Ответ: 32.
Задача 036. На доске написаны три различных числа от 1 до 9. Одним ходом разрешается либо прибавить к одному из чисел 1, либо вычесть из всех чисел по 1. Верно ли, что всегда можно добиться того, чтобы на доске остались только нули, сделав не более 23 ходов?
Решение:
Пусть вначале на доске написаны числа 1, 2 и 9, и через несколько ходов из них получились нули. Если из 9 в результате получился ноль, то вычитание производилось хотя бы девять раз. Значит, и из остальных чисел вычиталось хотя бы по девять единиц; значит, к 1 надо было сделать не меньше восьми прибавлений, а к двойке не меньше семи.
Итоговое количество ходов, таким образом, не меньше 9 + 8 + 7 = 24.
Ответ: неверно.
Задача 037. На острове Серобуромалин обитают 13 серых, 15 бурых и 17 малиновых хамелеонов. Если встречаются два хамелеона разного цвета, то они одновременно меняют свой цвет на третий (серый и бурый становятся малиновыми и так далее). Может ли случиться, что через некоторое время все хамелеоны будут одного цвета?
Решение:
Итак, имеется тройка чисел (13, 15, 17). Разрешается делать с ней следующие преобразования: к одному из чисел прибавить двойку, а от двух оставшихся одновременно отнять единицу. Спрашивается, можно ли получить один из наборов: (45, 0, 0); (0, 45, 0) или (0, 0, 45)?
Имеем процесс. Начнем искать инвариант. Прежде всего посмотрим, что можно сделать за один шаг. Можно получить (12, 14, 19)? Видны ли какие-либо грубые неизмененные вещи? Нет, разве что разность между первым и вторым членом не изменилась. А что с ней произойдет при каком-нибудь другом преобразовании? Мы можем получить из исходного набора также набор (12, 17, 16). Что здесь можно сказать относительно разности первого и второго? Она изменилась. Кстати, на сколько? На три. Ладно, и третье изменение из исходного: (15, 14, 16). Здесь разность совсем изменилась. А сейчас на сколько? Было −2, а стало +1. Разность –– 3. Что? Тройка у нас уже встречалась? Когда? В предыдущем случае. Только там в другую сторону. Все равно, что-то в этом есть.
Не пора ли перейти к остаткам? Остатки по модулю три. Исходная тройка чисел преобразуется в набор остатков (1, 0, 2). Требуется получить остатки (0, 0, 0) во всех трех случаях. Что можем получить после первого преобразования? (0, 2, 1), или (0, 2, 1), или... (0, 2, 1) –– каким путем ни иди! А на следующем шаге? (2, 1, 0). И на следующем шаге опять вернемся в исходное состояние (1, 0, 2). В общем-то понятно: с точки зрения остатков у нас совершается такое преобразование за один ход: к каждому остатку прибавляется 2 (или, что то же самое, с точки зрения остатков при делении на три –– отнимается по единице). Теперь понятно, что никогда три нуля мы не получим.
Промежуточное решение найдено. Теперь совсем нетрудно очистить его до конца: инвариант –– это разность между первым и вторым членом, взятая по модулю три. Она –– всегда единица. Это и есть нужный инвариант, который и покажет, что получить всех хамелеонов одного цвета не удастся (для них значение инварианта равно 0).
Задача 038. В классе 25 столов, расставленных в виде квадрата в пять рядов по пять столов в каждом. Учитель хочет, чтобы все поменялись местами по такому правилу: каждый переходит за стол, находящийся слева или справа от него, или за стол, находящийся перед ним или позади него. Можно ли осуществить это?
Решение:
Изобразим класс с 25 столами в виде шахматной доски, как показано на рисунке.
Чтобы ученики соблюдали правило учителя, им нужно переходить с закрашенного стола на не закрашенный или наоборот. Однако у нас 13 закрашенных столов и только 12 не закрашенных. Таким образом, пересаживание по правилу учителя невозможно.
Задача 039. Имеются двое песочных часов: на 7 минут и на 11 минут. Каша должна вариться 15 минут. Как сварить кашу, переворачивая часы минимальное число раз?
Решение:
Следует составить соответствующее равенство, связывающее числа 7, 11 и 15. Заметим, что 15=2·11−7. Перепишем это равенство в виде 15=(11−7)+11 и опишем наши действия.
1) Переворачиваем одновременно песочные часы.
2) В тот момент, когда в 7-минутных часах закончится песок, в 11-минутных часах останется песка ровно на 4 минуты, начинаем варить кашу.
3) Когда в 11-минутных часах закончится песок (прошло 4 минуты с момента начала варки каши), переворачиваем их.
4) Когда во второй раз закончится песок в 11-минутных часах — каша готова.
Ответ: 15=11−7+11.
Задача 040. В классе 24 ученика. Каждый из учеников класса занимается не более чем в двух кружках, причем для любых двух учеников существует кружок, в котором они занимаются вместе. Докажите, что найдется кружок, в котором занимаются не менее 16 учеников.
Решение:
Если в некоторый кружок ходит весь класс, то все доказано. Далее будем считать, что такого кружка нет.
Пусть самый многочисленный кружок — математический. Его участников мы будем называть математиками. Поскольку не весь класс ходит в этот кружок, найдется ученик Петров, который в него не ходит. Рассмотрим его и одного из математиков. Они вместе ходят в другой кружок, допустим в физический (физики). Петров не может ходить в этот кружок вместе со всеми математиками, иначе математический кружок не будет самым многочисленным. Значит, с кем-то из математиков он ходит еще в один кружок, например, литературный (лирики).
Поскольку Петров занимается не более чем в двух кружках, то математики не могут заниматься больше ни в каких других кружках. Значит, каждый математик может еще быть только либо физиком, либо лириком, а Петров является физиком и лириком одновременно. То, что было сказано про Петрова, можно сказать и про любого другого ученика, который не является математиком: каждый из таких учеников — физик и лирик одновременно (и больше ни в какие кружки не ходит).
Таким образом, кружков всего три, и каждый ученик ходит ровно в два кружка. Так как в классе 24 ученика, то на три кружка в общей сложности приходится 48 их участников. Поэтому в математический кружок (самый многочисленный) ходит не менее чем 48:3=16 учеников. (В этой задаче крайним был самый многочисленный кружок).