Два числа при делении на 16 дают остаток 8 доказать что разность

Презентация «Натуральные и целые числа. Делимость целых чисел. НОД и НОК натуральных чисел»

Описание презентации по отдельным слайдам:

Натуральные числа – это числа, которые используются для счета. 3+33=36 12*3=36 Не всегда выполняется «-» и «:» 14-15=-1 9:2=4,5 Обозначение: N

Целые числа – это все натуральные числа, «0» и противоположные натуральным. 3+33=36 12*3=36 14-15=-1 Не всегда выполняется «-» и «:» 9:2=4,5 Обозначение: Z

Определение. Пусть даны два натуральных числа а и b. Если существует такое q, что выполняется равенство a= bq, то говорят, что число a делится на число b. a – делимое, b – делитель, q – кратное Сравните: a:b

Основные признаки делимости Число делится (без остатка или нацело) на число 2, если его последняя цифра четная или 0; Число делится на число 3, если сумма его цифр делится на 3; Число делится на число 4, если две его последние цифры образуют число, которое делится на 4, или являются нулями.

4. Число делится на число 5, если его последняя цифра 0 или 5; 5. Число делится на число 8, если три его последние цифры образуют число, которое делится на 8, или являются нулями; 6. Число делится на число 9, если сумма его цифр делится на 9; 7. Число делится на число 10, если его последняя цифра нуль.

Простые и составные числа Определение. Если натуральное число имеет только два делителя – само себя и 1, то его называют простым числом; если оно имеет более двух делителей, то его называют составным числом. Число 1 не является ни простым, ни составным.

№ 1 Определите: на какие из чисел 2, 3, 4, 5, 6, 8, 9, 10, 15, 18, 20 делится без остатка число 562 320. № 2 Определите, простым или составным является число 87 516 540 321. № 3 Число N дает при делении на 8 остаток 3. Какой остаток при делении на 8 дает число в четыре раза больше данного?

№ 4 Два числа при делении на 16 дают остаток 8. Доказать, что разность и сумма этих чисел без остатка делятся на 16. № 5 Разложить на простые множители число 7000.

№ 6 Найти наибольший общий делитель чисел 48, 60, 72. Решение: 48 2 24 2 12 2 6 2 3 3 1 60 2 30 2 15 3 5 5 1 72 2 36 2 18 2 9 3 3 3 1

НОК натуральных чисел

Для нахождения НОК Чисел а, Ь, с. 1) выписывают разложения на простые множители чисел а, Ь, с. ; 2) перечисляют все простые множители, входящие хотя бы в одно из этих разложений; 3) каждый из перечисленных множителей возводят в максимальную степень, с которой этот множитель входит в разложения; 4) произведение полученных степеней простых множителей дает НОК чисел а, Ь, с, …

48 2 24 2 12 2 6 2 3 3 1 60 2 30 2 15 3 5 5 1 72 2 36 2 18 2 9 3 3 3 1

Используемая литература 1. Алгебра.10 класс. Часть 1. Учебник. Профильный уровень. Мордкович А.Г., Семенов П. В.;

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

Курс повышения квалификации

Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО

Курс профессиональной переподготовки

Математика: теория и методика преподавания в образовательной организации

Ищем педагогов в команду «Инфоурок»

Номер материала: ДБ-334307

Не нашли то что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Безлимитный доступ к занятиям с онлайн-репетиторами

Выгоднее, чем оплачивать каждое занятие отдельно

Учителям предлагают 1,5 миллиона рублей за переезд в Златоуст

Время чтения: 1 минута

Минпросвещения предлагает закрыть пляжи детских лагерей для посторонних лиц

Время чтения: 1 минута

Путин поручил не считать выплаты за классное руководство в средней зарплате

Время чтения: 1 минута

Бельгийский город будет платить детям виртуальные деньги за отказ от неэкологичного транспорта

Время чтения: 0 минут

Комиссия РАН призвала отозвать проект новых правил русского языка

Время чтения: 2 минуты

ОНФ проверит качество охраны в российских школах

Время чтения: 2 минуты

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Источник

math4school.ru

Делимость целых чисел и остатки

Немного теории

В разнообразных задачах про целые числа используются основные понятия и теоремы, связанные с делимостью. Приведём некоторые из них.

Каждое целое число а можно разделить на натуральное число m с остатком, то есть представить в виде а = mq + r, где q и r – целые числа и r (остаток) не меньше 0, но меньше q.

Среди любых m последовательных целых чисел найдется ровно одно число, делящееся на m.

Если два числа а и b при делении на число m дают одинаковые остатки, то говорят, что а сравнимо с b по модулю m. Записывают это так

Если a > b, то наибольший общий делитель a и b равен наибольшему общему делителю a – b и b.

Если а и b – натуральные числа и а = bq + r (r – остаток), то наибольший общий делитель d этих чисел равен наибольшему общему делителю b и r; пользуясь этим утверждением несколько раз, можно найти его как последний не равный нулю остаток в цепочке делений с остатком:

(алгоритм Евклида); отсюда следует, что существуют целые числа х и у, такие, что d = ах + by. В частности, если числа а и b взаимно просты, то есть не имеют общих делителей, больших 1, то существуют целые х и у, для которых ах + by = 1.

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

Количество простых чисел бесконечно; доказательство этого утверждения по Евклиду основано на том, что произведение нескольких простых чисел, сложенное с единицей, имеет отличные от всех этих простых чисел множители.

Задачи с решениями

1. Сколько существует натуральных чисел, меньших 1000, которые не делятся ни на 5, ни на 7?

Вычёркиваем из 999 чисел, меньших 1000, числа, кратные 5: их [999/5]=199. Далее вычёркиваем числа, кратные 7: их [999/7]=142. Но среди чисел, кратных 7, имеется [999/35]=28 чисел, одновременно кратных 5; они будут вычеркнуты дважды. Итого, нами должно быть вычеркнуто 199+142–28=313 чисел. Остаётся 999–313=686.

2. Номер автобусного билета – шестизначное число. Билет называется счастливым, если сумма трёх первых цифр номера равна сумме последних трёх цифр. Докажите, что сумма всех номеров счастливых билетов делится на 13.

Если счастливый билет имеет номер А, то билет с номером В=999999–А также счастливый, при этом А и В различны. Поскольку А+В=999999=1001·999=13·77·99 делится на 13, то и сумма номеров всех счастливых билетов делится на 13.

3. Докажите, что сумма квадратов трёх целых чисел не может при делении на 8 дать в остатке 7.

Любое целое число при делении на 8 имеет остатком одно из следующих восьми чисел 0, 1, 2, 3, 4, 5, 6, 7, поэтому квадрат целого числа имеет остатком при делении на 8 одно из трёх чисел 0, 1, 4. Чтобы при делении на 8 сумма квадратов трёх чисел имела остаток 7, необходимо, чтобы выполнялся один из двух случаев: либо один из квадратов, либо все три при делении на 8 имеют нечётные остатки.

В первом случае нечётный остаток есть 1, а сумма двух чётных остатков равна 0, 2, 4, то есть сумма всех остатков равна 1, 3, 5. Остатка 7 в этом случае получить нельзя. Во втором случае три нечётных остатка это три 1, и остаток всей суммы равен 3. Итак, 7 не может быть остатком при делении на 8 суммы квадратов трёх целых чисел.

4. Докажите, что при любом натуральном n:

а) число 5 5n+1 + 4 5n+2 + 3 5n делится на 11.

б) число 2 5n+3 + 5 n ·3 n+2 делится на 17.

а) Первоначально выполним следующее преобразование заданного выражения:

Принимая во внимание бином Ньютона n-й степени, можно записать: (х+1) n = Ах+1, где А – некоторое целое число при целых х. Тогда приведённое выше выражение принимает вид 11В+5+16+1 = 11С, очевидно делящееся на 11, где В и С – некоторые целые числа.

б) Выполним следующие преобразования, из которых следует доказываемое утверждение:

2 5n+3 + 5 n ·3 n+2 = 8·32 n + 9·15 n = 8(17+15) n + 9·15 n = 17А + 8·15 n + 9·15 n = 17А + 17·15 n = 17В,

где А, В – целые положительные числа.

