Timeline for What is the smallest size of a shape in which all fixed $n$-polyominos can fit?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 3, 2022 at 20:23 | comment | added | a3nm | I am very late in reacting to this, but thanks for your answer. I did not redo the calculations but I think I see the overall idea. It is a very nice argument, and very striking that this can be shown to be $\Theta(n^2)$. Thanks a lot for your work! | |
| Nov 3, 2022 at 20:21 | vote | accept | a3nm | ||
| May 24, 2022 at 13:17 | comment | added | Ville Salo | Oh, duh. I guess in terms of how I imagined this, the short explanation is you do not cheat the finitely many subrectangles separately, you cheat their union. | |
| May 24, 2022 at 11:11 | comment | added | fedja | @VilleSalo As to the second question, $P_K$ only has the property that every shift $E'$ of $E$ cannot fill at least one of the squares $Q_K$ but which one depends on the shift. Or, perhaps, I misunderstand what you are asking there? | |
| May 24, 2022 at 11:06 | comment | added | fedja | @VilleSalo Suppose that we have any set $E_0$ on the plane whose shifts can cover any $Cn$-mino on the plane. Then $E$ that is obtained by wrapping $E_0$ to the $n\times n$ torus should have the property that its shifts on the torus cover any $Cn$-mino contained in an $n\times n$ square placed on the torus. But we have proved that it is impossible if $E$ has fewer than $n^2/2$ cells and, obviously, $|E_0|\ge |E|$. | |
| May 24, 2022 at 7:30 | comment | added | Ville Salo | Could you spell out why it suffices to find a connected set of size $Cn$ which is not contained in any shift of $E$? I figured this is supposed to prove that the optimal shape inside $Cn \times Cn$ has to have large density somewhere. I see that you are individually cheating the boundedly many subrectangles, but what if the $P$ that cheats one subrectangle is covered by another? | |
| May 24, 2022 at 4:31 | history | answered | fedja | CC BY-SA 4.0 |