ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 314]      



Задача 78128

Темы:   [ Разбиения на пары и группы; биекции ]
[ Десятичная система счисления ]
Сложность: 4
Классы: 9,10,11

Доказать, что число всех цифр в последовательности 1, 2, 3,..., 10k равно числу всех нулей в последовательности 1, 2, 3,..., 10k + 1.

Решение

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


Задача 78236

Темы:   [ Разбиения на пары и группы; биекции ]
[ Сочетания и размещения ]
[ Квадратные уравнения. Теорема Виета ]
[ Теория графов (прочее) ]
Сложность: 4
Классы: 8,9,10,11

Собралось n человек. Некоторые из них знакомы между собой, причём каждые два незнакомых имеют ровно двух общих знакомых, а каждые два знакомых не имеют общих знакомых. Доказать, что каждый из присутствующих знаком с одинаковым числом человек.

Решение

  Пусть кто-то из собравшихся – назовём его X – имеет m знакомых: a1, a2, ..., am. По условию, никакие два человека из a1, a2, ..., am друг с другом не знакомы. Значит, для каждых двух человек ai, aj должен найтись ещё один общий знакомый кроме X. Этот человек не знаком с X; при этом разным парам  (ai, aj)  должны соответствовать разные люди (если бы один и тот же человек был общим знакомым одновременно для двух таких пар, то он имел бы с X более двух общих знакомых). Мы видим, что число всех людей, не знакомых с X, не меньше, чем число  ½ m(m – 1)  пар из людей a1, a2, ..., am.
  С другой стороны, каждый человек, не знакомый с X, имеет с ним ровно двух общих знакомых – разумеется, из числа a1, a2, ..., am. При этом разным людям соответствуют разные пары. Таким образом, число людей, не знакомых с X, не больше, чем  ½ m(m – 1).  Следовательно,  n = 1 + m +  ½ m(m – 1).  Мы получили квадратное уравнение относительно m. Легко видеть, что оно имеет только один положительный корень, а это и означает, что каждый имеет одинаковое число знакомых.

Прислать комментарий

Задача 109658

Темы:   [ Разбиения на пары и группы; биекции ]
[ Принцип Дирихле (прочее) ]
[ Арифметическая прогрессия ]
Сложность: 4
Классы: 7,8,9

В классе 33 человека. У каждого ученика спросили, сколько у него в классе тезок и сколько однофамильцев (включая родственников). Оказалось, что среди названных чисел встретились все целые от 0 до 10 включительно. Докажите, что в классе есть два ученика с одинаковыми именем и фамилией.

Решение

Объединим учеников в группы по фамилиям и в группы по именам (возможны группы, состоящие из одного человека – например, ученик без однофамильцев). Каждый войдет в две группы – по фамилии и по имени. Из условия задачи следует, что в классе ровно одиннадцать групп. Действительно, есть группы, состоящие из 1, 2, 11 человек, поэтому групп не меньше одиннадцати, но 1+2+...+11=66=2· 33 , т.е. мы уже сосчитали каждого ученика дважды, значит, больше групп нет.
Рассмотрим группу из одиннадцати человек (скажем, однофамильцев). Остальных групп, и, в частности, групп тезок, не более десяти. Поэтому какие-то двое из одиннадцати входят в одну группу тезок, т.е. у них одинаковы и имя, и фамилия.
Прислать комментарий


Задача 109745

Темы:   [ Разбиения на пары и группы; биекции ]
[ Суммы числовых последовательностей и ряды разностей ]
[ Четность и нечетность ]
Сложность: 4
Классы: 7,8,9

Числа от 1 до 999999 разбиты на две группы: в первую отнесено каждое число, для которого ближайшим к нему квадратом является квадрат нечётного числа, во вторую – числа, для которых ближайшими являются квадраты чётных чисел. В какой из групп сумма чисел больше?

Решение

  Разобьём числа от n² до  (n + 1)² – 1  на две группы  An = {n², n² + 1, ..., n² + n}  и  Bn = {n² + n + 1, n² + n + 2, ..., n² + 2n}.
  Для чисел группы An ближайшим квадратом является n², для Bn ближайшим является  (n + 1)²  – квадрат другой чётности.
  Суммы чисел в группах An и Bn обозначим S(An) и S(Bn) соответственно. Из равенства
S(Bn) – S(An) = ((n² + n + 1) – (n² + 1)) + ((n² + n + 2) – (n² + 2)) + ... + ((n² + 2n) – (n² + n)) – n² = n·n – n² = 0  следует, что суммы чисел в группах An и Bn равны.
  Осталось заметить, что все множество чисел от 1 до 999999 разбивается на непересекающиеся пары A1 и B1, A2 и B2, A999 и B999.

Ответ

Эти суммы одинаковы.

Прислать комментарий

Задача 110126

Темы:   [ Разбиения на пары и группы; биекции ]
[ Задачи с ограничениями ]
[ Степень вершины ]
Сложность: 4
Классы: 8,9,10

На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?

Решение

  Поскольку  45 = 1 + 2 + 3 + ... + 9,  можно разбить 45 человек на группы по 1, 2, ..., 9 человек. Пусть люди, принадлежащие одной группе, не знакомы между собой, а люди, принадлежащие разным группам, знакомы. Тогда каждый человек из k-й группы имеет  45 – k  знакомых.

При этом условие задачи выполнено, и общее количество пар знакомых людей равно  
  Докажем, что большего числа знакомств быть не могло. Зафиксируем некоторое k,  0 ≤ k ≤ 44.  Пусть некоторый выпускник знаком ровно с k другими. По условию никакой из его знакомых не может иметь ровно k знакомых. Поэтому количество выпускников, знакомых ровно с k другими, не превосходит
45 – k.
  Обозначим через  A0, A1, ..., A44  количество выпускников, имеющих соответственно 0, 1, ..., 44 знакомых. Как показано выше,  Ak ≤ 45 – k,  кроме того,  A0 + A1 + ... + A44 = 45.
  Оценим общее число знакомств:   2S = A1 + 2A2 + ... + 44A44 = A44 + (A44 + A43) + ... + (A44 + A43 + ... + A36) + ... + (A44 + A43 + ... + A0) ≤
≤ 1 + (1 + 2) + ... + (1 + 2 + ... + 9) + 45 + 45 + ... + 45 = 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 36·45 = 1740.

Ответ

870 пар.

Прислать комментарий

Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 314]      



© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .