Страница:
<< 6 7 8 9 10 11 12 >> [Всего задач: 323]
|
|
|
Сложность: 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. Легко видеть, что оно имеет только один положительный корень, а это и означает, что каждый имеет одинаковое число знакомых.
|
|
|
Сложность: 4
Классы: 7,8,9
|
В классе 33 человека. У каждого ученика спросили, сколько
у него в классе тезок и сколько однофамильцев (включая родственников).
Оказалось, что среди названных чисел встретились все целые от 0 до 10
включительно. Докажите, что в классе есть два ученика с одинаковыми именем
и фамилией.
Решение
Объединим учеников в группы по фамилиям и в группы по именам
(возможны группы, состоящие из одного человека – например, ученик
без однофамильцев). Каждый войдет в две группы – по фамилии и по
имени. Из условия задачи следует, что в классе ровно одиннадцать
групп. Действительно, есть группы, состоящие из 1, 2, 11
человек, поэтому групп не меньше одиннадцати, но
1
+2
+...+11
=66
=2
· 33
, т.е. мы уже сосчитали каждого ученика
дважды, значит, больше групп нет.
Рассмотрим группу из одиннадцати человек (скажем, однофамильцев).
Остальных групп, и, в частности, групп тезок, не более десяти.
Поэтому какие-то двое из одиннадцати входят в одну группу тезок,
т.е. у них одинаковы и имя, и фамилия.
|
|
|
Сложность: 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.
Ответ
Эти суммы одинаковы.
|
|
|
Сложность: 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 пар.
|
|
|
Сложность: 4
Классы: 8,9,10
|
300 бюрократов разбиты на три комиссии по 100 человек. Каждые два бюрократа либо знакомы друг с другом, либо незнакомы. Докажите, что найдутся два таких бюрократа из разных комиссий, что в третьей комиссии есть либо 17 человек, знакомых с обоими, либо 17 человек, незнакомых с обоими.
Решение
Для трёх бюрократов A, B, C из разных комиссий, будем говорить, что B и C похожи для A, если A либо знаком с обоими бюрократами B и C, либо незнаком с обоими. Для каждой пары бюрократов из разных комиссий найдём количество бюрократов в третьей комиссии, для которых они похожи. Оценим сумму s всех этих 3·100·100 чисел. В каждой тройке бюрократов A, B, C из разных комиссий есть либо две пары знакомых, либо две пары незнакомых между собой. Значит, два из них являются похожими для третьего, и вклад каждой тройки в сумму s не меньше 1. Следовательно, сумма s не меньше, чем число троек бюрократов, то есть s ≥ 100·100·100 = 106, и поэтому одно из слагаемых не меньше 106 : (3·104) = 100 : 3, то есть не меньше 34. Таким образом, какая-то пара бюрократов из разных комиссий является похожей не меньше чем для 34 бюрократов из третьей. Значит, эти два бюрократа либо знакомы хотя бы с 17 бюрократами из оставшейся комиссии, либо незнакомы хотя бы с 17 бюрократами из оставшейся комиссии.
Страница:
<< 6 7 8 9 10 11 12 >> [Всего задач: 323]
Фильтр
