Областная олимпиада по математике, 2012 год, 10 класс

Полное замощение прямоугольника $2m\times n$ с помощью $mn$ прямоугольных плиток $2\times 1$ называется $\textit{трансверсальным}$, если найдется прямая, делящая прямоугольник на две непустые части и не проходящая через внутренние точки плиток.
а) Докажите, что любое замощение прямоугольника $6\times 6$ с помощью 18 плиток является трансверсальным.
б) Найдется ли не трансверсальное замощение прямоугольника $6\times 7$ с помощью 21 плитки?

Комментарий/решение

а) 6*6 болатын тіктөртбұрыштың яғни, шаршының 18 плиткамен жабуының кез келген түрі трансверсалды болады. Себебі, біріншіден бұл фигура шаршы яғни 6 клетканы 2 ге және 1 ге бөлгенде ешқандай қалдық қалмайды. Сондықтан да плиткалардың қалай орналасқанына қарамастан, бұл фигураның қақ ортасынан жүргізілген түзу плиткаларды қимайды. Әрине плиткалардың қалай орналасқанына тікелей байланысты.

б) Жоғарыда көрсеткен дәлелдеуге сүйеніп 6*7 болатын тіктөртбұрыштың 21 плиткамен трансверсальды емес жабуы табылады деп айта аламын. 7 2ге қалдықсыз бөлінбейді . Яғни плиткалардың барлығын вертикаль қою қолдан келсе ал горизанталь қою мүмкін емес. Сәйкесінше, трансверсальды емес жабуы табылады.

Бұл дәлелдер мүлдем шешім емес. Тақта өлшемі мен оның ұзындығының көлденеңдігімен паритетінің арасында қандай байланыс бар?

a) Очевидно, что достаточно рассмотреть только линии, идущие по линиям сетки (при любом замощении плитками они занимают клетки целиком, поэтому любая линия, не проходящая по сетке, будет пересекать доминошки). В квадрате $6\times 6$ есть по пять линий разбиения, идущих по сеткам (делящие 1 и 2 горизонталь, 2 и 3 горизонталь и так далее, то же с вертикалями). Рассмотрим произвольное замощение прямоугольника $6\times 6$. Если это замощение не трансверсально, то каждая прямая сетки пересекает хотя бы одну доминошку. Теперь возьмем произвольную линию. Она делит квадрат на два прямоугольника: $k\times 6$ и $(6-k)\times 6$ , где $k=1,2,3,4,5$. В каждом из этих прямоугольников четное число клеток. Соответственно, если выбранная линия проходит хотя бы через одну доминошку (то есть одна клетка доминошки лежит в одном прямоугольнике. а другая -- в другом), то таких доминошек должно быть четное число, а значит как минимум 2. Действительно, если в одном прямоугольнике размещены $m$ доминошек и еще одна разрезается выбранной линией, то площадь этого прямоугольника должна быть $2m+1$, но эта площадь четна, противоречие. Итак, так как приведенные рассуждения верны для любой линии сетки, каждая линия сетки пересекает хотя бы две доминошки. Таким образом, общее количество разрезаемых доминошек равно $2 \cdot (5+5)=20$, так как ни одна доминошка не пересекается более чем одной линией сетки. Однако количество доминошек равно $\dfrac{6^2}{2}=18<20$, противоречие. Следовательно любое замощение трансверсально.