а) если х 2 +у 2 делится на 3 и числа х, у целые, то х и у делятся на 3;

б) если сумма трёх целых чисел делится на 6, то и сумма кубов этих чисел делится на 6;

в) если p и q простые числа и p>3, q>3, то p 2 –q 2 делится на 24;

г) если a, b, c – любые целые числа, то найдутся такие взаимно простые k и t, что ak+bt делится на c.

Таким образом, х=3а и у=3b, то есть х и у делятся на 3, что и требовалось доказать.

б) Достаточно показать, что x 3 +y 3 +z 3 –(x+y+z) делится на 6. Это так и есть, ведь каждое из слагаемых x 3 –x, y 3 –y и z 3 –z делится на 6, поскольку а 3 –а=а(а–1)(а+1) – произведение трёх последовательных целых чисел, которое обязательно делится на 2, 3, а, значит, и 6.

в) Кратность p 2 –q 2 числу 3 можно доказать так. При делении на 3 квадраты целых чисел дают остатки 0 или 1. Так как p и q простые числа больше 3, то это p 2 и q 2 при делении на 3 имеют одинаковые остатки – единицу. Тогда p 2 –q 2 делится на 3.

С другой стороны, p 2 –q 2 =(p+q)(p–q). Так как p и q нечётные и при делении на 4 имеют остатки 1 или 3, то выражение в одних скобках делится на 4, а в других – на 2, а разность квадратов p и q – на 8.

Так как p 2 –q 2 делится на взаимно простые числа 3 и 8, то p 2 –q 2 делится на 3·8=24, что и требовалось доказать.

г) Пусть наибольший общий делитель чисел b и c–a равен d, b=k·d и c–a=t·d. Тогда числа k и t взаимно просты.

Итак, a·k+b·t делится на c.

а) наибольший общий делитель чисел 2n+3 и n+7;

б) все пары натуральных чисел х, у таких, что 2х+1 делится на у и 2у+1 делится на х;

в) все целые k, для которых k 5 +3 делится на k 2 +1;

а) Заметим, что если m > n, то НОД (m; n) = НОД (m – n; n).

Иначе говоря, наибольший общий делитель двух натуральных чисел равен наибольшему общему делителю модуля их разности и меньшего числа. Легко доказать это свойство.

Пусть k – общий делитель m u n (m > n). Это значит, что m = ak, n = bk, где a, b – натуральные числа, причем a > b. Тогда m – n = k(a – b), откуда следует, что k – делитель числа m – n. Значит, все общие делители чисел m и n являются делителями их разности m – n, в том числе и наибольший общий делитель.

НОД (2n+3; n+7) = НОД (n+7; 2n+3 – (n+7)) = НОД (n+7; n–4) = НОД (n–4; 11).

Так как 11 – простое число, то искомый наибольший общий делитель равен 1 либо 11. Если n–4 = 11d, то есть n = 4+11d, то наибольший общий делитель равен 11, в противном случае – 1.

Ответ: НОД (2n+3; n+7) = 11, при n равных 4+11d; НОД (2n+3; n+7) = 1, при n не равных 4+11d.

б) Число 2х+1 нечётное и делится на у, поэтому у тоже нечётное. Аналогично х – нечётное.

Числа х и у взаимно простые. Действительно, пусть k – общий делитель х и у, тогда 2х делится на k, и (2х+1) тоже делится на k (k – делитель у, а у – делитель 2х+1). Значит, 1 делится на k, то есть k=1.

Число 2х+2у+1 делится и на х и на у, а значит, – на ху. Тогда 2х+2у+1 не меньше ху.

Пусть х 5 +3 = (k 3 –k)( k 2 +1) + (k+3), то k 5 +3 делится на k 2 +1, если k+3 делится на k 2 +1. Когда это возможно? Рассмотрим варианты:

1) k+3 = 0, а значит k = –3;

2) k+3 = k 2 +1; решая, находим k = –1, k = 2;

3) проверим целые k при которых k+3 > k 2 +1; после проверки: k = 0, k = 1.

г) пусть m = 2·3·5·7·k. Подбирая k так, чтобы m–1 делилось на 11, а m+1 – на 13, получим, что число n = m–10 удовлетворяет условию задачи.

