Вход через социальные сети

Школьная математика

Покрашенная доска

  • 27.04.2011, 02:34
    0 up down
    Сообщение
    27 и 6?
  • 27.04.2011, 10:44
    0 up down
    Сообщение
    malk в 27.4.2011, 0:34 написал(а): link

    27 и 6?

    Я так понимаю, что под словом "шесть" Вы имели в виду число способов раскраски 27 клеток соответствующим образом. Вот как раз это я и не смогла доказать. Зато доказала, что задача имеет ровно одно решение: 27 клеток.

    Разобьём доску на прямоугольники следующим образом:

    1. a1, b1, c1
    2. a2, b2, c2, a3, b3, c3
    3. a4, b4, c4, a5, b5, c5
    4. a6, b6, c6, a7, b7, c7
    5. a8, b8, c8, a9, b9, c9
    6. d1, e1, d2, e2, d3, e3
    7. d4, e4, d5, e5, d6, e6
    8. d7, e7, d8, e8, d9, e9
    9. f1, g1, f2, g2, f3, g3
    10. f4, g4, f5, g5, f6, g6
    11. f7, g7, f8, g8, f9, g9
    12. h1, i1, h2, i2, h3, i3
    13. h4, i4, h5, i5, h6, i6
    14. h7, i7, h8, i8, h9, i9

    Итак, мы имеем 13 прямоугольников нужных нам размеров и ещё один маленький.
    B 13 должно быть ровно 26 клеток по условию, значит, всего может быть 26, 27, 28 или 29.

    29 отметаем сразу же, ибо тогда в прямоугольнике a1, a2, a3, b1, b2, b3 будет больше двух клеток.

    Теперь пусть клеток ровно 26. Разобьём всю доску на квадратики 3\times 3. Хотя бы в одном из квадратиков должно быть менее трёх клеток. Ровно одна клетка, очевидно, быть не может. Значит их ровно две. B верхней строчке квадратика не может быть чёрной клетки, ибо тогда в прямоугольнике, образованном двумя другими строчками будет ровно одна клетка, a их должно быть две. Аналогично, чёрной клетки не может быть в нижней строчке, a также в левом и правом столбцах. Значит, чёрная клетка может быть лишь в центре. Ho тогда она одна, a не две! Противоречие.
    Итак, 26 мы тоже отметаем.

    Отметём и 28.
    Если клеток 28, то в какм-то квадратике 3\times 3 будет 4 клетки. Ho тогда в соседнем c ним квадратике должно быть ровно две (a мы уже доказали, что это невозможно)! Почему? Да потому, что два таких квадратика образуют три прямоугольника 3\times 2, значит, всего в них должно быть 6 клеток.

    Итак, можно только 27.

    Пример:

    c1, f1, i1, b2, e2, h2, a3, d3, g3,
    c4, f4, i4, b5, e5, h5, a6, d6, g6,
    c7, f7, i7, b8, e8, h8, a9, d9, g9.

    Ho вот как доказать, что более шести способов раскрасить 27 клеток не существует, я, к стожалению, не знаю Dash 1


  • 27.04.2011, 11:52
    0 up down
    Сообщение
    1. Разобьем квадрат на 9 квадратиков 3*3. Если не использовать любой из этих квадратиков, большой квадрат можно замостить 12 прямоугольниками. Если взять 9 таких квадратов c вырезами, то все клетки большого квадрата будут использоваться 8 раз. Итого 12*2*9/8=27.
    2. Рассмотрим маленький квадратик 3*3. B нем не менее 3 черных клеток. Если в каком-нибудь квадратике больше 3, то и в большом квадрате больше 27. Значит в квадратике ровно 3 черных клетки.
    Значит в прямоугольниках 1*3 и 3*1 ровно одна такая клетка. Следовательно вариантов расстановки в квадратике 6. Дальше несложно(если, конечно, я не ошибаюсь).
  • 27.04.2011, 15:07
    0 up down
    Сообщение
    что-то я не очень понял предложенные решения, поэтому приведу свое

    итак

    1. Никакие две смежные по вертикали/горизонтали клетки не могут быть одновременно черными.
    Доказательство
    пусть это так тогда получается:
    \to\to
    (зеленым обозначены клетки которые закрашиваем в черный, желтым -- в белый, белым обозначены неопределенные клетки)

    2. Теперь выберем некоторый прямоугольник 2x3 (или 3x2) у которого есть черная угловая клетка, например такой:

    и попытаемся произвести дальнейшую закраску:
    \to\to\to\to\to\to
    обратите внимание что на каждом шаге клетки для закрашивания определяются однозначно (кроме 3-го где можно было выбрать 1 из 2-х диагоналей)
    И похоже вырисовывается система: черные клетки образуют диагонали так, что каждые две соседние черные диагонали разделяются 2-мя белыми (кроме крайних)
    Получается что если гипотеза верна, то черных и вправду ровно 27 при этом способ раскраски только 1 (если не считать повороты и отражения)
  • 27.04.2011, 15:41
    0 up down
    Сообщение
    P.S. немного соврал: основных способов закраски 2: когда главная диагональ доски черная и нет