What is the fewest polyominoes you need so that any one of the numbers $0$ to $9$ can be constructed?
When constructing, polyominoes may be rotated and flipped, but may not overlap.
Bonus: How few would you need if overlapping was allowed?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ We're allowed to mix sizes? E.g. the answer might be something like "this domino, these two trominoes, and this tetromino"? $\endgroup$ – Rand al'Thor Mar 7 '20 at 8:55
-
1$\begingroup$ Sure, all polyominoes are allowed. $\endgroup$ – Jens Mar 7 '20 at 8:57
-
$\begingroup$ I read it as polynomials and was expecting a math question. $\endgroup$ – qwr Mar 8 '20 at 5:47
Add a comment
|
$\begingroup$
$\endgroup$
2
Non-overlapping
It can be done using
5 polyominoes: two dominoes, one straight tromino, and two L-tetrominoes.
As follows:
(dominoes in red and orange, tromino in the original green, tetrominoes in dark blue and light blue).
Proof that this is minimal:
The number of squares in each digit is respectively 12, 5, 11, 11, 9, 11, 12, 7, 13, 10. Let's assume we can use just 4 polyominoes.
If we use anything bigger than a pentomino (a polyomino of 6 or more squares), then it's impossible: we can't even find four numbers $a,b,c,d$, one of them at least 6, which can be used to make sums that come to each of $5,7,9,10,11,12,13$. (This is by trial and error, but you can see that it's true by trying to mess around with the numbers.)
In fact, the same is true even if we use a pentomino: the best we can get is $a,b,c,d=2,3,4,5$, which gives us sums for all the numbers except $13$. ($2,3,3,5$ wouldn't give $9$; $2,4,4,5$ wouldn't give $12$; $2,2,4,5$ wouldn't give $10$; and so on.) So we must use only tetrominoes at largest.
Now how do we cover the digit 1? It must be with a domino and a straight tromino. So we have $a,b,c,d\leq4$ with $a=2$ and $b=3$; to be able to sum to $13$, we must have $c=d=4$, i.e. two tetrominoes. But using the numbers $2,3,4,4$ we can't get a sum of $12$. Contradiction!
Overlapping
It can be done using
3 polyominoes, as shown in Glorfindel's answer.
Proof that this is minimal:
Imagine it can be done with just 2 polyominoes. Then at least one of them must be straight, to cover the digit 1. The remainder of the digit 8 must be covered by a single M-shaped polyomino, which is not going to be useful in covering the digit 0. Contradiction.
answered Mar 7 '20 at 10:52
-
-
1$\begingroup$ @Jens It was easier than I expected to prove that these numbers are minimal. Nice puzzle! Makes polyomino things a bit less daunting for me :-) $\endgroup$ – Rand al'Thor Mar 7 '20 at 17:24
$\begingroup$
$\endgroup$
2
A quick attempt using
5
polyominoes:
Here is an attempt for the bonus question using
3
polyomnioes
(yellow is placed first, then green, then red)
-
$\begingroup$ +1 You were first, but Rand also provided arguments for the answers, so on balance I gave him the checkmark. $\endgroup$ – Jens Mar 7 '20 at 17:23
-
2$\begingroup$ No problem, his answer is indeed a bit better. I didn't have time to prove it formally. $\endgroup$ – Glorfindel Mar 7 '20 at 17:24
$\begingroup$
$\endgroup$
Non-overlapping:
5
1, 22, 333, 444, 55 4 5 355 3 444 444 4 3 3 5 3 4 4 4 3 3 4 3 333 333 443 2 4 2 5 5 2 244 2 551 155 2
444 444 444 333 444 4 4 4 5 1 4 1 333 333 3 554 333 5 5 2 3 2 4 2 155 552 3 244 2
