На чудо яблоне растут бананы и ананасы

Добавил пользователь Валентин П.
Обновлено: 19.09.2024

За один раз разрешается сорвать с нее два плода. Если сорвать два банана или 2 ананаса, то вырастет еще один ананас, а если сорвать один банан и один ананас, то вырастет один банан. В итоге остался один плод. Какой это плод, если известно, сколько бананов и ананасов росло вначале.

Заметим , что чётность числа бананов не изменяется пусть , бананов-б, тогда ,если б -чётное , то остаться один банан не мог, а значит остался ананас, иначе (если б-нечётное),если остался ананас , то число бананов поменяло поменяло чётность (противоречие), значит остался банан

Прикрепленные файлы: 1 файл

Задачи к олимпиадам.doc

Идея №6

Инварианты

Инвариант – величина, которая не изменяется в результате некоторых операций (например, разрезание и перестановка частей фигур не меняет суммарной площади). Если инвариант различает два положения, то от одного нельзя перейти к другому. В качестве инварианта может использоваться чётность или раскраска. В задачах про сумму цифр используют остатки от деления на 3 или 9. Полуинвариант – величина, изменяющаяся только в одну сторону (т.е. которая может только увеличиваться или только уменьшаться). Понятие полуинварианта часто используется при доказательствах остановки процессов.

Пример 1. На чудо-яблоне растут бананы и ананасы. За один раз разрешается сорвать с неё два плода. Если сорвать два банана или два ананаса, то вырастет ещё один ананас, а если сорвать один банан и один ананас, то вырастет один банан. В итоге остался один плод. Какой это плод, если известно, сколько бананов и ананасов росло вначале.

Решение. Чётность числа бананов не меняется, поэтому, если число бананов было чётным, то оставшийся плод – ананас, если число бананов было нечётным, то – банан.

Пример 2. В одной клетке квадратной таблицы 4 х 4 стоит знак минус, а в остальных стоят плюсы. Разрешается одновременно менять знак во всех клетках, расположенных в одной строке или в одном столбце. Докажите, что, сколько бы мы не проводили таких перемен знака, нам не удастся получить таблицу из одних плюсов.

Решение. Заменим знак плюс на число 1 и знак минус на число –1. Заметим, что произведение всех чисел в таблице не меняется при смене знака у всех чисел столбца или строки, так как одновременно меняется знак у четырёх чисел. В начальном положении это произведение равно –1, а в таблице из одних плюсов +1, чем и доказана невозможность перехода.

Пример 3. На прямой стоят две фишки: слева красная, справа синяя. Разрешается производить любую из двух операций: вставку двух фишек одного цвета подряд (между фишками или с краю) и удаление пары соседних одноцветных фишек (между которыми нет других фишек). Можно ли с помощью таких операций оставить на прямой ровно две фишки: слева синюю, а справа красную?

Решение. Рассмотрим число разноцветных пар (не только соседних), где левая фишка красная, и заметим, что чётность этого показателя не меняется. Но в исходной ситуации наш показатель равен 1, а в желаемой ситуации – нулю. Поэтому перейти к желаемой ситуации невозможно.

Пример 4. На острове Серобуромалин живут хамелеоны: 13 серых, 15 бурых и 17 малиновых. Если 2 хамелеона разных цветов встречаются, то они оба меняют свой цвет на третий. Может ли случиться, что в некоторый момент все хамелеоны на острове станут одного цвета?

Указание. Рассмотрите остатки от деления чисел Б бурых, С серых и М малиновых хамелеонов на 3 и проверьте, что попарные разности у этих остатков не меняются.

Пример 6. На 44 деревьях, расположенных по кругу сидели по весёлому чижу. Время от времени какие-то два чижа перелетают на соседнее дерево – один по часовой стрелке, а другой – против. Могут ли все чижи собраться на одном дереве?

