7
$\begingroup$

Alice is tiling a very large area using square tiles. She can tile at most ten tiles each time before getting some rest. When she rests, Bob the trouble maker will sneak in to remove one connected block of tiles. What is the maximum percentage of area Alice can tile eventually?

Example: the 7 green tiles are one connected block of tiles, and there're 3 connected block of red tiles.

enter image description here

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ It seems 50% + 9 squares. $\endgroup$
    – Moti
    Commented Oct 20, 2023 at 5:31

4 Answers 4

Reset to default
6
$\begingroup$

This is similar to what daw tries to do (as I understand it) but I hope I can explain the idea better and produce a better coverage at the same time.

Alice will use the following basic shape

 .#..
 ###.
 .###
 ..#.

and arrange lots of pieces like that in a pattern so that the don't touch each other. She doesn't have to lie a complete basic shape in one move, she just fills in spots that ought to be tiled in the large pattern.

 .#.###.
 ###.#.#
 .###.##
 #.#.#.#
 ##.###.

The empty spots form infinite lines along some diagonals and in between you can always fit exactly one piece.

A little bit of counting now shows that

We need 4 empty fields for each 8 filled fields, giving us a coverage of 8/12=2/3

of the total area. In each turn Alice adds 10 new pieces and Bob can remove at most

8

So in the long run Alice can cover arbitrarily large parts of the plane with this pattern.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nice, this beats the 9/14 density I got using this 9-cell pattern. $\endgroup$
    – xnor
    Commented Oct 20, 2023 at 7:20
  • $\begingroup$ If she puts them down adjacent to one another (as in your first picture), Bob will pick them up, eight at a time. I think in order to demonstrate that she can get 2/3 coverage, you need to provide an order in which she puts them down that Bob can't pick them up as fast as she does so. $\endgroup$
    – msh210
    Commented Oct 20, 2023 at 8:08
  • 1
    $\begingroup$ @msh210 She puts donw 10 per turn and Bob picks up at most 8 (8 if there is a complete basic shape somewhere, less otherwise). So there will be more tiles filled after every turn. That doesn't depend on where she puts them, eventually a bigger and bigger part of the plane will fill up with her pattern. $\endgroup$
    – quarague
    Commented Oct 20, 2023 at 8:18
  • 4
    $\begingroup$ Simply put, Alice can always replace all the squares Bob took and add (at least) two more to her pattern. $\endgroup$
    – Jaap Scherphuis
    Commented Oct 20, 2023 at 8:57
  • $\begingroup$ Oh! I was picturing an infinite plane and figuring how much of her convex hull she can fill. But that wasn't the question: we're dealing with a finite plane. You're right then. $\endgroup$
    – msh210
    Commented Oct 20, 2023 at 10:21
5
$\begingroup$

Best 9 tile pattern I could find

Fills 18/27, equal to the simpler 8 tile pattern already posted by quarague
enter image description here

Improve this answer
$\endgroup$
3
$\begingroup$

What if Alice tiles the plane with a periodic pattern of this type 

 ###.
 ###.
 ###.
 ...#

As Bob can only remove 9 tiles at a time, Alice can place arbitrarily many tiles, achieving a ratio of 10/16.

The target pattern looks like this: 

 ###.###.###.
 ###.###.###.
 ###.###.###.
 ...#...#...#
 ###.###.###.
 ###.###.###.
 ###.###.###.
 ...#...#...#
 ###.###.###.
 ###.###.###.
 ###.###.###.
 ...#...#...#

Improve this answer
$\endgroup$
4
  • $\begingroup$ Bob can remove one 3x3 block per move. After Bob's move, Alice has placed one tile more than after the last move of Bob. So she eventually fills the plane. $\endgroup$
    – daw
    Commented Oct 20, 2023 at 5:38
  • 2
    $\begingroup$ Bob can remove at least one 3x3 block per move. To prevent that from growing to a larger number Alice must never place new tiles adjacent to existing tiles. So she can place an infinite number, but definitely not at arbitrarily high density, ie she can't fill the plane with this strategy. $\endgroup$
    – theonetruepath
    Commented Oct 20, 2023 at 6:05
  • 2
    $\begingroup$ Yes, your method is fine and 10/16 is achievable. But maybe you should fill in the gap in your final sentence, i.e. how 10/16 is arrived at, to enable others to better understand you. $\endgroup$
    – Eric
    Commented Oct 20, 2023 at 6:41
  • $\begingroup$ ok, edited, hope this explains the idea better. Anyway, the other answer creates a better pattern. $\endgroup$
    – daw
    Commented Oct 20, 2023 at 7:33
2
$\begingroup$

The best I did was the same percentage as the previous answers:

2/3

Using the following pattern:

pattern

I've spent around 4 hours trying other patterns and now I'm pretty sure it's not possible to do better... but at the same time, the 9th tile is not used, so I wonder if this percentage can be mathematically proven (without a brute-force search).

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.