8
$\begingroup$

Can a 10 * 10 square be paved with 1*4 rectangular stone plates?

I seek a very intuitive and simple answer to this puzzle.

P.S. Will post the source later. The source contains the answer but it is not very intuitive.

$\endgroup$

7 Answers 7

14
$\begingroup$

The following feels intuitive enough to me. Colour the grid as follows.

 R G B Y R G B Y R G
 Y R G B Y …
 B Y R G B …
 …

It’s clear that whichever way you place a 1 × 4 tile, it covers all four colours. But the number of R cells is larger than the number of B cells, so the grid can’t be tiled.

$\endgroup$
0
9
$\begingroup$

A very simple approach is to tile the 10x10 square

with alternating 2x2 squares of +1 and -1:

In the picture +1 and -1 are abbreviated + and -:

    + + - - + + - - + +
    + + - - + + - - + +
    - - + + - - + + - -
    - - + + - - + + - -
    + + - - + + - - + +
    + + - - + + - - + +
    - - + + - - + + - -
    - - + + - - + + - -
    + + - - + + - - + +
    + + - - + + - - + +
 

Every 1x4 or 4x1 tile covers

2 + and 2 -. The net total under each such tile is therefore zero and the same must hold for the area covered by any number of 1x4 and 4x1 tiles.

But there are 5x5 = 25, an odd number, of 2x2 squares meaning that they can't split evenly between + and -. The overall sum cannot be zero (it is +4) and hence a tiling cannot exist.

$\endgroup$
9
$\begingroup$

A proof without a colouring is as follows:

Every row must intersect 2,6 or 10 vertical tiles. In particular, the number of vertical tiles is even.

By the same token the number of horizontal tiles is even. But the total number of tiles must be 25, an odd number and a contradiction.

$\endgroup$
2
  • $\begingroup$ "In particular, the number of vertical tiles is even." That's true but is it obvious? Like it's not true on a toroidal board. Is it easier than I'm thinking? $\endgroup$ Commented 14 hours ago
  • $\begingroup$ @TylerSeacrest the difference between any two rows is even. The number of vertical tiles starting at any level must therefore be even. $\endgroup$ Commented 10 hours ago
3
$\begingroup$

The following well-known solution is so simple that it even does not need a coloring. :-)

Let $A$ be the square $[0,10]\times [0,10]$. Suppose for a contradiction that $A$ can be paved with $1\times 4$ rectangular plates $A_1,\dots, A_n$. Put $f(x,y)=\sin \frac\pi{2} x\cdot\sin \frac\pi{2} y$ for each $x,y\in A$. enter image description here

Then $$\int\int_A f(x,y)\, dx\, dy=\int_0^{10}\sin \frac\pi{2} x\, dx\cdot \int_0^{10} \sin \frac\pi{2} y\, dy =$$ $$\left(\frac {(-2)}{\pi}\cdot \cos\frac\pi{2} t{\Big|}_0^{10}\right)^2=\left(\frac {(-2)}{\pi}(\cos 5\pi-\cos 0)\right)^2=\left(\frac 4{\pi}\right)^2\ne 0.$$

On the other hand, we can similarly show that for each natural $i\le n$ we have $$\int\int_{A_i} f(x,y)\, dx\, dy=0.$$

But then $$0\ne \int\int_A f(x,y)\, dx\, dy = \int\int_{\bigcup_{i=1}^n A_i} f(x,y)\, dx\, dy=$$ $$\sum_{i=1}^n \int\int_{A_i} f(x,y)\, dx\, dy = \sum_{i=1}^n 0=0,$$ a contradiction.

$\endgroup$
3
  • $\begingroup$ @vallev Thanks for adding the graph of the function $f(x,y)$. Concerning your second edit, I think that the fraction should be inverted, see the update. $\endgroup$ Commented 16 hours ago
  • $\begingroup$ "invert, always invert" :) $\endgroup$ Commented 15 hours ago
  • 2
    $\begingroup$ Throwing geometry functions and integrals onto an otherwise discrete problem does not make it particularly intuitive. Does it? At least, in a discrete maths course this solution would not be accepted ;-) $\endgroup$ Commented 10 hours ago
3
$\begingroup$

Use the Integer-Rectangle Tiling Lemma:

Whenever a rectangle is tiled by rectangles each of which has at least one integer side, then the tiled rectangle has at least one integer side.

Scale down the sides in the puzzle from "Can a 10×10 square be tiled with 1×4 rectangles?" to "Can a 2.5×2.5 square be tiled with 0.25×1 rectangles?

Answer: NO (the big rectangle has no integer sides, but the small rectangles all do)

$\endgroup$
2
$\begingroup$

Pranay answers the question, but upon further review you don't need an exact count of each color square. You need only to distinguish even from odd, making this a "parity check" puzzle.

Using Pranay's pattern

 R G B Y R G B Y R G
 Y R G B Y …
 B Y R G B …
 …

we note that

the diagonal rows of R squares each contain an even number (the longest such row is ten and others come in decrements of four), but to cover the grid we would need an odd number (25) of tiles each covering one R square.

$\endgroup$
0
$\begingroup$

Here's an approach via linear programming, where the dual variables suggest a coloring that automatically yields a certificate of infeasibility.

For each possible $1 \times 4$ rectangle $r$, let binary decision variable $x_r$ indicate whether that rectangle is used. For each cell $(i,j)$, let binary decision variable $y_{ij}$ indicate whether that cell is uncovered. Let $R_{ij}$ be the set of rectangles that cover cell $(i,j)$. The problem is to minimize $$\sum_{i=1}^{10} \sum_{j=1}^{10} y_{ij}$$ subject to linear constraints \begin{align} \sum_{r \in R_{ij}} x_r + y_{ij} &= 1 &&\text{for $(i,j)\in [10]\times[10]$} \end{align} The minimum turns out to be $4$, meaning that $4$ cells are uncovered. The resulting optimal dual variables are: enter image description here

In this coloring, every $1 \times 4$ rectangle has sum $0$, but the entire grid has sum $4$ and so cannot be partitioned. Or just forget the numbers and note that each rectangle contains exactly one blue square; we need $25$ rectangles, but there are only $24$ blue squares.

An alternative optimal dual solution is: enter image description here

As in the previous coloring (which is the same as the one in the answer by @Albert.Lang), every $1 \times 4$ rectangle has sum $0$, but the entire grid has sum $4$ and so cannot be partitioned.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.