Решение. Пронумеруем деревья по кругу с 1-го по 44-е. Сумма номеров деревьев, на которых сидят чижи либо не меняется, либо уменьшается на 44, либо увеличивается на 44. Тем самым, остаток от деления этой суммы номеров на 44 не меняется. Изначально этот остаток равен 22, а если все чижи усядутся на одно дерево, то он будет равен нулю. Поэтому чижи не смогут собраться на одном дереве.

  1. Можно ли разрезать выпуклый 17-угольник на 14 треугольников.
  2. Можно ли круг разрезать на несколько частей и сложить квадрат? (Разрезы – это прямые и дуги окружностей).
  3. Болельщик Вася нарисовал расположения игроков на футбольном поле к началу первого и второго таймов. Оказалось, что некоторые игроки поменялись местами, а остальные остались на своих местах. При этом расстояние между любыми двумя игроками не увеличилось. Докажите, что все эти расстояния не изменились.
  4. Докажите, что сумма квадратов расстояний от вершин праивльного n-угольника до любой прямой, проходящей через его центр есть величина постоянная.
  5. (сизифов труд). На горе 1001 ступенька, на некоторых лежат камни, по одному на ступеньке. Сизиф берёт любой камень и переносит его вверх на ближайшую свободную ступеньку (т.е. если ближайшая ступенька свободна, то на неё, а если она занята, то на несколько ступенек вверх до первой свободной). После этого Аид скатывает на одну ступеньку вниз один из камней, у которых предыдущая ступенька свободна. Камней 500 и первоначально они лежали на нижних 500 ступеньках. Сизиф и Аид действуют по очереди, начинает Сизиф. Цель Сизифа положить камень на верхнюю ступеньку. Может ли Аид ему помешать?
  6. Столица страны соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с 10 городами (если А соединён с В, то В соединён с А). Известно, что из любого города можно попасть в любой другой (может быть, с пересадками). Докажите, что можно закрыть половину авиалиний, идущих из столицы, так что возможность попасть из любого города в любой другой сохранится.
  7. Во время перемирия за круглым столом разместились рыцари из двух враждующих станов. Оказалось, что число рыцарей, справа от которых сидит враг, равно числу рыцарей, справа от которых сидит друг. Докажите, что число рыцарей делится на 4.

Идея №7

Принцип Дирихле

Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.

Допустим, что в каждом ящике сидят меньше чем n/k кроликов. Тогда во всех ящиках вместе кроликов меньше чем n/k*k = n. Противоречие.

Формулировка принципа Дирихле кажется очевидной, однако трудность состоит в том, что в задачах не указаны ни кролики, не ящики.

Зная принцип Дирихле, можно догадаться, в каких случаях его применять. Например, если каждому элементу множества А соответствует ровно один элемент множества В, то элементы А можно назвать кроликами, а элементы В – ящиками.

Заметим, что в последней формулировке кролики играют роль ящиков для травы, а трава – роль кроликов, сидящих в ящиках.

Пример 1. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.

Решение. Всего в году 365 дней. Назовём дни ящиками, а учеников кроликами. Тогда в некотором ящике сидят не меньше 400/366 кроликов, т.е. больше одного. Следовательно, не меньше двух.

Можно рассуждать от противного. Допустим, что каждый день отмечают день рождения не больше одного ученика, тогда всего учеников не больше 366. Противоречие.

Пример 2. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 х 6 из чисел +1, -1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.

Решение. Допустим, что квадрат составлен. Тогда суммы чисел могут меняться от –6 до +6. Всего 13 значений. Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем 14 различных сумм. Противоречие, значит, составить такой квадрат невозможно.

Пример 3. На планете Земля океан занимает больше половины площади поверхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки.

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

Пример 4. На собеседование пришли 65 школьников. Им предложили 3 контрольных работы. За каждую контрольную ставилась одна из оценок: 2,3,4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на контрольных?

Решение. Рассмотрим множество наборов из трёх оценок за соответствующие контрольные. Количество таких наборов равно 43 или 64 (4 возможности за каждую из трёх контрольных). Поскольку число учащихся больше 64, по принципу Дирихле каким-то двум учащимся отвечает один набор оценок.

Идея №8

Делимость и остатки

Остаток может выступать в роли инварианта (например, остаток от деления на 9 в задачах про сумму цифр).

Пример 1. Докажите, что существует бесконечно много чисел, которые не представимы в виде суммы двух квадратов.

Решение. Достаточно доказать, что числа, имеющие при делении на 4 остаток 3, не представимы в виде суммы двух квадратов. Из равенств (2k)2 = 4k2, (2k + 1)2 = 4k2 + 4k + 1 следует, что квадрат целого числа при делении на 4 даёт остаток 0 или 1. Поэтому сумма двух квадратов не может иметь остаток 3.

Пример 2. Докажите, что число, в десятичной записи которого участвуют три единицы и несколько нулей, не может быть квадратом.

Решение. Если такое число существует, то оно делится на 3, но не делится на 9 (по признакам делимости на 3 и на 9). Но если число делится на 3 и является полным квадратом, то оно делится на 9. Противоречие.

  1. Какие числа можно представить в виде разности двух квадратов целых чисел?
  2. Если p – простое число, большее 3, то p2 – 1 делится на 24.
  3. При каких n число 2n – 1 делится на 7?
  4. Известно, что сумма нескольких натуральных чисел делится на 6. Докажите, что сумма кубов этих чисел тоже делится на 6.
  5. Если в целочисленной арифметической прогрессии встретился квадрат целого числа, то квадратов в ней бесконечно много. Докажите.

Идея №9

Алгоритм Евклида

Пусть даны два натуральных числа n1 и n2. Поделим n1 на n2 с остатком. Обозначим остаток n3. Поделим n2 на n3 с остатком и т.д. (каждый раз мы делим предыдущий делитель на полученный остаток) до тех пор, пока остаток не будет равен нулю. Последний ненулевой остаток и будет равен наибольшему общему делителю исходных чисел n1 и n2.

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

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