What are the small values of S_{3}(n)? Is there a formula for S_{3}(n)? How about S_{k}(n)? What are the small values of M_{k}? Is there a formula for M_{k}? What about placing squares in a rectangle? How do these values change if we allow the squares to be rotated or placed off the square grid?
David Bevan noticed S_{k}(n) ≤ n/k/4^{2}, since a square can't see k other squares if it is perimeter is less than k.
David Bevan also showed S_{5}(n) ≥ (n^{2}–12n+27)/4 for n≥18, S_{6}(n) ≥ (n^{2}–30n+181)/4 for n≥29, and S_{8}(n) ≥ (n^{2}–103n+2687)/5 for n=40r+6 and r≥2.
David Bevan was interested in the limiting density of solutions L(k). It is fairly easy to see that L(0)=0, L(1)=0, L(2)=0, L(3)=0, L(4)=1, L(5)=1/4, and L(6)=1/4. He thinks L(7)=2/9, L(8)=1/5, L(9)=2/25, L(10)=1/14, L(11)=1/18, and L(12)=1/20, since these are the best on an infinite grid. Are these correct? Is there any solution at all for n≥9 ?
David Bevan also made the following graph-theoretic observation: if k is odd, then S_{k}(n) is even.
Here are the values of S_{k}(n) for k≤2:
S_{0}(n) = n | M_{0} = 1 | |||||
S_{1}(n) = 4n/3 | M_{1} = 2 | |||||
S_{2}(n) = 2n | M_{2} = 2 |
Here are the best known values of S_{k}(n) for other small k:
S_{3}(n) ≥ 4n-14 | S_{3}(5)=6 | S_{3}(6)≥10 | S_{3}(7)≥14 | S_{3}(8)≥18 | M_{3} = 5 |
S_{4}(2n) = 4n^{2}-12n+4 | S_{4}(8)=20 | S_{4}(10)=44 | S_{4}(12)=76 | M_{4} = 8 |
S_{5}(13)≥6 | S_{5}(16)≥8 |
S_{5}(19)≥54 (David Bevan) | S_{5}(23)≥88 (David Bevan) | M_{5} ≤ 13 |
S_{6}(20)≥8 | S_{6}(30)≥82 (David Bevan) | M_{6} ≤ 20 |
S_{7}(31)≥8 (Trevor Green) | M_{7} ≤ 31 |
S_{8}(86)≥245 (David Bevan) | M_{8} ≤ 86 |
S^{*}_{3}(2+ε)=4 (Trevor Green) | M^{*}_{3} = 2 + ε |
S^{*}_{4}(3+ε)=9 (David Bevan) | S^{*}_{4}(4+ε)=16 (David Bevan) | S^{*}_{4}(6+ε)=36 (David Bevan) | M^{*}_{4} = 3 + ε |
S^{*}_{5}(4+ε)=16 (David Bevan) | M^{*}_{5} ≤ 4 + ε |
S^{*}_{6}(4+ε)=16 (David Bevan) | M^{*}_{6} ≤ 4 + ε |
If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 9/21/07.