Олимпиадные задачи по теме «Теория чисел. Делимость» для 1-8 класса - сложность 4 с решениями

В некоторых клетках доски 100×100 стоит по фишке. Назовём клетку <i>красивой</i>, если в соседних с ней по стороне клетках стоит чётное число фишек.

Может ли ровно одна клетка доски быть красивой?

На клетчатую плоскость положили 2009 одинаковых квадратов, стороны которых идут по сторонам клеток. Затем отметили все клетки, которые покрыты нечётным числом квадратов. Докажите, что отмеченных клеток не меньше, чем клеток в одном квадрате.

Для прохождения теста тысячу мудрецов выстраивают в колонну. Из колпаков с номерами от 1 до 1001 один прячут, а остальные в случайном порядке надевают на мудрецов. Каждый видит только номера на колпаках всех впереди стоящих. Далее мудрецы по порядку от заднего к переднему называют вслух целые числа. Каждое число должно быть от 1 до 1001, причём нельзя называть то, что уже было сказано. Результат теста – число мудрецов, назвавших номер своего колпака. Мудрецы заранее знали условия теста и могли договориться, как действовать.

  а) Могут ли они гарантировать результат более 500?

  б) Могут ли они гарантировать результат не менее 999?

Дано конечное множество простых чисел <i>P</i>. Докажите, что найдётся такое натуральное число <i>x</i> , что оно представляется в виде  <i>x = a^p + b^p</i>  (с натуральными <i>a, b</i>) при всех   <i>p</i> ∈ <i>P </i>  и не представляется в таком виде для любого простого <i>p</i> ∉ <i>P</i>.

Диагональ правильного 2006-угольника <i>P</i> называется <i>хорошей</i>, если её концы делят границу <i>P</i> на две части, каждая из которых содержит нечётное число сторон. Стороны <i>P</i> также называются хорошими. Пусть <i>P</i> разбивается на треугольники 2003 диагоналями, никакие две из которых не имеют общих точек внутри <i>P</i>. Какое наибольшее число равнобедренных треугольников, каждый из которых имеет две хорошие стороны, может иметь такое разбиение?

Некоторые участники олимпиады дружат, и дружба взаимна. Назовём группу участников <i>кликой</i>, если все они дружат между собой. Их число называется <i>размером</i> клики. Известно, что максимальный размер клики чётен. Докажите, что участников можно рассадить по двум аудиториям так, что максимальные размеры клик в обеих аудиториях совпадают.

Докажите, что если натуральное число <i>N</i> представляется в виде суммы трёх квадратов целых чисел, делящихся на 3, то оно также представляется в виде суммы трёх квадратов целых чисел, не делящихся на 3.

Найдите все такие пары  (<i>x, y</i>)  натуральных чисел, что  <i>x + y = aⁿ,  x</i>² + <i>y</i>² = <i>a^m</i>  для некоторых натуральных <i>a, n, m</i>.

Натуральные числа <i>x</i> и <i>y</i> таковы, что  2<i>x</i>² – 1 = <i>y</i>¹⁵.  Докажите, что если  <i>x</i> > 1,  то <i>x</i> делится на 5.

Натуральные числа <i>x, y, z</i>  (<i>x</i> > 2,  <i>y</i> > 1)  таковы, что  <i>x^y</i> + 1 = <i>z</i>².  Обозначим через <i>p</i> количество различных простых делителей числа <i>x</i>, через <i>q</i> – количество различных простых делителей числа <i>y</i>. Докажите, что  <i>p ≥ q</i> + 2.

Можно ли в клетках бесконечного клетчатого листа расставить натуральные числа таким образом, чтобы при любых натуральных  <i>m, n</i> > 100  сумма чисел в любом прямоугольнике <i>m</i>×<i>n</i> клеток делилась на  <i>m + n</i>?

