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

   Решение

Можно ли число ¹/₁₀ представить в виде произведения десяти положительных правильных дробей?

   Решение

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

   Решение

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

   Решение

Доказать, что  776⁷⁷⁶ + 777⁷⁷⁷ + 778⁷⁷⁸  делится на 3.

   Решение

Когда встречаются два жителя Цветочного города, один отдает другому монету в 10 копеек, а тот ему - 2 монеты по 5 копеек. Могло ли случиться так, что за день каждый из 1990 жителей города отдал ровно 10 монет?

   Решение

Известно, что  p > 3  и p – простое число. Как вы думаете:
  а) будут ли чётными числа  p + 1  и  p – 1;
  б) будет ли хотя бы одно из них делиться на 3?

   Решение

Найдите два таких простых числа, что и их сумма, и их разность – тоже простые числа.

   Решение

Углы треугольника ABC связаны соотношением  3α + 2β = 180°. Докажите, что  a² + bc = c².

   Решение

Найти остаток  13¹⁶ – 2⁵⁵·5¹⁵  от деления на 3.

   Решение

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

   Решение

Темы:    [ Теория графов (прочее) ] [ Принцип Дирихле (прочее) ] [ Сочетания и размещения ] [ Доказательство от противного ] [ Разбиения на пары и группы; биекции ]

Сложность: 3 Классы: 7,8,9

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

Условие

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

Решение

  а) Рассмотрим граф с четырьмя вершинами A, B, C, D, соответствующими людям, и соединим ребрами людей, знающих общий язык. Условие означает, что каждая тройка вершин соединена хотя бы двумя рёбрами. А доказать нужно, что есть два ребра без общих вершин. Пусть это неверно.
  Первый способ. Если в тройке  (A, B, C)  проведены рёбра AB и AC, то рёбер BD и CD нет. Но тогда в тройке  (B, C, D)  не больше одного ребра. Противоречие.
  Второй способ. Всего есть 4 тройки. Каждое ребро входит в две тройки. Следовательно, рёбер не менее  4·2 : 2 = 4.  С другой стороны, каждому ребру соответствует отсутствующее "противоположное" ребро. Следовательно, рёбер не более трёх. Противоречие.

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

Источники и прецеденты использования