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

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.

• If it's so easy, how do you know there isn't some humongous rectangle that can be filled by using size $1\times 1\,806\,732$ chocolate bars? – Arthur Mar 3 '14 at 7:18
• I am sorry for causing confusion. I didn't say it's easy to prove. I said I can't think of an example that doesn't follow this 'rule'. It makes sense but I can't find a proof. – Transcendental Mar 3 '14 at 7:21
• It's homework in what? Are you supposed to use calculus? – alex Mar 3 '14 at 7:28
• Well its basically math homework, we did calculus, but I dont think we're allowed to use is since this is first year revision. But I would like to see any solution.. – Transcendental Mar 3 '14 at 7:32

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$.

• nice proof seeing a calculus based proof for tiling problems for the first time – happymath Mar 3 '14 at 8:54
• @user129901 I'd like to see another one. – alex Mar 3 '14 at 9:22

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.

• @alex finally a colouring proof – happymath Mar 4 '14 at 9:18
• I'm not sure I understand the last part. Could you expand it? – alex Mar 4 '14 at 14:13
• I also am not clear about "or else we would have proved the claim". To me it is clear that if $k|n$ then any number in $\{0,\ldots ,k-1\}$ must appear the same number of times, as any row is filled by such $1 \times k$ blocks. But: if any number in $\{0,\ldots ,k-1\}$ appears the same number of times, then $k|n$, that is not. – alex Mar 4 '14 at 14:47
• @alex edited it. – happymath Mar 4 '14 at 15:18