4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Arthur Mar 3 '14 at 7:18
  • $\begingroup$ 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. $\endgroup$ – Transcendental Mar 3 '14 at 7:21
  • $\begingroup$ It's homework in what? Are you supposed to use calculus? $\endgroup$ – alex Mar 3 '14 at 7:28
  • $\begingroup$ 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.. $\endgroup$ – Transcendental Mar 3 '14 at 7:32
4
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ @alex finally a colouring proof $\endgroup$ – happymath Mar 4 '14 at 9:18
  • $\begingroup$ I'm not sure I understand the last part. Could you expand it? $\endgroup$ – alex Mar 4 '14 at 14:13
  • $\begingroup$ 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. $\endgroup$ – alex Mar 4 '14 at 14:47
  • $\begingroup$ @alex edited it. $\endgroup$ – happymath Mar 4 '14 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.