Making a $m*n$ chocolate bar out of $1*k$ chocolate bars

Question

So I've been puzzled by this problem for some time now: Suppose we have a chocolate bar with dimensions $m*n$ and it is made up out of finite number of $1*k$ chocolates. Proof that for any natural numbers m,n,k, in order for chocolate to be made, k must devide at least one of m,n. Now this solution come so logical to me that I can't even start thinking about a way to obtaining it. I would really appreciate your help. Thanks.

Answer 1

Let $D=\{(x,y)\in\mathbb R^2|0\leq x \leq m,0 \leq y \leq n\}$. Then $D$ is the union of subsets of the type $\{i\leq x \leq i+1,j\leq y \leq j+k \}$ or $\{i\leq x \leq i+k,j\leq y \leq j+1\}$. Now $$\int_D\sin (\frac{2\pi}{k}x)\sin (\frac{2\pi}{k}y)dxdy=0$$ because on each of the aforementioned subsets this integral vanishes. On the other hand $$\int_D\sin(\frac{2\pi}{k}x)\sin(\frac{2\pi}{k}y)dxdy=\int_0^m\sin(\frac{2\pi}{k}x)dx\int_0^n\sin(\frac{2\pi}{k}y)dy$$ so one of these two integrals must vanish. This yields that either $k|m$ or $k|n$.

Answer 2

Here is another proof using coloring ideas. Write it as a matrix $m*n$. Now number rows form $\{0,1,2,...,m-1\}$. Similarly number columns as $\{0,1,2,...,n-1\}$.Now each element of the matrix is defined to be $r+c \hspace{1mm}mod\hspace{1mm}k$,where $r$ is the number of the row and $c$ is the number of the column.Now wlog say $k\nmid m$.Now we try to show that it has to definitely divide $n $.Now we observe that in this coloring the number of $0's,1's,2's...$ should be same or else we cannot cover it with $1*k$ tiles. Since where ever we put $1*k$ block it will have all the numbers from $0$ to $k-1$.So now we have to exhibit a number which is there in the matrix not $m*n/k$ times.

To find that number let $r_1 \equiv m \hspace{1mm}mod\hspace{1mm}k$ and $r_2 \equiv n \hspace{1mm}mod\hspace{1mm}k$.Then it is clear that $r_1$ repeats more than $mn/k$ if $r_2 \neq 0$.The number $r_1$ appears $[(m/k)]$+1 times in first row and this trend continues for the next $r_1$ columns and till k th column is reached it remains to be only [$m/k$].So in k columns the number of times numbers repeat will be $m$.Hence $r_1$ is a number which repeats more than $mn/k$ times.