Занятия Вечерней Математической Школы проходят в девяти аудиториях. Среди прочих, на эти занятия приходят 19 учеников из одной и той же школы.
  а) Докажите, что как их не пересаживай, хотя бы в одной аудитории окажется не меньше трех таких школьников.
  б) Верно ли, что в какой-нибудь аудитории обязательно окажется ровно три таких школьника?

   Решение

Темы:    [ Раскраски ] [ Куб ] [ Ломаные и пространственные многоугольники ] [ Четность и нечетность ]

Сложность: 5- Классы: 9,10,11

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

Условие

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

Решение

  Пусть PQ – горизонтальное ребро одного из кубиков. Обозначим через C_PQ вертикально расположенный прямоугольник, нижняя сторона которого – PQ, а верхняя лежит на поверхности куба.
  Пусть n_PQ – число пересечений данной ломаной с прямоугольником C_PQ. Ребро PQ окрасим в белый цвет, если n_PQ чётно, и в чёрный, если n_PQ нечётно. Все вертикальные рёбра кубиков, окрасим в белый цвет. Докажем, что приведённая раскраска удовлетворяет условию.
  Пусть PQRS – вертикальная грань и PQ и RS – её горизонтальные рёбра. Если ломаная не пересекает PQRS, то прямоугольники C_PQ и C_RS пересекаются с ломаной в одних и тех же точках. Поэтому рёбра PQ и RS окрашены в один цвет, и, следовательно, эта грань удовлетворяет условию. Если же ломаная пересекает прямоугольник PQRS, то n_PQ и n_RS отличаются на 1 и, следовательно, имеют разную чётность. Поэтому ребра PQ и RS окрашены в разные цвета, что означает выполнение условия и в этом случае.
  Пусть теперь PQRS – горизонтальная грань. Объединение прямоугольников C_PQ, C_QR, C_RS и C_SP есть боковая поверхность параллелепипеда, состоящего из кубиков, расположенных в точности над гранью PQRS. Замкнутая ломаная пересекает поверхность этого параллелепипеда чётное число раз (сколько раз ломаная заходит внутрь параллелепипеда, столько раз она и выходит из него).
  Заметим, что ломаная не пересекает верхнюю грань параллелепипеда.
  Если грань PQRS не отмечена, то ломаная не пересекает её. Тогда все точки пересечения ломаной с поверхностью параллелепипеда расположены на его боковой поверхности. В этом случае сумма  n_PQ + n_QR + n_RS + n_SP   чётна. Поэтому число чёрных сторон грани PQRS чётно.
  Если же грань PQRS отмечена, то одна из точек пересечения ломаной с поверхностью параллелепипеда принадлежит PQRS. Тогда сумма
n_PQ + n_QR + n_RS + n_SP  нечётна и, следовательно, нечётное число сторон грани PQRS окрашено в чёрный цвет.

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