Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Четность
Четность — одна из самых простых идеи олимпиадной математики. Сама по себе идея не слишком содержательна. Она заключается в том, что все натуральные числа являются либо четными (то есть делятся на два), либо нечетными (и на два не делятся). Причем, после каждого четного числа идет нечетное, а после каждого нечетного — четное. Однако, не смотря на свою простоту она помогает решать некоторые (даже не очень простые) задачи.
В разных задачах четность проявляется по разному. Это либо идея чередования (будут ли совпадать объекты стоящие на краях ряда из чередующихся объектов, зависит от четности их числа), либо идея разбиения на пары (какие-то объекты можно разбить на пары тогда, и только тогда, когда их количество четно). В каких-то задачах сразу видно, что все зависит от четности, а в других это не так очевидно.
Пример. На столе лежат 13 шестеренок, соединенных в замкнутую цепочку. Могут ли все шестеренки вращаться одновременно?
Решение. Пронумеруем подряд все шестеренки. Предположим, что первая шестеренка вращается по часовой стрелке. Тогда вторая шестеренка должна вращаться против часовой стрелки. Третья — снова по часовой, четвертая — против и т.д. Ясно, что “нечетные” шестеренки должны вращаться по часовой стрелке, а “четные” — против. Но тогда 1-я и 13-я шестеренки одновременно вращаются по часовой стрелке. Противоречие.
Ответ. Не могут.
Пример. Может ли прямая, не содержащая вершин замкнутой 13—звенной ломаной, пересекать все ее звенья?
Решение. Пронумеруем вершины ломаной в порядке следования числами от 1 до 13. Прямая делит плоскость на две полуплоскости I и II. Пусть вершина с номером 1 находится в полуплоскости I. Соседние вершины ломаной должны располагаться в разных полуплоскостях. Значит, вершина 2 — в полуплоскости II, вершина 3 — в полуплоскости I, и так далее, вершина 13 — в полуплоскости I. Тогда звено, с концами в вершинах 1 и 13, не пересекает прямую. Значит, прямая не может пересекать все звенья ломаной.
Ответ. Не может.
Пример. Можно ли нарисовать 13—звенную замкнутую ломаную, каждое звено которой пересекается ровно с одним из остальных звеньев?
Решение. Если бы такое было возможно, то все звенья ломаной разбились бы на пары пересекающихся. Однако, тогда число звеньев должно быть четным. Противоречие.
Ответ. Нельзя.
Пример. На доске 25×25 расставлены 25 шашек, причем их расположение симметрично относительно диагонали. Докажите, что одна из шашек расположена на диагонали.
Решение. Шашки, не стоящие на диагонали, разбиваются на пары симметричных, то есть таких шашек четное число. Так как всего шашек нечетное число, то на диагонали стоит нечетное число шашек, то есть, по крайней мере, одна.
Пример. На доске 25×25 расставлены 25 шашек, причем их расположение симметрично относительно обеих главных диагоналей. Докажите, что одна из шашек стоит в центральной клетке.
Решение. Из решения предыдущего примера следует, что на диагонали стоит нечетное число фишек. Но фишки стоящие на диагонали должны располагаться симметрично относительно другой диагонали. Следовательно одна из шашек стоит в центре доски.
Пример. Квадратная таблица 25×25 раскрашена в 25 цветов так, что в каждой строке и в каждом столбце представлены все цвета. Докажите, что если расположение цветов симметрично относительно одной из диагоналей, то на этой диагонали тоже представлены все цвета.
Решение. Поскольку в каждой строке представлены все цвета и количество цветов совпадает с числом столбцов, то в каждой строке находится ровно по одной клетке каждого цвета. Таким образом, клеток каждого цвета — 25 штук. Далее, так как таблица симметрична относительно диагонали, то вне диагонали находится четное число клеток каждого цвета (каждой клетке соответствует симметричная). Поскольку клеток каждого цвета нечетное число, то на диагонали каждый цвет обязан присутствовать. Это и требовалось доказать.
Пример. В классе 30 учеников и каждый день трое из них дежурят по классу. Может ли через некоторое время оказаться так, что каждый с каждым дежурил ровно один раз?
Решение. Рассмотрим одного из учеников. В каждом его дежурстве участвует еще два школьника. Если оказалось, что с каждым он дежурил ровно один раз, то все остальные разбились на пары. А это невозможно, так как число 29 — нечетно.
Ответ. Не может.
Пример. За круглым столом сидят 25 мальчиков и 25 девочек. Докажите, что у кого-то из сидящих за столом оба соседа — мальчики.
Решение. Предположим, что можно рассадить детей так, чтобы ни у одного из них не были оба соседа мальчики. Это означает, что два ребенка, сидящие через одного не могут быть одновременно мальчиками. Рассмотрим 25 детей сидящих через одного. Среди них после каждого мальчика по ходу часовой стрелки сидит хотя бы одна девочка. Значит среди этих 25 ребят девочек не меньше, чем мальчиков, то есть хотя бы 13. Аналогично, среди оставшихся 25 ребят сидящих через одного — также хотя бы 13 девочек. А значит, всего девочек должно быть по крайней мере 26. Противоречие.
Задача
Ответ: нет
3 (Раскрашенная доска)
Клетки доски 7 на 7 раскрашены в 7 цветов, причем в каждый цвет окрашено ровно 7 клеток. Раскраска оказалась симметричной относительно главной диагонали. Докажите, что на главной диагонали присутствуют все цвета.
(Круглый стол)
За круглым столом сидят 25 мальчиков и 25 девочек. Докажите, что у кого-то из сидящих за столом оба соседа - мальчики.
город Дальний)
В стране не менее 1000 городов. Столица соединена дорогой с 999 городами,
каждый из остальных городов - с 20 городами, а город Дальний - ровно с 1 городом. Докажите, что из Столицы можно добраться по нескольким дорогам до города Дальний
(Умножай, дели)
На доске написано число 12. В течение каждой минуты число либо умножают, либо делят на 2 или на 3, и результат записывают на доску вместо исходного числа. Докажите, что число, которое будет написано на доске ровно через час, не может быть равно 54.
(Корень многочлена)
Дан многочлен x^7+2x^6+3x^5+4x^4+5x^3+6x^2+7x+1.3.5…99.
Имеет ли этот многочлен целый корень?
(Дружный класс)
В классе несколько мальчиков и девочек. Известно, что каждая девочка дружит ровно с 7 девочками и 7 мальчиками, а каждый мальчик дружит ровно с 7 девочками. Какое наименьшееколичество детей могло быть в классе?
(График дежурств)
В классе 30 учеников и каждый день трое из них дежурят по классу. Может ли через некоторое время оказаться так, что каждый с каждым дежурил ровно один раз?
(Шайба)
На ледяной плоскости лежат три шайбы, не находящиеся на одной прямой. Каждую минуту хоккеист бьет по одной из шайб так, чтобы она прошла между двумя другими. Могут ли шайбы вернуться на свои места через 2013 минут?
(Ряд карточек)
В ряд выложены карточки, на которых записаны числа 1, 2, 3, 4, 5, 6, 7, 8, 9. За одну операцию можно поменять местами любые две карточки. Можно ли за 2013 ходов переложить все карточки в обратном порядке?
Домашнее задание
(Числа в таблице)
Можно ли в таблице 9 на 10 расставить натуральные числа так, чтобы сумма чисел в любом столбце или строке являлась простым числом?
(Разрезание на параллелограммы)
Можно ли некоторый выпуклый 13-угольник разрезать на параллелограммы?
(Равные звенья)
Существует ли на плоскости замкнутся 2013-звенная ломаная, у которой все вершины имеют целые координаты, а все звенья имеют одинаковую длину?
(Перекрашивание доски)
Изначально клетки доски окрашены в шахматном порядке. За одну операцию разрешено перекрасить клетки в квадратике 2 на 2. Можно ли за несколько операций получить ситуацию, в которой покрашены черным в точности клетки главной диагонали?
Тест
1. Единицы в таблице
13.33 баллa
В клетки таблицы 4×4 записаны числа 1 и −1 так, что в каждой строке, в каждом столбце и на каждой диагонали (не обязательно главной; в частности, в угловых клетках) произведения чисел равны 1. Какое максимальное число минус единиц может быть в таблице?
2. Попарные произведения
20.00 баллa
Дано n чисел x1, x2, …, xn, каждое из которых равно +1 или −1. Известно, что
x1x2+x2x3+…+xn−1xn+xnx1=0.
Отметьте те значения n, при которых это возможно.
Решение
В каждом указанном в условии ряду должно быть четное число минус единиц. Рассмотрим все диагонали, содержащие нечетное количество клеток. Их 8, и никакие две из них не имеют общих клеток. На каждой из них должна быть хотя бы одна единица, поэтому число единиц не меньше 8, и следовательно, число минус единиц не больше 8. Пример с 8 минус единицами: на двух главных диагоналях стоят 1, в остальных клетках −1.
Решение
Для удобства расположим данные числа по окружности в порядке x1, x2, …, xn. Раскрасим дугу между соседними числами в красный цвет, если эти числа равны. Далее, раскрасим дугу между соседними числами в синий цвет, если первое из этих чисел (при движении по часовой стрелке) равно +1, а второе равно −1, и раскрасим дугу между соседними числами в зеленый цвет, если первое из этих чисел равно −1, а второе равно +1. Количество синих дуг равно количеству зеленых, поскольку синяя дуга соответствует переходу от группы нескольких подряд стоящих единиц к группе минус единиц при движении по часовой стрелке, а зеленая дуга соответствует переходу от группы минус единиц к группе единиц; следовательно, если игнорировать красные дуги, синие и зеленые дуги будут чередоваться. Произведение чисел на концах красной дуги равно 1, а произведение чисел на концах синей или зеленой дуги равно −1; поэтому чтобы сумма
x1x2+x2x3+…+xn−1xn+xnx1
была равна нулю, необходимо, чтобы количество красных дуг было равно суммарному количеству синих и зеленых дуг. Итак, если синих и зеленых дуг по s, то красных дуг 2s, и общее количество дуг
n=s+s+2s=4s.
Это означает, что n делится на 4. Легко привести пример, для любого n, делящегося на 4. Достаточно взять последовательность:
1,1,−1,−1,…1,1,−1,−1.
3. Совет мудрецов
33.33 баллa
Переаттестация Совета из десяти мудрецов происходит так: король выстраивает их в колонну по одному и надевает на голову каждому колпак белого или черного цвета. Каждый мудрец видит цвета колпаков всех впереди стоящих мудрецов, но не видит цвет своего колпака и цвета колпаков мудрецов, стоящих сзади него. Затем мудрецы по одному называют какой-нибудь цвет (каждому разрешается говорить ровно один раз; то, что говорит один мудрец, слышат все). После этого король казнит всех мудрецов, назвавших цвет, отличный от цвета своего колпака. Накануне переаттестации все члены Совета договорились между собой и придумали, как минимизировать число казненных. Скольким из них гарантированно удастся избежать казни?
Ваш ответ: 9
Правильный ответ: 9
Решение
Нет никакой гарантии, что мудрец, стоящий в конце колонны спасется -- его колпака не видит ни один мудрец. Покажем, что гарантированно спастись могут все остальные мудрецы. Пусть мудрец, стоящий последним в колонне, скажет "белый", если он видит перед собой четное число белых колпаков, и "черный", если нечетное. Теперь мудрецы по порядку от девятого к первому смогут называть цвет своего колпака. В тот момент, когда очередь говорить доходит до k-го мудреца (k=9, 8, …, 1), он знает четность числа белых колпаков всех мудрецов от первого до девятого, и знает цвета колпаков всех мудрецов с первого до девятого, за исключением своего (мы предполагаем, что девятый, …, (k+1)-й мудрецы уже верно назвали цвет своего колпака, колпаки же первого, второго, …, (k−1)-го мудрецов k-ый мудрец видит). По этим данным k-ый мудрец легко определяет цвет своего колпака.
4. Числа с тремя делителями
6.67 баллa
Простые числа имеют только два различных делителя —единицу и само это число. А какие натуральные числа имеют только три различных делителя? Найдите восьмое по величине такое число.
Ваш ответ: 361
Правильный ответ: 361
Решение
Разобьем делители числа n на пары: делителю m числа n поставим в соответствие число nm. Заметим, что тогда каждому делителю будет поставлен в другой делитель, кроме того m для которого m2=n. Из этого следует, что если число делителей нечетно, то n=m2. Причем всегда еще есть делители n и 1. Поэтому m должно быть простым. Значит искомое число -- это p2, где p -- восьмое простое число, то есть 19.
5. Четные против нечетных
0.00 баллa
Все натуральные числа от 1 до 1000 включительно разбиты на две группы: чётные и нечетные. Пусть a -- сумма сумм цифр чисел в первой группе, b -- во второй. Найдите |a−b|.
Подсказка 1
Попробуйте разбить все числа на пары четное -- нечетное так, чтобы во всех парах суммы цифр отличались на какую-то фиксированную величину.
Подсказка 2
Попробуйте разбить все числа на пары четное —нечетное так, чтобы в записи чисел из одной пары отличались только одной цифрой.
Ваш ответ: 500
Правильный ответ: 499
Решение
Сумма цифр числа 1 равна сумме цифр числа 1000. Остальные числа разобьём на пары: 2--3, 4--5, 6--7, 8--9, ..., 998--999. В каждой паре единицы нечетного числа больше на 1, чем чётного, а десятков и сотен у них поровну. Всего таких пар 499. Значит, сумма цифр нечётных чисел больше на 499.