A special kind of parallelogram tile is made up by attaching the legs of two right isosceles triangles of side length $1$. We want to put a number of these tiles on the floor of an $n\times n$ room such that the distance from each vertex of each tile to the sides of the room is an integer and also no two tiles overlap. Prove that at least an area $n$ of the room will not be covered by the tiles. Proposed by Ali Khezeli
Problem
Source: Iran TST 2013-Third exam-2nd day-P6
Tags: geometry, parallelogram, rotation, combinatorics proposed, combinatorics
01.06.2013 06:16
By side length 1 do you mean the sides of the parallelogram are $1, \sqrt{2}, 1, \sqrt{2}$? Can tiles be rotated?
02.06.2013 05:30
Yes, they have side lengths as you said. And of course, they can be rotated.
21.06.2013 16:08
here his solution is: the first step is clear ,that most of us take it,make the tiles into chain, a chain is made up with some unit squres,that means if two tiles have common $ \sqrt2$side,weld them,we get seveal "squre chain" (the vertises are half squres,but no problem,we can consider it a squre chain)for each chain,the area of the uncoverd is 1,and we can easily get the chain,is the "shortist path" that we can call it increase progressively or decrease progressively(specially a single squre can call a chain,too) then if less than n,we can assume area of (n-1) isn't coverd, that is exactly (n-1)chain cover the room for each chain first,we define a "start point" at each column that for a increase progressively one ,the start point is the one (in every cloumn) whose y coodinate is the min for a decrease progressively one ,the start point is the one (in every cloumn) whose y coodinate is the max the other squre,call them "normal" and for every chain define the vertex,is the first starting point so many deffination but that's all important and the main idea is about the "normal" then assume inthe first cloumn there's k vertex then,in the first column,there's n-k normal for each normal it can "creat" a new normal in the next cloumn for the increase chain,a normal "create" a new normal in 45 down for the decrease chain,a normal "create" a new normal in 45 up except the new "normal" is a vertex but there are only (n-1)-k vertex not in first cloumn so at least one normal in the first cloumn ,can creat a squense length n that is from the first cloumn to the n'th cloumn and not very hard to prove that each chain at most 1 normal in that normal squense,then get a contradiction so at least area of n not be covered. done.