Работа 21. Разные задачи – II 1 Что больше: 2009 2010 или 2010 2011 ? 2 Напишите, используя каждую из цифр 1, 2, 3, 4 ровно два ра- за, восьмизначное число, у которого между единицами стоит ровно 1 цифра, между двойками — ровно 2 цифры, между тройками — ровно 3 и между четверками — ровно 4 цифры. 3 Миша, Антон и Стёпа решали задачки. Миша сказал: «Я решил больше всех задач». Антон усомнился: «Либо ты решил не больше всех, либо Стёпа меньше всех». Стёпа сказал: «Я решил больше задач, чем Антон». Кто решил больше всех задач, если прав только один из мальчиков? Ответ объясните. 4 Денежной единицей коротышек является фертинг. В данный момент 1 фертинг стоит 3 руб. 55 коп. Сколько фертингов стоит 1 рубль? (Фертинг разменивается на 100 сантиков, при нецелом числе сантиков округление происходит в большую сторону.) 5 Решите ребус: ТИК+ТАК=АКТ. Буквами зашифрованы циф- ры. Одинаковые буквы обозначают одинаковые цифры, разные бук- вы — разные цифры. 6 Пятеро по очереди ели торт. Первый съел пятую его часть, вто- рой — четверть остатка, третий — треть нового остатка, четвертый — половину того, что осталось после третьего, а пятый доел торт до конца. Кто из них съел больше всех? 7 В Циссильвании 1000 жителей. Трое из них — вампиры, но мало кому известно, кто именно. Заезжий писатель м-р Стокер попросил каждого жителя назвать двух человек, которые, по его мнению, яв- ляются вампирами. Каждый вампир назвал двух других вампиров, а остальные могли назвать кого угодно. Докажите, что, пользуясь данными опроса (и зная, что вампиров в Циссильвании ровно трое), м-р Стокер может выбрать себе проводника, не являющегося вам- пиром. 8 В однокруговом футбольном турнире (каждая команда с каж- дой сыграла ровно по одному матчу) участвовало 7 команд. По итогам турнира оказалось, что команды, занявшие призовые места, набрали ровно половину всех очков. Могло ли по итогам турнира оказаться ровно 6 ничьих? (за победу даётся 3 очка, за ничью — 1, за поражение — 0) Ответы и решения 1 Ответ: 2010 2011 больше. Решение. Первая дробь на 1 2010 меньше числа 1, а вторая на 1 2011 . Т.к. 1 2010 > 1 2011 , то вторая дробь больше. 2 Ответ: 23421314. 3 Ответ: Антон. Решение. Рассмотрим два случая. Если Миша прав, то он первый. Поскольку прав только один, то Стёпа неправ. Значит, второй — Антон, а Стёпа — третий. Но тогда утверждение Антона верно. Получаем, что всего было два верных высказывания, что противоречит условию задачи. Значит, этот случай невозможен. Если Миша неправ, то он не первый. Тогда утверждение Антона верно. Получается, что утверждение Стёпы должно быть неверным. Значит, он, как и Миша, не может быть первым. Тогда Антон — пер- вый. Нетрудно проверить, что эта ситуация удовлетворяет условию задачи. 4 Ответ: 28 сантиков. Решение. Тогда рубль стоит 1 3, 55 = 0, 281 . . . фертингов. 5 Ответ: 216+246=462, 261+251=512, 432+492=924. Решение. Заметим, что Т — четное, так как оно равно последней цифре суммы (К+К). С другой стороны, Т≤ 4, так как иначе АКТ не может быть трёхзначным числом. Таким образом, Т=2 или Т=4. Если Т=2, то К=1 или К=6. В первом случае, нетрудно прове- рить, что А=5, а И=6. Во втором случае, А=4 (тогда И=1) или А=5 (тогда И не может быть однозначным числом — противоречие). Если Т=4, то К=2 или К=7. В первом случае, А=9, а И=3. А второй случай, как нетрудно проверить, к решению не приводит. 6 Ответ: все съели поровну. Решение. Первый съел 1 5 . Осталось 1 − 1 5 = 4 5 . 80 Второй съел 4 5 · 1 4 = 1 5 . Осталось 4 5 − 1 5 = 3 5 . Третий съел 3 5 · 1 3 = 1 5 . Осталось 3 5 − 1 5 . Четвертый съел 2 5 · 1 2 = 1 5 . Осталось 2 5 − 1 5 = 1 5 . Пятый съел 1 5 . Таким образом, все съели поровну. 7 Решение. Известно, что все вампиры указали друг на друга. Значит, они образуют тройку, внутри которой каждый показывает на двух других. Любой житель может входить не более, чем в одну такую тройку. Все жители не могут разбиться на такие тройки, так как их количество не делится на 3. Поэтому найдётся житель, не вошедший в такую тройку. Значит, он не является вампиром. 8 Ответ: нет, не могло. Решение. Всего игр было сыграно 7 · 6 2 = 21. Если всего было 6 ничьих, то всего команды набрали (21 − 6) · 3 + 6 · 2 = 45 + 12 = 57 очков. Но тогда первые три команды набрали 57/2 = 28.5 очков, чего не может быть. 81 Работа 22. Составление уравнений 1 Решите уравнение (x : 2 − 3) : 2 − 1 = 3. 2 Деду 56 лет, внуку — 14. Через сколько лет дедушка будет вдвое старше внука? 3 Упаковка чая на 50 копеек дороже пакета кофе. Вася купил 7 упаковок чая и 6 пакетов кофе, потратив 68 рублей 50 копеек. Сколько стоит пакет кофе? 4 9 одинаковых тетрадок стоят 11 рублей с копейками, а 13 таких же тетрадок — 15 рублей с копейками. Сколько стоит одна тетрад- ка? 5 Представьте число 45 в виде суммы четырёх чисел так, что после прибавления 2 к первому числу, вычитания 2 из второго, умножения на 2 третьего и деления на 2 четвёртого эти числа станут равными. 6 В трёх ящиках лежат орехи. В первом на 6 орехов меньше, чем в двух других вместе, а во втором на 10 орехов меньше, чем в первом и третьем. Сколько орехов в третьем ящике? 7 Вифсла, Тофсла и Хемуль играли в снежки. Первый снежок бросил Тофсла. Затем в ответ на каждый попавший в него сне- жок Вифсла бросал 6 снежков, Хемуль — 5, а Тофсла — 4. Через некоторое время игра закончилась. Найдите, в кого сколько снеж- ков попало, если мимо цели пролетели 13 снежков. (В себя самого снежками не кидаются.) 8 Ваня 28 ноября сказал: «Сегодня разность между числом про- житых мною полных месяцев и числом полных лет впервые стала равна 144». Когда у Вани День рождения? Ответы и решения 1 Ответ: 22. Решение. Делаем всё в обратном порядке: (x : 2 − 3) : 2 − 1 = 3 (x : 2 − 3) : 2 = 4 x : 2 − 3 = 8 x : 2 = 11 x = 22. 2 Ответ: через 28 лет. Решение. Пусть это произойдёт через x лет. Тогда 56 + x = 2 · (14 + x) 56 + x = 28 + 2x 28 = x. 3 Ответ: 5 рублей. Решение. Пусть пакет кофе стоит x рублей, тогда упаковка чая стоит x + 0, 5. Значит, 7 · (x + 0, 5) + 6x = 68, 5 7x + 3, 5 + 6x = 68, 5 13x = 65 x = 5. 4 Ответ: 1 руб. 23 коп. Решение. Обозначим за x рублей цену одной тетрадки. Тогда усло- вие задачи можно переписать так: 11 < 9x < 12, 15 < 13x < 16. 83 Из левого неравенства первого соотношения следует, что 1, 222 . . . < x, а из правого неравенства второго соотношения x < 1, 230... < 1, 24. Значит, тетрадка стоит больше, чем 1 руб. 22 коп., и меньше, чем 1 руб. 24 коп. Единственно возможный вариант 1 руб. 23 коп. 5 Ответ: 8 + 12 + 5 + 20 = 45. Решение. Пусть в итоге все числа стали равны x. Тогда изначально числа были равны x − 2, x + 2, 0, 5x, 2x. По- лучается, что x − 2 + x + 2 + 0, 5x + 2x = 45 4, 5x = 45 x = 10. 6 Ответ: 8 орехов. Решение. Обозначим количество орехов в ящиках x, y, z соответ- ственно. Тогда получаем, что x + 6 = y + z, y + 10 = x + z. Сложим эти два равенства x + y + 16 = x + y + 2z 16 = 2z z = 8. Значит, в третьем ящике 8 орехов. 7 Ответ: в каждого попало по 1 снежку. Решение. Если в Вифслу, Тофслу и Хемуля попали x, y и z снежков соответственно, то всего было брошено 13 + x + y + z снежков (поскольку 13 снежков не достигли цели). С другой стороны, Вифсла бросил 6x, Хемуль — 5y, а Тофсла — (4z + 1) снежков (вместе с первым). Получаем уравнение 6x + 5y + 4z + 1 = 13 + x + y + z 5x + 4y + 3z = 12 Так как x, y, z — целые неотрицательные числа, то x может быть равен 1 или 2, y — 1, 2 или 3, z — 1, 2, 3 или 4. Перебором находим единственное решение x = 1, y = 1, z = 1. 8 Ответ: 28 октября. Решение. Пусть с того момента, как Ваня родился, до 28 ноября этого года прошло x лет и ещё y месяцев (y от 0 до 11). Значит, полных месяцев всего прошло 12x + y. Тогда 12x + y − x = 144 11x + y = 144 11x = 144 − y Значит, 144 − y делится на 11. Но единственное подходящее из воз- можных y равно 1. Получается, что День рождения у Вани за 1 месяц до 28 ноября, то есть, 28 октября. Работа 23. Геометрические конструкции 1 У двух человек было два квадратных торта. Каждый сделал на своём торте по два прямолинейных разреза от края до края. При этом у одного получилось три куска, а у другого — четыре. Могло ли такое быть? 2 На рисунке изображена развертка кубика. На ней проставлены только числа: 1 и 2. Расставьте остальные числа: 3, 4, 5, 6 — так, чтобы сумма чисел на любых двух противоположных гранях была равна 7. 1 2 3 Можно ли на плоскости отметить 6 точек и соединить их отрез- ками так, чтобы каждая была соединена ровно с четырьмя други- ми? 4 Верно ли, что среди любых пяти отрезков найдутся три, из ко- торых можно составить треугольник? 5 Кролик, готовясь к приходу гостей, повесил в трёх углах своей многоугольной норы по лампочке. Пришедшие к нему Винни-Пух и Пятачок увидели, что не все горшочки с мёдом освещены. Когда они полезли за мёдом, две лампочки разбились. Кролик перевесил оставшуюся лампочку в некоторый угол так, что вся нора оказалась освещена. Могло ли такое быть? 6 Поставьте на плоскости 9 точек так, чтобы никакие 4 не лежали на одной прямой, но из любых 6 нашлись 3, лежащие на одной прямой. (На рисунке проведите все прямые, на которых лежат по три отмеченные точки.) 7 Каждую грань куба разбили на четыре одинаковых квадрата Можно ли каждый из получившихся квадратов покрасить в один из трёх цветов так, чтобы любые два квадрата, имеющие общую сторону, были покрашены в разные цвета? 8 На клетчатой бумаге отмечен прямоугольник размером 2 × 6. Можно ли раскрасить узлы клеток, лежащие на границе и внутри этого прямоугольника (всего их 21), в два цвета так, чтобы никакие четыре одноцветных узла не оказались в вершинах прямоугольника со сторонами, идущими вдоль линий сетки? Ответы и решения 1 Ответ: да, могло. Решение. 2 Решение. 1 2 3 4 6 5 3 Ответ: да, можно. Решение. 4 Ответ: нет, не верно. 88 Решение. Пусть отрезки имеют длины 1, 2, 4, 8, 16. Нетрудно видеть, что для любых трех отрезков a < b < c верно, что a+b < c. Значит, треугольник составить не удастся. 5 Ответ: да, могло. Решение. Пример см. на рис. Лампочки обозначены кружочками. 6 Решение. Далее несложным перебором легко показать, что данная конфигу- рация удовлетворяет условию. 7 Ответ: да, можно. Решение. 89 3 1 1 3 2 1 1 2 3 1 1 3 2 1 1 2 2 3 3 2 2 3 3 2 8 Ответ: нет, нельзя. Решение. Разобьем прямоугольник из условия на 7 троек из 3 вертикальных точек. Заметим, что если какие-то две тройки сов- падают, то найдется искомый прямоугольник, т.к. в каждой тройке одного из двух цветов хотя бы 2 точки. Всего таких комбинаций 2 · 2 · 2 = 8. Осталось заметить, что если выбрана комбинация из трех точек цвета 1, то не выбраны еще хотя бы 3 тройки(в каж- дой из них ровно две точки цвета 1). Таким образом, найдутся две одинаковые тройки. Работа 24. Принцип крайнего 1 По кругу выписано несколько натуральных чисел, каждое из которых не превосходит одного из соседних с ним. Докажите, что среди этих чисел точно есть хотя бы два равных. 2 По кругу выписано несколько чисел, каждое из которых равно среднему арифметическому двух соседних с ним. Докажите, что все эти числа равны. 3 8 грибников собрали 37 грибов. Известно, что никакие двое не собрали грибов поровну и каждый нашёл хотя бы один гриб. До- кажите, что какие-то двое из них собрали больше, чем какие-то пятеро. 4 На шахматной доске стоят несколько ладей. Обязательно ли най- дется ладья, бьющая не более двух других? (Перепрыгивать через другие фигуры ладья не может.) 5 В стране есть несколько городов. Сумасшедший путешественник едет из города A в самый далёкий от него город B. Затем едет в самый далёкий от B город C и т.д. Докажите, что если город C не совпадает с городом A, то путешественник никогда не вернётся обратно в город A. 6 В космическом пространстве летают 2011 астероидов, на каж- дом из которых сидит астроном. Все расстояния между астероида- ми различны. Каждый астроном наблюдает за ближайшим астеро- идом. Докажите, что за одним из астероидов никто не наблюдает. 7 Гоша задумал четыре неотрицательных числа и посчитал их всевозможные попарные суммы (всего 6 штук). Какие числа он за- думал, если эти суммы — 1, 2, 3, 4, 5, 6? Ответы и решения 1 Решение. Рассмотрим наибольшее из этих чисел(или одно из них, если таких чисел несколько). Так как оно не меньше и не боль- ше одного из своих соседей, то оно равно ему. Мы нашли пару рав- ных чисел. 2 Решение. Рассмотрим наибольшее из этих чисел(или одно из них, если таких чисел несколько). Из того, что оно не меньше сво- их соседей и равно их среднему арифметическому, следует, что оно равно своим соседям. Проводя аналогичные рассуждения, получа- ем, что все числа равны. 3 Решение. Пронумеруем грибников так, чтобы первый набрал больше всех грибов, второй больше среди оставшихся и т.д. Ясно, что первый не мог набрать меньше 9 грибов, т.к. тогда бы все вместе набрали максимум 1 + . . . + 8 = 36 < 37 грибов. Также второй не мог набрать меньше 7 грибов. Значит, первый и второй вместе набрали хотя бы 7+ 9 = 16 грибов. Учитывая то, что третий набрал хотя бы 6 грибов, то 4-й, 5-й, . . . , 8-й набрали вместе максимум 37 − 16 − 6 = 15 < 16 грибов 4 Ответ: да, обязательно. Решение. Рассмотрим самую верхнюю ладью, если таких несколь- ко, то самую левую из них. Тогда выше и левее этой ладьи нет других ладей, значит, она бьет не более двух других. 5 Решение. Предположим, что на втором шаге путешественник не возвратился в A, т.е. город C отличен от города A. Тогда марш- рут от A до B короче маршрута из B в C (поскольку C — наиболее удаленный от B город). В дальнейшем каждый следующий марш- рут будет не короче предыдущего, так как каждый раз мы в каче- стве следующего пункта назначения выбираем наиболее удаленный город. Пусть на некотором шаге путешественник все же вернулся в город A, выйдя из некоторого города X. По доказанному, маршрут от X до A длиннее маршрута от A до B, а это противоречит тому, что B — наиболее удаленный от A город. 6 Решение. Рассмотрим два астероида A и B, расстояние между которыми наименьшее. Астроном на астероиде A смотрит на астероид B, а астроном на астероиде B смотрит на астероид A. Если найдется астроном, который смотрит на астероид A или B, то найдется астероид на которого никто не смотрит. В противном случае исключим из рассмотрения астероиды A и B. Получим систему из 2011 − 2 = 2009 астероидов, для которых очевидно выполняется условие задачи. Продолжая так далее, придем к случаю трех астероидов. Выбрав, среди них два, расстояние между которыми наименьшее получим, что на оставшийся астероид никто не смотрит. 7 Ответ: 0, 1, 2, 4. Решение. Пусть Гоша задумал числа a > b > c > d > 0. Все суммы различны, поэтому самая маленькая из посчитанных сумм — c + d, следующая за ней — d + b, также самая большая — a + b, а следующая за ней — a + c. Значит, c + d = 1, d + b = 2, a + b = 6, a + c = 5. Тогда c = 1 − d, b − c = 1, b = c + 1 = 2 − d, a = 5 − c = 4 + d. Заметим, что a + d = 4 + 2d и b + c = 3 − 2d есть числа 3 и 4 в некотором порядке. Число d неотрицательно, значит, a + d ≥ 4 и b + c ≤ 3, значит, d = 0,тогда c = 1, b = 2, a = 4. Работа 25. Клетчатые задачи 1 Можно ли в квадрате 7 × 7 закрасить некоторые клетки так, чтобы в любом квадрате 2×2 была ровно одна закрашенная клетка? 2 а) Можно ли в клетках шахматной доски расставить целые чис- ла так, чтобы сумма чисел в любом столбце была больше 100, а в любой строке — меньше 100? б) В клетках квадратной таблицы 10 × 10 стоят ненулевые цифры. В каждой строке и в каждом столбце из всех стоящих там цифр произвольным образом составлено десятизначное число. Может ли оказаться так, что из двадцати получившихся чисел ровно одно не делится на 3? 3 Можно ли в центры 16 клеток шахматной доски 8 × 8 вбить гвозди так, чтобы никакие три гвоздя не лежали на одной прямой? 4 В квадрате 7 × 7 закрасьте некоторые клетки так, чтобы в каж- дой строке и в каждом столбце оказалось ровно по 3 закрашенные клетки. 5 В клетках шахматной доски расставлены натуральные числа так, что в каждой строке и в каждом столбце сумма чисел чётна. Докажите, что сумма чисел в чёрных клетках будет чётна. 6 Можно ли шестиугольный торт разрезать на 23 равных куска по указанным линиям? 7 Каждая грань куба с ребром 4 см разделена на клетки со сторо- ной 1 см. Можно ли целиком оклеить 3 его грани, имеющие общую вершину, шестнадцатью бумажными прямоугольными полосками размером 1×3 так, чтобы границы полосок совпадали с границами клеток? 8 Бумага расчерчена на клеточки со стороной 1. Ваня вырезал из неё по клеточкам прямоугольник и нашёл его площадь и периметр. Таня отобрала у него ножницы и со словами «Смотри, фокус!» вы- резала с краю прямоугольника по клеточкам квадратик, квадратик выкинула и объявила: «Теперь у оставшейся фигуры периметр та- кой же, какая была площадь прямоугольника, а площадь — как был периметр!» Ваня убедился, что Таня права. а) Квадратик какого размера вырезала и выкинула Таня? б) Приведите пример такого прямоугольника и такого квадрата. в) Прямоугольник каких размеров вырезал Ваня? Ответы и решения 1 Ответ: да, можно. Решение. Возьмем квадрат 8 × 8 и закрасим в нем клетки, стоя- щие на пересечении столбца и строки с четным номером. Ясно, что у этого квадрата в любом квадрате 2 × 2 будет ровно одна закра- шенная клетка. Теперь выкинем правый столбец и верхнюю строку. Получим квадрат 7 × 7, удовлетворяющий условию. 2 а) Ответ: нет, нельзя. Решение. Посчитаем сумму всех чисел в таблице. Складывая по столбцам, получим, что она больше 800, а по строкам — получим, что меньше 800. б) Ответ: нет, не может. Решение. Ясно, что остаток суммы всех чисел по строкам равен остатку суммы всех чисел по столбцам и равен остатку суммы всех цифр в таблице при делении на 3. Если ровно одно из чисел не делится на 3, то суммы по строкам и по столбцам дают разные остатки, чего не может быть. 3 Ответ: да, можно. Решение. 4 Решение. 5 Решение. Покрасим доску так, как показано на рисунке. Тогда черные клетки перекрасятся в синий и зеленый цвета, а белые — в красный и желтый. Заметим, что если сумма двух чисел четна, то эти числа одной четности. Значит, в каждом столбце и в каждой строке четность суммы цифр на белых клетках совпадает с четностью суммы на черных. Поэтому четность суммы зеленых чисел совпадает с чет- ностью красных. А четность суммы красных совпадает с четностью суммы синих. Тогда сумма синих чисел совпадает с четностью сум- мы зеленых, а, значит, сумма чисел в черных клетках четна. 6 Ответ: нельзя. Решение. Раскрасим фигуру так, как изображено на рисунке. Ес- ли разрезание возможно, то в куске будет два треугольника: черный и белый (всего их 46), то есть черных и белых треугольников долж- но быть поровну. Но на рисунке черных треугольников 21, а белых — 25, следовательно, требуемое разрезание невозможно. 7 Ответ: нельзя. Решение. Закрасим 27 квадратиков указанных граней так, как по- казано на рисунке. Тогда любая полоска 3×1 закрывает четное чис- ло закрашенных квадратиков. Поэтому заклеить данные три грани полосками так, как требуется в условии, не удастся. 8 Ответ: а) 2 × 2; б) см. рис.; в) 3 × 10 или 4 × 6. Решение. а) Квадратик не мог иметь общий угол с прямоугольником (см. рис.), так как тогда периметр остался бы прежним или уменьшился, а площадь бы уменьшилась. Значит, квадрат примыкает только к одной из сторон прямоугольника (см. рис.). Пусть сторона квадрата x. Тогда Таня, вырезав квадрат, уменьшила площадь фигуры на x, при этом периметр увеличился на две стороны квадрата, то есть на 2x. Таким образом, исходная площадь−x 2 = площадь полученной фигуры, исходный периметр+2x = периметр полученной фигуры. По условию исходная площадь = периметр полученной фигуры, исходный периметр = площадь полученной фигуры. Отсюда исходная площадь −x 2 = исходный периметр, исходный периметр +2x = исходная площадь. Значит, x 2 = 2x, откуда x = 2. 99 б) в) Пусть стороны прямоугольника m и n. Тогда из решения пунк- та а) следует, что mn = 2m + 2n + 4. Наша задача — найти все возможные пары чисел m и n, удовлетворяющие этому равенству. Равенство mn = 2m+2n+4 можно записать в виде (n−2)(m−2) = 8. Поскольку m и n превосходят 2, задача сводится к поиску разло- жений числа 8 на два натуральных множителя. Работа 26. Примеры и контрпримеры Если утверждение верно всегда, то докажите его, а если хоть в одном случае неверно, то покажите, что это за случай (приведите контрпример). 1 Приведите контрпример к каждому из следующих утвержде- ний. а) Все числа, делящиеся на 4 и на 6, делятся на 24. б) Все прямоугольники являются квадратами. в) Все четырехугольники, у которых все стороны равны, являются квадратами. 2 Вася думает, что если площадь первого прямоугольника боль- ше площади второго, а также периметр первого больше периметра второго, то из первого можно вырезать второй. Прав ли он? 3 Гриб называется плохим, если в нем не менее 10 червей. В лу- кошке 90 плохих и 10 хороших грибов. Могут ли все грибы стать хорошими после того, как некоторые черви переползут из плохих грибов в хорошие? 4 Выберите 24 клетки в прямоугольнике 5 × 8 и проведите в каж- дой выбранной клетке одну из диагоналей так, чтобы никакие две проведенные диагонали не имели общих концов. 5 Барон Мюнхгаузен утверждает, что может для некоторого N так переставить числа 1, 2, . . . , N в другом порядке и затем выписать их все подряд без пробелов, что в результате получится многозначное число-палиндром (оно читается одинаково слева направо и справа налево). Не хвастает ли барон? 6 На доске написаны три различных числа от 1 до 9. Одним ходом разрешается либо прибавить к одному из чисел 1, либо вычесть из всех чисел по 1. Верно ли, что всегда можно добиться того, чтобы на доске остались только нули, сделав не более 23 ходов? 7 Рома придумал теорему: Если число A является квадратом на- турального числа B, а также каждая цифра числа A делится на 3, то и каждая цифра числа B делится на 3. Верна ли ромина теорема? 101 Ответы и решения 1 Ответ: а) 12; б) прямоугольник со сторонами 1 и 2; в) ромб, не являющийся квадратом. 2 Ответ: нет, не прав. Решение. Из прямоугольника 1 × 100 нельзя вырезать квадрат 2 × 2. 3 Ответ: могут. Решение. Пусть в каждом плохом грибе ровно 10 червей, а в хоро- шем червей нет. Далее, пусть из каждого плохого гриба по одному червю переползут в хорошие, по 9 в каждый. В результате в каждом грибе окажется по 9 червей, и все грибы будут хорошими. 4 Решение. 5 Ответ: нет, не хвастает. Решение. Числа можно выписать, например, так 9.18.7.16.5.14.3.12.1.10.11.2.13.4.15.6.17.8.19 Объясним, почему нужно искать пример для N ≥ 19. В палин- дроме количество всех цифр, кроме, быть может, одной, должно быть четным. Однако если N = 2, . . . , 9, то цифры 1 и 2 встречают- ся в записи чисел 1, 2, . . . , N по одному разу, а если N = 10, . . . , 18, то по 1 разу встречаются цифры 0 и 9. 6 Ответ: неверно. Решение. Пусть вначале на доске написаны числа 1, 2 и 9, и через несколько ходов из них получились нули. Если из 9 в результате получился ноль, то вычитание производилось хотя бы девять раз. Значит, и из остальных чисел вычиталось хотя бы по девять единиц; значит, к 1 надо было сделать не меньше восьми прибавлений, а к двойке не меньше семи. Итоговое количество ходов, таким образом, не меньше 9 + 8 + 7 = 24. 7 Ответ: неверна. Решение. Например, для B = 264, 813. 2642 = 69696, 8132 = 660969. Работа 27. Логика – II 1 Петя сказал: «Если кот шипит, то рядом собака, и наоборот, если собаки рядом нет, то кот не шипит». Не сказал ли Петя чего- то лишнего? 2 Вася написал на доске натуральное число. После этого Катя и Маша сказали: —У этого числа четная сумма цифр. —У этого числа число нечетных цифр нечетно. Сколько среди этих утверждений верны? 3 Среди 5 школьников A,B,C,D,E двое всегда лгут, а трое всегда говорят правду. Каждый из них сдавал зачет, причем все они знают, кто сдал зачет, а кто — нет. Они сделали следующие утверждения. A:«B не сдал зачет». B:«C не сдал зачет». C:«A не сдал зачет». D:«E не сдал зачет». E:«D не сдал зачет». Сколько из них зачет сдали? 4 В школе прошёл забег с участием 5 спортсменов, и все заняли разные места. На следующий день каждого из них спросили, какое место он занял, и каждый, естественно, назвал одно число от 1 до 5. Сумма их ответов оказалась равна 22. Какое наименьшее число врунишек было? 5 На острове живут племя рыцарей и племя лжецов. Однажды каждый житель острова заявил: «В моем племени у меня больше друзей, чем в другом». Может ли рыцарей быть меньше, чем лже- цов? 6 Четырехзначное чиcло таково, что все его цифры различны, а также известно, что числа 5860, 1674, 9432, 3017 содержат ровно по две цифры, принадлежащие этому числу, однако ни одна из них не стоит в том же месте, что и в этом числе. Найдите его. 7 2011 обитателей острова рыцарей и лжецов встали по кругу. Каждый из них по очереди произнес фразу: Оба мои соседа — лже- цы. Если про рыцаря солгали, он обижается и становится лжецом. Если про лжеца сказали правду, он расстраивается и становится рыцарем. Когда лжецов было больше — в начале, или в конце? 8 В поселке некоторые дома соединены проводами. Соседями на- зываются двое, дома которых связаны проводом. Всегда ли удастся поселить в каждый дом по одному человеку: лжецу или рыцарю — так, чтобы каждый на вопрос: «Есть ли среди ваших соседей лже- цы?» ответил положительно? (Каждый знает про каждого из своих соседей, лжец он или рыцарь). Ответы и решения 1 Ответ: сказал. Решение. Если бы собаки рядом не было, а кот бы зашипел, то собака должна была бы быть рядом, а это не так. Поэтому вторая часть утверждения никакого смысла в себе не несет. 2 Ответ: одно. Решение. Заметим, что второе утверждение означает, что у васи- ного числа нечетная сумма цифр. Поскольку сумма цифр может быть либо четной, либо нечетной, то верно только одно из утвер- ждений. 3 Ответ: двое. Решение. Поскольку все пять утверждений были сделаны про 5 разных школьников и три из них верны, то три школьника не сдали зачет. Два других утверждения ложны, поэтому соответствующие школьники зачет сдали. 4 Ответ: 2. Решение. Заметим, что сумма ответов тех, кто ответил честно, не больше 1 + 2 + 3 + 4 + 5 = 15. Т.к. 22 − 15 = 7 > 5, то хотя бы двое соврали. Пример ответов: 5,5,3,4,5 (последние трое ответили честно). 5 Ответ: да, может. Решение. Пусть есть четверо рыцарей, которые попарно дружат. А также четыре пары лжецов, где лжецы каждой пары дружат со своим рыцарем, а друг с другом не дружат. Также никакие два лжеца не дружат. 6 Ответ: 4306. Решение. Пусть искомое число abcd . Для каждой цифры a, b, c, d посчитаем, сколько раз она встречается в данных четырех числах. Очевидно, что сумма этих вхождений должна равняться 8. По- скольку никакая цифра не встречается в 3 числах, то каждая цифра встречается ровно дважды. Т.е. в искомом числе могут быть только цифры 0,1,3,4,6,7. Но в первом числе из этих цифр есть только 6 и 0. Значит, эти цифры в числе точно есть. Аналогично из третьего числа, получаем цифры 4 и 3. Составим табличку, в которой плюсики стоят в тех разрядах, в которых они могут быть написаны. 0 + − + − 3 − + − + 4 + − + − 6 + − − + Очевидно, что т.к. в разряде сотен есть только один «+», то в разряде сотен числа стоит тройка. Действуя так далее и восполь- зовавшись тем, что четырехзначное число с нуля не начинается, получим число 4306, которое, очевидно, подходит. 7 Ответ: поровну. Решение. Рассмотрим некоторого человека. Заметим, что поме- нять статус он может только, когда произносят фразы его соседи. Предположим, что он был школьником. Тогда после первого соседа он станет студентом, а после второго — школьником. Если же он был студентом, то после первого соседа он станет школьником, а за- тем — снова студентом. Значит, сколько школьников было, столько и осталось. 8 Ответ: да, всегда. Решение. Рассмотрим наибольшее подмножество A домов, ника- кие два из которых не являются соседними. Поселим в каждый дом множества A лжеца, а во все остальные — по рыцарю. Тогда заме- тим, что у каждого рыцаря есть сосед – лжец, иначе бы дом этого рыцаря можно было бы добавить в множество A. По построению ни у какого лжеца нет соседей – лжецов. Работа 28. Расстановки ладей 1 а) Расставьте 8 ладей на шахматной доске так, чтобы они не били друг друга, тремя разными способами. б) А сколько всего таких способов? 2 Ладья стоит на поле a1 шахматной доски. Может ли она обойти всю доску, побывав в каждой клетке ровно один раз и закончив в клетке h8? (Ладья может перепрыгивать через клетки, в которых уже побывала.) 3 На шахматную доску поставили несколько ладей произвольным образом. Докажите, что точно найдётся ладья, бьющая не более двух других. 4 На шахматной доске стоят 8 ладей, никакие две из которых не бьют друг друга. Докажите, что количество ладей в левом верхнем квадрате 4 × 4 равно количеству ладей в правом нижнем квадрате 4 × 4. 5 На шахматной доске стоят 8 ладей, никакие две из которых не бьют друг друга. Докажите, что число ладей, стоящих на чёрных полях, чётно. 6 На шахматной доске 4×4 расположена фигура «летучая ладья», которая ходит так же, как обычная ладья, но не может за один ход встать на поле, соседнее с предыдущим. Может ли она за 16 ходов обойти всю доску, побывав в каждой клетке по разу, и вернувшись на исходное поле? 7 На полях a1, a2 и b1 шахматной доски стоят соответственно бе- лая, чёрная и красная ладьи. Разрешается делать ходы по обычным правилам, однако после любого хода каждая ладья должна быть под защитой какой-нибудь другой ладьи (т.е. в одной горизонтали или вертикали с другой ладьёй). Сколько ещё других расстановок этих ладей можно получить из исходной расстановки? 8 На шахматную доску по очереди выставляются ладьи так, что каждая нечётная по очереди выставленная ладья никого не бьёт, а каждая чётная бьёт ровно одну выставленную ранее. Какое наи- большее количество ладей можно поставить на доску по этим пра- вилам? Ответы и решения 1 а) Решение. Можно поставить ладей вдоль одной из главных диагоналей. Два других способа из первой расстановки можно по- лучить перестановкой столбцов. б) Ответ: 8!. Решение. Заметим, что любую такую расстановку можно полу- чить перестановкой столбцов из расстановки ладей по диагонали. Причем разные перестановки задают разные расположения. Всего перестановок 8 столбцов — 8!. 2 Ответ: да, может. Решение. 3 Решение. Выберем самую левую ладью среди самых верхних. Очевидно, что левее и выше ее нет ладей. Значит, она бьет не более двух ладей. 4 Решение. Заметим, что в любых четырех столбцах и любых четырех строках ровно по 4 ладьи. Но тогда сумма количеств ла- дей в левом нижнем квадрате и правом нижнем совпадает с суммой количеств ладей в правом нижнем и правом верхнем квадрате. От- куда следует, что количество ладей в левом верхнем квадрате 4 × 4 равно количеству ладей в правом нижнем квадрате 4 × 4. 5 Решение. Поскольку любую расстановку ладей можно полу- чить из диагональной последовательными перестановками соседних столбцов, то достаточно проверить, что из расстановки ладей, при которой на черных клетках стоит четное число ладей, получается расстановка с тем же свойством. Заметим, что при такой перестановке каждая ладья меняет цвет поля. Но тогда четность ладей на черных клетках не меняется. 6 Ответ: да. Решение. 5 11 6 12 1 15 2 16 8 10 7 9 4 14 3 13 7 Ответ: 9407. Решение. Заметим, что эти три ладьи всегда располагаются в трёх клетках, лежащих в углах некоторого прямоугольника со сторона- ми, параллельными сторонам доски («квартета» из четырёх клеток, находящихся на пересечении двух горизонталей и двух вертикалей). При этом их порядок по часовой стрелке совпадает с исходным, т.е. белая, чёрная и красная ладьи. Нетрудно убедиться, что возможно любое из таких расположений. Для этого ладьи сначала сдвигаются в три угла такого квартета (передвигаются в две вертикали, потом в две горизонтали квартета, сохраняя друг друга под защитой), а затем перемещаются по очереди по часовой стрелке через свобод- ный угол. Всего существует (8 · 7/2)2 = 282 = 784 таких квартетов, что определяется выбором двух горизонталей и двух вертикалей, на пересечении которых и будут находиться четыре угла соответ- ствующего прямоугольника. В каждом таком прямоугольнике су- ществуют 4 · 3 = 12 расстановок ладей по часовой стрелке, т.к. ла- дьи всегда образуют уголок, в центральной клетке которого может находиться любая ладья (3 варианта), а сама центральная клетка может находиться в любом из углов квартета (4 варианта). Учиты- вая исходный вариант, получим всего 784·12−1 = 9407 расстановок. 8 Ответ: 10. Решение. Пример, см. на рисунке: Докажем, что больше 10 ладей расставить не удастся. Каждая нечёт- ная по номеру ладья бьёт ровно 4 новые стенки из 32 = 4·8 стенок на доске (сторон граничных клеток), а каждая чётная ладья бьёт ров- но 2 новые стенки, т.к. две стенки ряда (строки-столбца), в котором эта ладья стоит вместе с побитой ею ладьёй, уже были ранее по- биты той ладьёй. Значит, каждая пара подряд выставленных ладей бьёт ровно 6 новых стенок, тогда можно выставить ровно [32/6] = 5 пар ладей (всего 10 ладей), после чего останется ровно 32−5 · 6 = 2 непобитые стенки, которых уже не хватит для появления на доске 11-й ладьи, т.к. ей надо 4 новые стенки. Работа 29. Длины и расстояния 1 Отрезок, равный 28 см, разделён на три (возможно неравных) отрезка. Расстояние между серединами крайних отрезков равно 16 см. Найдите длину среднего отрезка. 2 На стороне AC треугольника ABC отметили точку E. Известно, что периметр треугольника ABC равен 25 см, треугольника ABE — 15 см, треугольника BCE — 17 см. Найдите длину отрезка BE. 3 Длина стороны AC треугольника ABC равна 3.8 см, длина сто- роны AB — 0.6 см. Известно, что длина BC — целое число. Чему она может быть равна? 4 Прямоугольник разбит на 9 меньших прямоугольников. Пери- метры четырёх из них указаны на рисунке. Найдите периметр пря- моугольника x. 10 x 11 12 13 5 Квадрат ABCD со стороной 2 и квадрат DEFK со стороной 1 стоят рядом на верхней стороне AK квадрата AKLM со стороной 3. Между парами точек A и E, B и F, C и K, D и L натянуты паутинки. Паук поднимается снизу вверх по маршруту AEF B и спускается по маршруту CKDL. Какой маршрут короче? 6 Один прямоугольник расположен внутри другого. Может ли так быть, что периметр внутреннего прямоугольника больше периметра внешнего? 7 На клетчатой бумаге нарисован квадрат со стороной 5. Можно ли его разрезать на пять частей одинаковой площади, проводя раз- резы только по линиям сетки так, чтобы суммарная длина разрезов была не больше 16? 8 Прямоугольник составлен из шести квадратов (см. рисунок). Найдите сторону самого большого квадрата, если сторона самого маленького равна 1. Ответы и решения 1. Ответ: 4 см. Решение. Заметим, что сумма половин двух крайних отрезков рав- на 28 − 16 = 12 см, значит, сумма их длин равна 2 · 12 = 24 см, но тогда длина среднего отрезка равна 28 − 24 = 4 см. 2. Ответ: 3.5 см. Решение. Сложим периметры треугольников ABE и BCE. С од- ной стороны, мы получим сумму периметра треугольника ABC и удвоенного отрезка BE, с другой — 32 см. Откуда следует, что 2BE = 32 − 25 = 7 см, и BE = 3.5 см. 3. Ответ: 4 см. Решение. Известно, что в треугольнике любая сторона меньше суммы двух других. Поэтому сторона BC меньше AB + AC = 3.8 + 0.6 = 4.4 см. Также BC + AC > AB, т.е. BC + 0.6 > 3.8, BC > 3.2 см. Получили что BC, длина которой целая, удовлетво- ряет неравенствам 4.4 > BC > 3.2, т.е. BC = 4 см. 4. Ответ: 11. Решение 1 (с использованием прямоугольника с периметром 11). Посмотрим на прямоугольники с периметром 11 и 12. Горизонталь- ные стороны у них равны, а сумма двух вертикальных сторон ниж- него на 1 больше вертикальных сторон верхнего. Это означает, что в последнем столбце, у среднего прямоугольника периметр на 1 мень- ше, чем у прямоугольника с периметром 13, т.е. 12. Применяя ана- логичные рассуждения для прямоугольников с периметрами 10 и 11, получим, что у x периметр равен 12 − 1 = 11. Решение 2 (без его использования). Заметим, что суммы пери- метров маленьких прямоугольников, стоящих в противополжных углах, равны. Тогда 12 + x = 10 + 13 = 23, откуда x = 11. 5. Ответ: никакой, маршруты равны. Решение. Заметим, что в обоих маршрутах есть отрезок длины 1 (в первом это отрезок EF, во втором — KD). Теперь нарисуем сетку так, чтобы все точки из условия оказались в узлах, а сто- роны квадратов были параллельны линиями сетки. Теперь можно заметить, что отрезки AE и CK равны, а также отрезки BF и DL равны. Получили, что оба маршрута равны. 6. Ответ: нет, не может. Решение. Назовем внутренний прямоугольник маленьким, а внеш- ний большим. Ясно, что если стороны маленького прямоугольника параллель- ны сторнам большого, то каждая сторона большого больше соот- вествующей стороны маленького, а, стало быть, периметр большого больше. Разберем случай, когда стороны маленького не параллельны сторонам большого. Опишем около маленького прямоугольника сред- ний прямоугольник так, чтобы стороны среднего были параллель- ны сторонам большого и вершины маленького лежали на сторонах среднего(см. рис.) Покажем, что периметр маленького прямоугольника меньше, чем периметр среднего. Действительно, поскольку кратчайший путь меж- ду точками — отрезок, то каждая красная сторона меньше суммы двух черных отрезков, образующих с ней треугольник. Сумма всех таких черных отрезков равна периметру среднего прямогуольни- ка. А то, что периметр среднего меньше периметра большого, мы доказали в первом случае. Значит, такого быть не могло. 7. Ответ: да, можно. Решение. Приведем пример. 8. Ответ: 7. Решение. Обозначим сторону квадрата, расположенного в левом нижнем углу за x. Тогда стороны других квадратов легко вычис- лить. Получится, как на рисунке. 1 x x x + 1 2x − 1 x + 2 Поскольку вертикальные стороны прямоугольника равны, то (2x − 1) + x = (x + 2) + (x + 1), т.е. 3x − 1 = 2x + 3, откуда x = 4. Значит, сторона самого большого квадрата равна 2·4−1 = 8−1 = 7. 115 Работа 30. Города и дороги 1 В некоторой стране а) 6; б) 20 городов, любые два из которых соединены дорогой. Сколько всего дорог в этой стране? в) Дока- жите, что если число городов равно n, то дорог n(n − 1) 2 . 2 В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник заметил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий делится на три. Можно ли добраться из города 1 в город 9? 3 В государстве 100 городов, и из каждого выходит по 4 дороги. Сколько всего дорог в государстве? 4 В Совершенном городе шесть площадей. Каждая площадь со- единена прямыми улицами ровно с тремя другими. Никакие две улицы в городе не пересекаются. Из трёх улиц, отходящих от каж- дой площади, одна проходит внутри угла, образованного двумя дру- гими. Начертите возможный план такого города. 5 Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка A на плане) до своего отеля (точка B). Он хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрёстке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет. 6 В стране 96 городов, из которых 24 — «областные». Некоторые пары городов соединены между собой дорогами (но не более чем од- ной), причём любой путь по дорогам между двумя обычными горо- дами, если он есть, проходит хотя бы через один «областной» город. Какое наибольшее количество дорог могло быть в этой стране? 7 В чемпионате России по футболу участвуют 16 команд. Любые две команды играют друг с другом два раза: по разу на поле каж- дого из соперников. а) Какое максимальное и какое минимальное количество очков может набрать команда, участвующая в чемпи- онате России? б) Какое минимальное и какое максимальное коли- чество очков могут набрать в сумме все команды? (В футболе за победу в матче даётся 3 очка, за ничью — 1 очко, за поражение — 0 очков.) 8 В шахматном турнире приняло участие несколько человек. Каж- дый сыграл с каждым ровно одну партию. Оказалось, что все, кро- ме Гоши, набрали одинаковое количество очков. Докажите, что Го- ша либо у всех выиграл, либо всем проиграл. (В шахматах за победу даётся 1 очко, за ничью — 1/2 очка, за поражению — 0 очков.) Ответы и решения 1 Ответ: а) 15; б) 190. Решение. Докажем в). Посчитаем пары городов. На первое место можно выбрать n городов, на второе уже n − 1 (так как город не может быть соединен сам с собой). Следовательно, всего пар n(n − 1). Заметим, что число дорог в два раза меньше числа пар, так как пару город А – город Б мы посчитали 2 раза (А-Б и Б-А). Значит, надо поделить на 2. Пункты а) и б) получаются подстановкой в формулу. 2 Ответ: нет, нельзя. Решение. По признаку делимости на 3 число делится на 3 только в том случае, когда сумма его цифр делится на 3. 1 не делится на 3. Следовательно, этот город может быть соединен только с городом, который на 3 тоже не делится и т.д. (Иначе получится, что сумма цифр не делится на 3, так как сумма кратного трем и не кратного не делится на 3). 9 делится на 3. Поэтому добраться из города в город нельзя. 3 Ответ: 200. Решение. В государстве 100 городов, из каждого выходит по 4 дороги. Значит, если мы умножим 100 на 4, то получим число дорог, умноженное на 2, так как каждую дорогу мы посчитали 2 раза, ведь дорога соединяет 2 города. Следовательно, число дорог равно 100 · 4 2 = 200. 118 4 Решение. План города может быть, например, таким. 5 Решение. Один из возможных маршрутов туриста изображён на рисунке. Двигаясь по этому пути, турист пройдёт 34 улицы (улицей мы называем отрезок между двумя соседними перекрёстками). Дока- жем, что более длинный маршрут невозможен. Всего в Старом горо- де 36 перекрёстков. Всякий раз, когда турист проходит очередную улицу, он попадает на новый перекрёсток. Таким образом, больше чем 35 улиц турист пройти не сможет (начальный перекрёсток A не считается). Покажем, что посетить 35 перекрёстков (и, следова- тельно, пройти 35 улиц) любознательный турист тоже не сможет. Для этого раскрасим перекрёстки в чёрный и белый цвета в шахматном порядке. Всякий раз, проходя улицу, турист попадает на перекрёсток другого цвета. И отель, и вокзал расположены на белых перекрёстках. Поэтому любой маршрут содержит чётное число улиц, а число 35 нечётно. 6 Ответ: 2004. Решение. Очевидно, что обычные города не соединены дорога- ми, иначе бы существовал путь не проходящий через областной го- род. Значит, максимальное число дорог в том случае, когда каждый обычный город соединен с каждым областным, и все областные со- единены между собой. Нетрудно убедиться, что ответ в таком слу- чае будет равен 24 · 23 2 + (96 − 24) · 24 = 276 + 1728 = 2004. 7 Ответ: а) 90 и 0 очков; б) 480 и 720 очков. Решение. а) Ясно, что наибольшее число очков команда может набрать, когда все матчи выиграет, а минимальное, когда все матчи проиграет. б) Если в матче одна из команд ожержит победу, то в сумме за матч будет разыграно 3 очка; если же ни одна из команд не выиграет, то в сумме будет разыграно два очка. Ясно, что можно добиться того, чтобы в каждом матче было разыграно 2 очка — каждый матч закончиться ничьей. Тогда будет разыграно всего 16· 15 · 2 = 480 очков. Максимальное число будет разыграно, когда в каждом матче одна из команд выиграет. В этом случае будет разыграно 16 · 15 · 3 = 720 очков. 8 Решение. Поменяем немного правила начисления очков: за по- 120 беду будем давать 2 очка, а за ничью 1 очко. Ясно, что после такой замены все условия задачи сохранятся и каждый из участников на- берет целое число. Будем считать, что в этом турнире всего участ- ников было n. Тогда все участники в сумме набрали n(n−1) очков. Пусть у тех участников, которые набрали равное число очков, по k очков, а у Гоши G очков. Тогда n(n − 1) = k(n − 1) + G. Заметим, что G кратно n − 1. Но всего максимум очков могло быть 2(n − 1) (n − 1 тур, в каждом максимум два очка). Значит, G = 0, n−1 или 2(n−1). В первом и третьем случае получим то, что нужно доказать, во втором получим n = k+1, или k = n−1, но тогда все, в том числе и Гоша, набрали n − 1 очко, но это противоречит условию задачи.