7. Существует ли десятизначное число, делящееся на 11, в записи которого каждая цифра встречается по одному разу?

I способ. Выписывая трёхзначные числа, делящиеся на 11, можно среди них найти три числа, в записи которых участвуют все цифры от 0 до 9. Например, 275, 396,418. С их помощью можно составить десятизначное число, делящееся на 11. Например:

2753964180 = 275·10 7 + 396·10 7 + 418·10 = 11·(25·10 7 + 36·10 4 + 38·10).

II способ. Для нахождения требуемого числа воспользуемся признаком делимости на 11, согласно которому числа n=a₁a₂a₃…a₁₀ (в данном случае а_i не множители, а цифры в записи числа n) и S(n)=a₁–a₂+a₃–…–a₁₀ одновременно делятся на 11.

Пусть А – сумма цифр, входящая в S(n) со знаком «+», В – сумма цифр, входящая в S(n) со знаком «–». Число А–В, согласно условию задачи, должно делиться на 11. Положим В–А=11, кроме того, очевидно, А+В=1+2+3+…+9=45. Решая полученную систему В–А=11, А+В=45, находим, А=17, В=28. Подберём группу из пяти различных цифр с суммой 17. Например, 1+2+3+5+6=17. Эти цифры возьмём в качестве цифр с нечётными номерами. В качестве цифр с чётными номерами возьмём оставшиеся – 4, 7, 8, 9, 0.

Мы видим, что условию задачи удовлетворяет, например, число 1427385960.

8. Два двузначных числа, записанных одно за другим, образуют четырёхзначное число, которое делится на их произведение. Найти эти числа.

Пусть a и b – два двузначных числа, тогда 100a+b – четырёхзначное число. По условию 100a+b = k·ab, отсюда b = a(kb–100), то есть b делится на a.

Итак, b = ma, но a и b двузначные числа, поэтому m однозначное.

Так как 100a+b = 100a+ ma = а(100+m) и 100a+b = kab, то а(100+m) = kab,

то есть 100+m = kb или 100+m = kma, откуда 100 = m(ka–1).

Таким образом, m – делитель числа 100, кроме того, m – однозначное число, значит, m = 1, 2, 4, 5.

Так как ka = 1+100/m, причём а двузначно, то отпадают для m значения 1 и 5, ибо

при m = 1 число 100/1+1 = 101 не делится ни на какое двузначное число а;

при m = 5 число 100/5+1 = 21 и имеем а=21, при котором b = ma = 5·21 – трёхзначное число.

При m = 2 имеем, ka = 51, a = 17, b = 17·2 = 34;

при m = 4 имеем, ka = 26, a = 13, b = 13·4 = 52.

Ответ: 17 и 34, 13 и 52.

Воспользуемся тем, что сумма одинаковых нечётных степеней двух чисел делится на сумму этих чисел, что следует из известного алгебраического тождества. Можно записать:

2 2k+1 + n 2k+1 = (2 + n)·А₁,

3 2k+1 + (n – 1) 2k+1 = (3 + (n – 1))·А₂ = (2 + n)·А₂,

4 2k+1 + (n – 2) 2k+1 = (4 + (n – 2))·А₃ = (2 + n)·А₃ и так далее, где А_i – некоторые целые числа.

В зависимости от чётности n возможна нехватка числа для образования последней пары, избежать этого позволит умножение на 2, рассматриваемой в условии суммы. Итак,

2(1 2k+1 + 2 2k+1 +. +n 2k+1 ) = 2·1 2k+1 + (2 2k+1 + n 2k+1 ) + (3 2k+1 + (n – 1) 2k+1 ) +. + (n 2k+1 + 2 2k+1 ) =

= 2 + (n + 2)·А, где А – некоторое целое число.

Одно из слагаемых последней суммы делится на n + 2, другое при любых натуральных n – нет. Итак, рассматриваемая в условии сумма не делится на n при любых натуральных n и k.

10. Докажите, что для любого простого числа р > 2 числитель m дроби

Заметим, что число р–1 чётное, и преобразуем дробь m/n к виду