Имеются одна красная и <i>k</i>  (<i>k</i> > 1)  синих ячеек, а также колода из 2<i>n</i> карт, занумерованных числами от 1 до 2<i>n</i>. Первоначально вся колода лежит в произвольном порядке в красной ячейке. Из любой ячейки можно взять верхнюю карту и переложить её либо в пустую ячейку, либо поверх карты с номером, большим на единицу. При каком наибольшем <i>n</i> можно такими операциями переложить всю колоду в одну из синих ячеек?

Найдите все такие нечётные натуральные  <i>n</i> > 1,  что для любых взаимно простых делителей <i>a</i> и <i>b</i> числа <i>n</i> число  <i>a + b</i> – 1  также является делителем <i>n</i>.

Два многочлена  <i>P</i>(<i>x</i>) = <i>x</i>⁴ + <i>ax</i>³ + <i>bx</i>² + <i>cx + d</i>  и  <i>Q</i>(<i>x</i>) = <i>x</i>² + <i>px + q</i>  принимают отрицательные значения на некотором интервале <i>I</i> длины более 2, а вне <i>I</i> – неотрицательны. Докажите, что найдётся такая точка <i>x</i>₀, что  <i>P</i>(<i>x</i>₀) < <i>Q</i>(<i>x</i>₀).

Найдите все такие натуральные числа <i>n</i>, что для любых двух его взаимно простых делителей <i>a</i> и <i>b</i> число  <i>a + b</i> – 1  также является делителем <i>n</i>.

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

Найдите все такие тройки натуральных чисел <i>m, n</i> и <i>l</i>, что  <i>m + n</i> = (НОД(<i>m, n</i>))²,  <i>m + l</i> = (НОД(<i>m, l</i>))²,  <i>n + l</i> = (НОД(<i>n, l</i>))².

Найдите все такие натуральные <i>n</i>, что при некоторых взаимно простых <i>x</i> и <i>y</i> и натуральном  <i>k</i> > 1,  выполняется равенство  3<i>ⁿ = x^k + y^k</i>.

На столе лежат три кучки спичек. В первой кучке находится 100 спичек, во второй – 200, а в третьей – 300. Двое играют в такую игру. Ходят по очереди, за один ход игрок должен убрать одну из кучек, а любую из оставшихся разделить на две непустые части. Проигравшим считается тот, кто не может сделать ход. Кто выиграет при правильной игре: начинающий или его партнер?

В однокруговом футбольном турнире играли &nbsp<i>n</i> > 4  команд. За победу давалось 3 очка, за ничью 1, за проигрыш 0. Оказалось, что все команды набрали поровну очков.

  а) Докажите, что найдутся четыре команды, имеющие поровну побед, поровну ничьих и поровну поражений.

  б) При каком наименьшем <i>n</i> могут не найтись пять таких команд?

У ведущего есть колода из 52 карт. Зрители хотят узнать, в каком порядке лежат карты (при этом не уточняя   сверху вниз или снизу вверх). Разрешается задавать ведущему вопросы вида "Сколько карт лежит между такой-то и такой-то картами?". Один из зрителей подсмотрел, в каком порядке лежат карты. Какое наименьшее число вопросов он должен задать, чтобы остальные зрители по ответам на эти вопросы могли узнать порядок карт в колоде?

Доказать, что существует бесконечно много таких составных <i>n</i>, что  3^<i>n</i>–1 – 2^<i>n</i>–1 кратно <i>n</i>.

Из колоды вынули семь карт, показали всем, перетасовали и раздали Грише и Лёше по три карты, а оставшуюся карту

  а) спрятали;

  б) отдали Коле.

Гриша и Лёша могут по очереди сообщать вслух любую информацию о своих картах. Могут ли они сообщить друг другу свои карты так, чтобы при этом Коля не смог вычислить местонахождение ни одной из тех карт, которых он не видит? (Гриша и Лёша не договаривались о каком-либо особом способе общения; все переговоры происходят <i>открытым текстом</i>.)

Марсианское метро на плане имеет вид замкнутой самопересекающейся линии, причём в одной точке может происходить только одно самопересечение. (Линия нигде не касается сама себя.) Доказать, что тоннель с таким планом можно прорыть так, что поезд будет проходить попеременно под и над пересекающей линией.

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