Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Imagine I have two bags of square and planar unit square tiles, with Penrose-like "nodules" on their edges s.t. two tiles can only be placed together if their edges are flush (i.e. if the two vertices defining the adjacent edges along the tile's contours are also adjacent). Said another way, tiling the plane with these unit tile constructs should create a series of vertices and edges that can be overlayed on a $Z^2$ integer lattice. Here, we have $k_r$ "red" tiles in the first bag, and $k_b$ "blue" tiles in the second bag.

You and I now play a game:

You create two "red" and "blue" connected components with the $k_r$ red tiles and $k_b$ blue tiles, respectively. You then hand these connected components to me. I am allowed to rotate, translate, or reflect the assemblies as I please, with the objective of maximizing the number of red tiles adjacent to blue tiles on a plane. However, importantly, I may not ever overlap any red or blue tiles. Your objective is to frustrate me to the greatest extent possible - to minimize the total number of edges shared between red and blue tiles.

How well can you possible do as a function of $k_r$ and $k_b$? When is it possible to insure that only one or two red/blue edges are possible? What is your optimal strategy? Perhaps to pack a sphere or other strictly convex object?

Additional Note: It's not at all clear to me what conditions guarantee only being able to ever have a single red/blue edge between two manipulable, but non-overlapping, red and blue connected components (besides the trivial case where $k_r$ and $k_b$ equal one). I'd be very interested to know what conditions insure or prevent this?

share|improve this question

1 Answer 1

up vote 0 down vote accepted

If I understand correctly then I think that one can always keep it to two shared edges. There are usually many ways to do this. The challenge is to find a very briefly describable scheme. Assume $r$ red tiles and $b$ blue tiles with $ 2 \le r \le b.$ Here is a scheme where the blue tiles are used to make a $1 \times b$ rectangle. It should be clear how to continue. Actually it should also be ok if $b \lt r$ too: alt text

For a more compact scheme with $r,b$ not too small, one could use a rectangle and a $45^{\circ}$ rotated square. I've indicated some possible blank squares inside since that was not ruled out. I'm sure there are other ways to deal with the need to get the exact count to work out. textareatextarea

If you think about it for a while I think you will be convinced that when $r,b \gt 1$ we can always have at least two edges of contact. This is the kind of thing that is easy to see but more involved than one would expect to give a complete proof of. I think that it should be possible to argue that we can start the two figures with a vertex of contact between the bottom left vertex of the leftmost square of the bottom of the red region and the top right vertex of the rightmost square of the top of the blue region. Now slide the red region down one or two spaces.

Here is the start of a more careful sketch that gets part of the way (and will be three times as long as the rest of the solution): There is a smallest bounding rectangle for each shape (with integer length horizontal and vertical sides).

  1. If both shapes have two consecutive edges touching a side of their bounding rectangle, then we can put those touching and we are done.

  2. So now we can assume that the blue region does not have two consecutive edges anyway on the bounding rectangle. This also means that all four corner squares of the bounding rectangle are unoccupied (since the blue region is connected and a mere corner to corner contact does not count as connected, I assume.)

  3. Suppose first that the red region does have a corner of the bounding rectangle filled, say the lower left corner and that the square vertically above it is also occupied (this is no restriction, flip if needed). Temporarily position that corner so that it is touching the rightmost occupied vertex of the top of the blue region. That vertex is the top left corner of a blue square which has a blue square below it but not on either side of it. There is no obstacle to sliding the entire red region down by one creating at least one vertical edge of contact. At this stage EITHER there is also a horizontal edge of contact (and we are done) OR there is no obstacle to sliding the red figure down by one more no creating two vertical edges of contact (and we are done).

  4. Our final case is that both the red and blue regions have all four corners of the bounding rectangle unoccupied and every colored square touching the bottom of the bounding rectangle next to an empty square on the left and right but with a colored square directly above it (with the appropriate changes for top, left, and right sides). ..

I am starting to see more further sub cases than I care to consider (and there may be a more elegant line of reasoning) but you get the idea. SO I think the result is true but do not claim to have done more than point at a line of argument.

share|improve this answer
    
@Aaron Meyerowitz On your suggestion, I am now calling the tiles "unit square tiles" instead of "Penrose tiles". However, it's not clear to me that we want to make two rectangles, since the adversary can always juxtapose the two longest blue and red rectangle sides? Also, and this may be a stupid question because it is intuitively obvious, what is a "soundbite" for why we need at least two touching edges instead of a single edge when $k_r>1$ and $k_b>1$? –  B.H. Dec 31 '12 at 21:38
    
@Aaron Meyerowitz Here, the adversary will try all possible sets of relative orientations for the red and blue tile assemblies to maximize the number of red/blue edges. Making rectangles of any aspect ratio for both of the assemblies should therefore quickly fail. –  B.H. Dec 31 '12 at 21:42
    
I only said a 1xn blue rectangle. The red could be a 2x2 square for 4, a cross for 5. The only non-rectangle for 3. I'll try to clarify. –  Aaron Meyerowitz Dec 31 '12 at 22:31
    
@Aaron Meyerowitz Sorry that I misunderstood you. To be a bit more clear myself, I'm mainly interested here in ruling out small numbers of shares edges (1,2,...) for threshold values of $k_r$ and $k_b$. –  B.H. Dec 31 '12 at 22:34
    
@Aaron Meyerowitz Very nice construction! How would we quickly prove though that one can never do better than two red/blue edges for $k_r>1$ and $k_b>1$? –  B.H. Jan 1 '13 at 1:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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