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
31 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 3, 2022 at 20:21 | vote | accept | a3nm | ||
| May 24, 2022 at 4:31 | answer | added | fedja | timeline score: 8 | |
| May 6, 2022 at 13:56 | comment | added | a3nm | I see -- nice! :) | |
| May 6, 2022 at 12:23 | comment | added | RobPratt | I used an integer linear programming solver, with a binary decision variable for each polyomino-position pair and a binary decision variable for each cell. | |
| May 6, 2022 at 8:57 | comment | added | a3nm | @RobPratt. OK, thanks! out of curiosity, may I ask how did you find this lower bound and the 31 upper bound? | |
| May 5, 2022 at 16:57 | comment | added | RobPratt | I don't know, either. But $30$ does turn out to be a lower bound. | |
| May 5, 2022 at 16:16 | history | edited | a3nm | CC BY-SA 4.0 |
fix grammar error
|
| May 5, 2022 at 16:09 | comment | added | a3nm | @RobPratt: Interesting! I agree that according to my code this 31-cell shape can embed all 8-polyominos. And it is "minimal under inclusion", i.e., removing any of these cells breaks this property. I don't know if a 30-cell solution for N=8 is possible. | |
| Apr 26, 2022 at 22:45 | answer | added | Saúl RM | timeline score: 6 | |
| Apr 25, 2022 at 13:48 | comment | added | RobPratt | $S_8 \le 31$: \begin{matrix} .& .& .& \#& .& .& .& . \\ .& .& .& \#& \#& .& .& . \\ .& .& \#& \#& \#& \#& .& . \\ .& \#& \#& \#& \#& \#& \#& . \\ \#& \#& \#& \#& \#& \#& \#& \# \\ .& \#& .& \#& \#& \#& \#& . \\ .& .& \#& \#& \#& .& .& . \\ .& .& .& \#& \#& .& .& . \end{matrix} | |
| Apr 25, 2022 at 10:15 | comment | added | a3nm | @RobPratt: thanks a lot for catching this! indeed, I had messed up. I have edited the post accordingly. If your computation is able to get $S_8$ it would be interesting, to see if the matches with OEIS sequences are coincidental or not. | |
| Apr 25, 2022 at 10:13 | history | edited | a3nm | CC BY-SA 4.0 |
fixed errors, many thanks to @RobPratt
|
| Apr 24, 2022 at 18:27 | comment | added | RobPratt | I get $S_7 = 24$ (like yours but with only one hole). Your proposed solution cannot contain the 14th polyomino. | |
| Apr 24, 2022 at 18:04 | comment | added | RobPratt | Thanks for the data. Notice that your $n=5$ solution, which is optimal subject to fitting within an $n \times n$ square, actually uses only $13$ cells. | |
| Apr 24, 2022 at 14:46 | comment | added | a3nm | @PeterKagey: thanks for the pointer! the SAT-based approach in this great answer codegolf.stackexchange.com/a/167973 could probably be adapted for free polyominos to compute more terms in the series I ask about | |
| Apr 24, 2022 at 14:43 | comment | added | a3nm | @RobPratt: here zero.crans.org/… (I checked that the number of polyominos produced for each N matches oeis.org/A001168) | |
| Apr 24, 2022 at 2:11 | comment | added | Peter Kagey | I've asked about something similar about free polyominoes on Code Golf Stack Exchange and Math Stack Exchange. | |
| Apr 23, 2022 at 15:52 | answer | added | AnttiP | timeline score: 4 | |
| Apr 23, 2022 at 15:08 | comment | added | Saúl RM | @a3nm oh sorry, I had a mistake in my argument. As domotorp says, "straight polyominos" are not enough | |
| Apr 23, 2022 at 14:30 | comment | added | RobPratt | Can you please share the input data (an explicit list of the fixed $n$-polyominoes) for $n \le 8$? | |
| Apr 23, 2022 at 9:34 | history | edited | a3nm | CC BY-SA 4.0 |
acknowledge original question authors
|
| Apr 23, 2022 at 8:53 | comment | added | domotorp | @a3nm Take a nice set $S$ whose area is $<0.01n^2$ and contains a length $n$ segment in every direction. Such a set $S$ exists by the constructions given on Wikipeida for the Kakeya set. Now pixelize $S$ by checking which unit squares it intersects from the unit grid. The number of these squares is $0.01n^2 +O(n)$ as the perimeter of $S$ is nice. As $n\to \infty$, this gives an upper bound of $0.01n^2$, and we can pick $0.01$ as small as we want to. | |
| Apr 23, 2022 at 8:26 | comment | added | a3nm | @SaúlRodríguezMartín I'd be very interested by an $\Omega(n^2)$ bound. Some colleagues thought they could show $\Omega(n^{2-\epsilon})$ for all $\epsilon$ by a complicated argument, but it's not $\Omega(n^2)$ and the argument was probably more complicated than it should. | |
| Apr 23, 2022 at 8:25 | comment | added | a3nm | @domotorp, thanks, I was already aware of the related problems (Moser's worm problem and Kakeya sets), but I do not understand the argument (is your point that there is an $o(n^2)$ solution?). | |
| Apr 23, 2022 at 6:24 | comment | added | domotorp | The continuous analogoue of the original problem would be this unsolved question: en.wikipedia.org/wiki/Moser%27s_worm_problem (without the convexity assumption). A lot of results can be found in Chapter 11.4 of Research Problems in Discrete Geometry by Brass, Moser, Pach. | |
| Apr 23, 2022 at 6:10 | comment | added | domotorp | In fact, the constructions show that for this case $o(n^2)$ is the answer. Just take the overlapping shifts of a large number of slices of a triangle as given in the Perron tree, then take its digital cover. If $n$ is large enough compared to the number of slices, and the number of slices is large, then this gives $o(n^2)$. I didn't calculate the exact magnitude, and other constructions of Kakeya sets might work as well. I wonder if this construction also works for the original problem. | |
| Apr 23, 2022 at 5:13 | comment | added | domotorp | The case of the "straight polyominos" proposed by Saúl is the digital equivalent of the celebrated Kakeya problem: en.wikipedia.org/wiki/Kakeya_set | |
| Apr 23, 2022 at 1:56 | comment | added | Steven Stadnicki | You can at least get $S_n=\Omega(n\log n)$ by a simple argument based on the rectangles. | |
| Apr 22, 2022 at 22:22 | comment | added | Saúl RM | Seems like the "straight polyominos" (those obtained as a union of the squares touching a given segment, which need not be horizontal or vertical) should give the $\Omega(n^2)$ lower bound, I'll write something tomorrow if no one has answered that part of the question | |
| Apr 22, 2022 at 22:12 | history | edited | a3nm |
+tag
|
|
| Apr 22, 2022 at 21:57 | history | asked | a3nm | CC BY-SA 4.0 |