Выбрано 16 задач 
Убрать все задачи
Дано несколько белых и несколько чёрных точек. Из каждой белой точки идет стрелка в каждую чёрную, на каждой стрелке написано натуральное число. Известно, что если пройти по любому замкнутому маршруту, то произведение чисел на стрелках, идущих по направлению движения, равно произведению чисел на стрелках, идущих против направления движения. Обязательно ли можно поставить в каждой точке натуральное число так, чтобы число на каждой стрелке равнялось произведению чисел на её концах?
Докажите, что связный граф, у которого число рёбер на единицу меньше числа вершин, является деревом.
Пусть p – простое число и p > 3.
а) Докажите, что если разрешимо сравнение x² + x + 1 ≡ 0 (mod p), то p ≡ 1 (mod 6).
б) Выведите отсюда бесконечность множества простых чисел вида 6k + 1.
Пусть p – простое число и p > 5. Докажите,
что если разрешимо сравнение x4 + x3 + x2 + x + 1 ≡ 0 (mod p), то
p ≡ 1 (mod 5).
Выведите отсюда бесконечность множества простых чисел вида 5n + 1.
Имеется 20 человек – 10 юношей и 10 девушек. Сколько существует способов составить компанию, в которой было бы одинаковое число юношей и девушек?
Во время шахматного турнира, несколько игроков сыграли нечётное количество партий. Докажите, что число таких игроков чётно.
Пусть a и k > 0 произвольные числа. Определим последовательность {an} равенствами
В углах шахматной доски 3×3 стоят четыре коня: два белых (в соседних углах) и два чёрных.
Можно ли за несколько ходов поставить коней так, чтобы во всех соседних углах стояли кони различного цвета?
На плоскости нарисовано несколько точек, некоторые пары точек соединены отрезками. Известно, что из каждой точки выходит не более k отрезков. Докажите, что точки можно покрасить в k + 1 цвет таким образом, чтобы каждые две точки, соединенные отрезком, были покрашены в разные цвета.
n точек соединены отрезками так, что каждая точка с чем-нибудь соединена и нет таких двух точек, которые соединялись бы двумя разными путями.
Доказать, что общее число отрезков равно n – 1.
Дано простое p и целое a, не делящееся на p. Пусть k – наименьшее натуральное число, при котором ak ≡ 1 (mod p). Докажите, что p – 1 делится на k.
В парламенте 200 депутатов. В процессе заседания произошло 200 потасовок, в каждой из которой участвовали некоторые два депутата.
Докажите, что можно объединить в комиссию 67 депутатов, из которых никакие два не выясняли между собой отношения в потасовке.
В прямоугольном треугольнике ABC CH – высота, проведённая к гипотенузе. Окружность с центром H и радиусом CH пересекает больший катет AC в точке M. Точка B' симметрична точке B относительно H. В точке B' восставлен перпендикуляр к гипотенузе, который пересекает окружность в точке K. Докажите, что:
а) B'M || BC;
б) AK – касательная к окружности.
Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее рёбрами так, чтобы он остался связным.
Пусть M – конечное множество чисел. Известно, что среди любых трёх его элементов найдутся два, сумма которых принадлежит M.
Какое наибольшее число элементов может быть в M?
а) Докажите, что если p — простое число и 2 ≤ k ≤ p – 2, то делится на p.
б) Верно ли обратное утверждение?
|
|
 |
Условие
а) Докажите, что если p — простое число и 2 ≤ k ≤ p – 2, то делится на p.
б) Верно ли обратное утверждение?
Решение
а) При k > p – k + 1 (2k > p + 1) оба биномиальных коэффициента равны нулю, а при 2k = p + 1 – единице. Поэтому далее считаем, что 2k ≤ p.
Числитель кратен p, а ни один из множителей знаменателя не делится на p.
б) Пусть p – составное число и q – один из его простых делителей. Тогда
Ответ
б) Верно.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 4 |
| Название | Арифметика остатков |
| Тема | Деление с остатком. Арифметика остатков |
| параграф | |
| Номер | 2 |
| Название | Делимость |
| Тема | Теория чисел. Делимость (прочее) |
| задача | |
| Номер | 04.044 |