Приводя полученное выражение к общему знаменателю

Задачи без решений

1. Докажите, что при любом натуральном n:

а) число 4 n + 15n – 1 делится на 9;

б) число 3 2n+3 + 40n – 27 делится на 64;

в) число 5 n (5 n + 1) – 6 n (3 n + 2 n ) делится на 91.

а) натуральные значения n такие, что n 5 – n делится на 120;

б) наименьшее натуральное число n такое, что n делится на 19, а n + 2 делится на 82.

3. Пусть m, n – различные натуральные числа, причём m – нечётное. Докажите, что 2 m –1 и 2 n +1 взаимно простые.

4. Четыре различных целых трёхзначных числа, начинающиеся с одной и той же цифры, обладают тем свойством, что их сумма делится на три из них без остатка. Найдите эти числа.

Источник

Два числа при делении на 16 дают остаток 8 доказать что разность

а) Приведите пример такого натурального числа n, что числа n 2 и (n + 16) 2 дают одинаковый остаток при делении на 200.

б) Сколько существует трёхзначных чисел n с указанным в пункте а свойством?

в) Сколько существует двухзначных чисел m, для каждого из которых существует ровно 36 трёхзначных чисел n, таких, что n 2 и (n + m) 2 дают одинаковый остаток при делении на 200.

а) Например, число 17.

б) Если два числа дают одинаковых остаток при делении на 200, то их разность будет делиться на 200. Имеем:

Следовательно, делится на 25, откуда Тогда:

Таким образом, существует 36 чисел.

в) По условию — целое, поэтому m — четное, т.е. Имеем:

— целое, m — двузначное, поэтому

1) Пусть k = 25, тогда n может быть любым трехзначным нечетным числом, которых гораздо больше, чем 36.

2) Пусть но кратно пяти. Значит, (n + k) кратно 10. В зависимости от k подойдут либо все четные трехзначные числа, делящиеся на 5, либо нечетные, делящиеся на 5. В любом случае таких чисел больше 36.

3) Пусть k не кратно 5, k — нечетное, но сумма (n + k) кратна 50. Поскольку то (n + k) с учетом условия принимает все значения, кратные 50, причем на одно значение — одно значение m. Следовательно, для каждого k возможно 18n, что не подходит по условию задачи.

4) Пусть k не кратно 5, k — четное, и сумма (n + k) кратна 25. Рассуждая аналогично пункту 3) при и возможных значений (n + k) — 36, поэтому возможных значений n тоже 36. При и возможных значений (n + k) — 36, поэтому возможных значений n тоже 36. В таблице представлены подходящие k и соответствующие им m. Их 18.

Источник

Два числа при делении на 16 дают остаток 8 доказать что разность

Логический прием, использованный в приведенном доказательстве, называется принципом Дирихле – по имени Петера Густава Дирихле (1805-1895) немецкого математика, автора описанного метода.

Вот общая форма принципа Дирихле:

Если k∙n+1 предмет разложен в k ящиков, то, по крайней мере, в одном из ящиков лежит не меньше, чем n+1 предмет.

По традиции в популярной литературе принцип Дирихле объясняют на примере “зайцев” и “клеток’:

Если N зайцев сидят в n клетках и N>n, то хотя бы в одной клетке сидит более одного зайца.

Этим принципом в неявном виде пользовался, например, Ферма в XVII веке; но широко применяться в доказательствах он стал лишь с прошлого века! Несмотря на свою простоту, это рассуждение оказалось чрезвычайно плодотворным. Вот только один пример. Если делить одно целое число на другое, например 1 на 7, что мы получим? Будем делить в столбик, получая все новые и новые остатки. Но поскольку остатками от деления на 7 могут быть лишь числа 1, 2, 3, 4, 5, 6 и 0, мы либо должны на каком-то шаге получить 0 и остановиться, либо после шестого деления один из остатков обязан повториться. Дальше делить нет смысла — этот остаток мы уже разделили на 7, и все результаты у нас перед глазами. Ясно, что деление будет продолжаться бесконечно, но мы будем получать снова и снова одну и ту же последовательность цифр — период.

