Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A cross consists of six unit squares and looks as follows:

         O
       OOOO
         O

(this may also be rotated by several right turns, or horizontally reflected or vertically reflected).

What is the maximum number of crosses than can be fit on a $ 10\times 11 $ chessboard without overlapping? (Every cross must cover exactly six of the little squares on the chessboard.)

share|improve this question
2  
can't do corners, leaves max 106 covered, can't do partial, so 102 max (17 crosses). Chunking board into 3x4 sections easily gives 8 crosses, so 8 <= max number of crosses <= 17 – Slepz Feb 24 at 18:14
    
@Slepz I've narrowed it down a little more in my answer, but not, like, mathematically – question_asker Feb 24 at 18:59
    
@question_asker you're right the hard cap should be 90 / 6 = 15 if you account for how floor((sideLength - 1) / 2) at most squares on an edge can be used. New inequality is (14 <= max number of crosses <= 15). I wonder if we can improve on that with a proof. – Slepz Feb 24 at 20:09
up vote 7 down vote accepted

To prove that Jeff B's answer is maximal:

As suggested by Slepz in comments, it is clear that no corner cell may be covered, and no two adjacent edge cells may be covered. It follows that at most 5 of the 9 non-corner cells on each long edge may be covered, and at most 4 of the 8 non-corner cells on each short edge may be covered. This gives an upper bound of 5+5+4+4=18 for the number of covered edge cells.

Lemma: It is not possible to achieve 18 covered edge cells

Proof: Following the same logic as the previous paragraph, 5+5+4+4 would be the only possible way to achieve 18. By inspection we can see that the only way to cover 5 squares on the long edge is the green-yellow pattern in Jeff B's answer (with two possible orientations).

However, note that each yellow cross actually eliminates 2 non-corner cells on each short edge. Considering both yellow crosses on one short edge, this means only the two central cells of the short edge remain. Since they are adjacent only at most one can be covered.

So we have shown that if 5 cells are covered on both long edges, then at most 3 cells may be covered on either short edge. This proves the lemma and reduces our upper bound for edge square coverage to 16.

Finally, since there are 8 x 9 = 72 non-edge squares, 72 + 16 = 88 is now the upper bound on coverage for all squares; therefore placing 15 crosses (which would cover 90 squares) is not possible.

share|improve this answer
    
lol I just got totally cut out of this, didn't i – question_asker Feb 24 at 21:08
    
@question_asker jeff's layout and colour scheme made my answer a bit shorter than if I'd referenced yours.. nothing personal :) – M.M Feb 24 at 21:38
2  
@question_asker has a better explanation because he uses technical terms like jutty out parts and bluish. I can't understand this lemma malarkey but bluish I can get behind. – corsiKa Feb 25 at 18:26
    
@corsiKa The best part about "jutty-out parts" is that I went to the trouble to make up that term and then never used it again. Bluish is a word though, and has been for centuries. – question_asker Feb 25 at 18:29

Highly non-mathematical answer ahead

I managed to get

$14$



enter image description here

Seeing what seemed to be wasted space, I tried rotating a few (e.g., the leftmost bluish cross), but couldn't get any more in.

Not a proof, but some reasoning:

Corners are out. Since the shape has... let's call them "jutty-out parts"... none can be packed flat against a side, so there will necessarily be unused squares on every single side. Packing them as closely as possible (as I have at the bottom), each long side will have the previously-mentioned $2$ unused corner squares as well as $4$ unused squares which alternate with the end bits of the crosses. Each short side will have the previously-mentioned $2$ unused corner squares and at least $4$ other unused squares. This alone (unusable side squares) gives us a maximum $90$ squares that could contain parts of crosses. If we could rearrange that remaining space, and if, instead of crosses, we were trying to pack $3\times2$ rectangles in that remaining space, then we could fit exactly $15$ of them in there.

This, in combination with the reasoning given in @M.M's post, shows that $14$ is the largest number of crosses that can be contained entirely within a $10\times11$ grid.

extremely arnold schwarzenegger voice remember when I said I would never do another math puzzle again. i lied.

share|improve this answer

Manually:

14
My Solution
I cannot manage a better arrangement.

share|improve this answer

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.