Выходит, при делении целого числа на целое мы получим либо конечную десятичную дробь, либо периодическую — и более ничего!

Как видим – все гениальное просто, и к этому же относится и принцип Дирихле.

В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.

Перед нами миллион «кроликов»-елок и, увы, всего лишь 600001 клетка с номерами от 0 до 600000. Каждый «кролик»-елка сажается нами в клетку с номером, равным количеству иголок на этой елке. Так как «кроликов» гораздо больше, чем клеток, то в какой-то клетке сидит по крайней мере два «кролика» – если бы в каждой сидело не более одного, то всего «кроликов»-елок было бы не более 600001 штук. Но ведь, если два «кролика»-елки сидят в одной клетке, то количество иголок у них одинаково.

Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 11.

Остатки по модулю 11 – «клетки», числа – «кролики».

В городе Ленинграде живет более 5 миллионов человек. Докажите, что у каких-то двух из них одинаковое число волос на голове, если известно, что у любого человека на голове менее миллиона волос.

Постройте миллион клеток с номерами от 0 до 999999 и рассадите там людей, поместив каждого ленинградца в клетку, номер которой равен количеству волос на его голове.

В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

25 ящиков-«кроликов» рассадим по 3 клеткам-сортам. Так как 25 = 3 • 8 + 1, то применим «обобщенный принцип Дирихле» для N = 3, k = 8 и получим, что в какой-то клетке-сорте не менее 9 ящиков.

В стране Курляндии m футбольных команд (по 11 футболистов в каждой). Все футболисты собрались в аэропорту для поездки в другую страну на ответственный матч. Самолет сделал 10 рейсов, перевозя каждый раз по m пассажиров. Еще один футболист прилетел к месту предстоящего матча на вертолете. Докажите, что хотя бы одна команда была целиком доставлена в другую страну.

Так как перевезено всего 10m + 1 футболистов, то, рассадив их по клеткам-командам, получаем, что в какой-то клетке сидит 11 футболистов.

Дано 8 различных натуральных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.

Различных разностей может быть 14 – от 1 до 14 – это те 14 клеток, в которые мы будем сажать кроликов. Кто же будет нашими кроликами? Ими, конечно, должны быть разности между парами данных нам натуральных чисел. Однако имеется 28 пар и их можно рассадить по 14 клеткам так, что в каждой клетке будет сидеть ровно два «кролика» (и значит, в каждой меньше трех). Здесь надо использовать дополнительное соображение: в клетке с номером 14 может сидеть не более одного кролика, ведь число 14 можно записать как разность двух натуральных чисел, не превосходящих 15, лишь одним способом: 14 = 15 – 1. Значит, в оставшихся 13 клетках сидят не менее 27 кроликов, и применение обобщенного принципа Дирихле дает нам желаемый результат.

Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании.

Вариантов числа знакомых всего 5: от 0 до 4. Осталось заметить, что если у кого-то 4 знакомых, то ни у кого не может быть 0 знакомых.

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

Пусть всего команд n. Тогда вариантов числа команд, с которыми сыграла данная команда n: от 0 до n – 1. Осталось заметить, что если одна команда сыграла со всеми n – 1-й, то никакая другая команда не могла ни с кем не сыграть.

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

Из условий следует, что найдутся 7 школьников, решивших 35 – 6 = 29 задач. Так как 29 = 4 • 7 + 1, то найдется школьник, решивший не менее пяти задач.

Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никакие два из них не били друг друга?

Ответ: 16 королей. Разобьём доску на 16 квадратиков, в каждом может быть не более одного короля.

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

Каждый из меньших треугольников не может накрывать более одной вершины большого треугольника.

В квадрат со стороной 1 метр бросили 51 точку. Докажите, что какие-то три из них можно накрыть квадратом со стороной 20 см.

Разобьем наш квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле, в какой-то из них попадет по крайней мере три точки из 51 брошенной.

Пятеро молодых рабочих получили на всех зарплату – 1500 рублей. Каждый из них хочет купить себе магнитофон ценой 320 рублей. Докажите, что кому-то из них придется подождать с покупкой до следующей зарплаты.

Если бы каждый из рабочих мог купить магнитофон, то у них в сумме было бы не менее 5 • 320 = 1600 рублей.

В бригаде 7 человек и их суммарный возраст – 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142 лет.

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

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

Рассмотрите 1988 степеней и их остатки по модулю 1987.

Докажите, что из 52 целых чисел всегда найдутся два, разность квадратов которых делится на 100.

Квадраты при делении на 100 могут давать лишь 51 остаток, так как остатки x и 100 – x при возведении в квадрат дают один и тот же остаток.

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

Рассмотрим 1988 чисел-«кроликов» 1, 11, 111, …, 111 … 11 (1988 единиц) и посадим их в 1987 клеток с номерами 0, 1, 2, …, 1986 – каждое число попадает в клетку с номером, равным остатку от деления этого числа на 1987. Тогда (по принципу Дирихле) найдутся два числа, которые имеют одинаковые остатки при делении на 1987. Пусть это числа 11 … 11 (m единиц) и 11 … 11 (n единиц), причем m > n. Но их разность, которая делится на 1987, равна 11 … 1100 … 00 (m – n единиц и n нулей). Сократим все нули – ведь они не имеют никакого отношения к делимости на 1987 – и получим число из одних единиц, которое делится на 1987.

Докажите, что существует степень тройки, оканчивающаяся на 001.

Если 3m и 3n – степени тройки, дающие один и тот же остаток при делении на 1000, то 3m – 3n = 3n(3m – n – 1) делится на 1000 (мы считаем для определенности, что m > n).

Эти суммы могут принимать лишь 7 разных значений: от – 3 до 3.

Сто человек сидят за круглым столом, причем более половины из них – мужчины. Докажите, что какие-то два мужчины сидят друг напротив друга.

Разобьем всех людей на 50 пар так, что в каждой паре – два человека, сидящих друг напротив друга. Ясно, что в одной из этих пар-«клеток» оба человека – мужчины.

15 мальчиков собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов.

Если это не так, то, очевидно, что мальчики собрали не менее, чем 0 + 1 + 2 + … + 14 = 105 орехов – противоречие.

Цифры 1, 2, …, 9 разбили на три группы. Докажите, что произведение чисел в одной из групп не меньше 72.

Произведение чисел во всех группах равно 9! = 362880, а 71? = 357911.

Поскольку от любой клетки до любой другой можно добраться, не более 19 раз сдвинувшись в соседнюю клетку, то все числа находятся между числами a и a + 95, где a – минимальное из всех расставленных чисел. Значит, среди этих чисел не более 96 различных.

Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых.

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

На клетчатой плоскости дано 5 произвольных узлов сетки. Докажите, что середина одного из отрезков, соединяющих какие-то две из этих точек, также является узлом сетки.

Рассмотрите координаты этих точек и их остатки при делении на 2.

На складе имеется по 200 сапог 41, 42 и 43 размеров, причем среди этих 600 сапог 300 левых и 300 правых. Докажите, что из них можно составить не менее 100 годных пар обуви.

В каждом размере каких-то сапог меньше: правых или левых. Выпишем эти типы сапог по размерам. Какой-то тип, например, левый, повторится по крайней мере дважды, например, в 41 и 42 размерах. Но так как количество левых сапог в этих размерах суммарно не меньше 100 (почему?), то мы имеем не менее 100 годных пар обуви в этих размерах.

В алфавите языка племени Ни-Бум-Бум 22 согласных и 11 гласных, причем словом в этом языке называется произвольное буквосочетание, в котором нет двух согласных подряд и ни одна буква не использована дважды. Алфавит разбили на 6 непустых групп. Докажите, что из всех букв одной из групп можно составить слово.

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

Докажите, что среди любых 10 целых чисел найдется несколько, сумма которых делится на 10.

Рассмотрите 10 сумм: x₁, x₁ + x₂, …, x₁ + x₂ + … + x₁₀ и их остатки при делении на 10.

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

Разбейте числа от 1 до 20 на 10 наборов, в каждом из которых в любой паре чисел одно делится на другое: 11, 13, 15, 17, 19, 1,2,4,8,16, 3,6,12, 5,10,20, 7,14, 9,18.

Источник