Alice and Bob play the following game on a $9\times11$ chessboard.

  • First Alice divides the chessboard into $33$ smaller rectangles of dimensions $1\times3$ and $3\times1$.
  • Then Bob labels each of the $99$ squares with one of the integers $0,1,2,3,4,5$, such that in each of Alice's smaller rectangles the sum of the labels equals $5$.
  • Bob wins the game, if in each of the nine rows the sum of the labels is a prime number. Otherwise Alice wins.

Question: Which player is going to win this game? (As usual, we assume that Alice and Bob both use optimal strategies.)

up vote 9 down vote accepted

Bob can always win by labeling the squares using the following scheme:

$31131131131 \quad 19$
$13113113113 \quad 19$
$11311311311 \quad 17$
$31131131131 \quad 19$
$13113113113 \quad 19$
$11311311311 \quad 17$
$31131131131 \quad 19$
$13113113113 \quad 19$
$11311311311 \quad 17$

The sum of each row is a prime number. Any horizontal or vertical combination of $3$ squares has the sum $5$.

Bob will win.

This is because it is impossible for Alice to force him to make a non-prime sum in a row.

I will go a step further and say it is always possible to fill the rows so that 6 rows have the sum 19 and 3 rows have the sum 17.

To prove this i will solve it with an easy board and show how every other combination of rectangles can be made from this board with simple transformations and still show the same solution.


Our easy board will have the first two colums filled with 3 vertical rectangles per column.

The rest of the board will be filled with horizontal rectangles for an additional 3 horizontal rectangles per row:

┌─┬─┬─────┬─────┬─────┐
│ │ │     │     │     │
│ │ ├─────┼─────┼─────┤
│ │ │     │     │     │
│ │ ├─────┼─────┼─────┤
│ │ │     │     │     │
├─┼─┼─────┼─────┼─────┤
│ │ │     │     │     │
│ │ ├─────┼─────┼─────┤
│ │ │     │     │     │
│ │ ├─────┼─────┼─────┤
│ │ │     │     │     │
├─┼─┼─────┼─────┼─────┤
│ │ │     │     │     │
│ │ ├─────┼─────┼─────┤
│ │ │     │     │     │
│ │ ├─────┼─────┼─────┤
│ │ │     │     │     │
└─┴─┴─────┴─────┴─────┘

Now each row will have a sum of 15 (for the three horizontal boxes) plus a small amount from the vertical boxes.

I will fill it in as easy as possible:

┌─┬─┬─────┬─────┬─────┐
│1│1│5 0 0│5 0 0│5 0 0│  17
│ │ ├─────┼─────┼─────┤
│2│2│0 5 0│0 5 0│0 5 0│  19
│ │ ├─────┼─────┼─────┤
│2│2│0 0 5│0 0 5│0 0 5│  19
├─┼─┼─────┼─────┼─────┤
│1│1│5 0 0│5 0 0│5 0 0│  17
│ │ ├─────┼─────┼─────┤
│2│2│0 5 0│0 5 0│0 5 0│  19
│ │ ├─────┼─────┼─────┤
│2│2│0 0 5│0 0 5│0 0 5│  19
├─┼─┼─────┼─────┼─────┤
│1│1│5 0 0│5 0 0│5 0 0│  17
│ │ ├─────┼─────┼─────┤
│2│2│0 5 0│0 5 0│0 5 0│  19
│ │ ├─────┼─────┼─────┤
│2│2│0 0 5│0 0 5│0 0 5│  19
└─┴─┴─────┴─────┴─────┘

Now we can already guess where this is going.

3 Transformations are possible/needed:

  1. substituting 3 horizontal rectangles by 3 vertical rectangles.

This is done easily as we already have our 5s filled in perfectly

┌─┬─┬─────┬─────┬─────┐
│1│1│5 0 0│5 0 0│5 0 0│
│ │ ├─────┼─────┼─────┤
│2│2│0 5 0│0 5 0│0 5 0│
│ │ ├─────┼─────┼─────┤
│2│2│0 0 5│0 0 5│0 0 5│
├─┼─┼─┬─┬─┼─────┼─────┤
│1│1│5│0│0│5 0 0│5 0 0│
│ │ │ │ │ ├─────┼─────┤
│2│2│0│5│0│0 5 0│0 5 0│
│ │ │ │ │ ├─────┼─────┤
│2│2│0│0│5│0 0 5│0 0 5│
├─┼─┼─┴─┴─┼─────┼─────┤
│1│1│5 0 0│5 0 0│5 0 0│
│ │ ├─────┼─────┼─────┤
│2│2│0 5 0│0 5 0│0 5 0│
│ │ ├─────┼─────┼─────┤
│2│2│0 0 5│0 0 5│0 0 5│
└─┴─┴─────┴─────┴─────┘

This can actually be done at any position we wish as long as we have 3 rectangles in a square formation.

  1. moving vertically

When we have 3 vertical rectangles in a square formation and a horizontal rectangle directly above or below we can switch them.

┌─┬─┬─────┬─────┬─────┐
│1│1│5 0 0│5 0 0│5 0 0│
│ │ ├─────┼─────┼─────┤
│2│2│0 5 0│0 5 0│0 5 0│
│ │ ├─┬─┬─┼─────┼─────┤
│2│2│5│0│0│0 0 5│0 0 5│
├─┼─┤ │ │ ├─────┼─────┤
│1│1│0│5│0│5 0 0│5 0 0│
│ │ │ │ │ ├─────┼─────┤
│2│2│0│0│5│0 5 0│0 5 0│
│ │ ├─┴─┴─┼─────┼─────┤
│2│2│0 0 5│0 0 5│0 0 5│
├─┼─┼─────┼─────┼─────┤
│1│1│5 0 0│5 0 0│5 0 0│
│ │ ├─────┼─────┼─────┤
│2│2│0 5 0│0 5 0│0 5 0│
│ │ ├─────┼─────┼─────┤
│2│2│0 0 5│0 0 5│0 0 5│
└─┴─┴─────┴─────┴─────┘

We dont need to care for the first 2 columns for now as whenever this movement is possible there will always be at least 3 vertical 5-rectangles in the same 3 rows.

  1. horizontal movement

When we have 3 horizontal rectangles in a square formation and a vertical rectangle directly left or right we can switch them.

┌─┬─┬─────┬─────┬─────┐
│1│1│5 0 0│5 0 0│5 0 0│
│ │ ├─────┼─────┼─────┤
│2│2│0 5 0│0 5 0│0 5 0│
│ │ ├─┬─┬─┼─────┼─────┤
│2│2│5│0│0│0 0 5│0 0 5│
├─┼─┤ │ │ ├─────┼─────┤
│1│1│0│5│0│5 0 0│5 0 0│
│ │ │ │ │ ├─────┼─────┤
│2│2│0│0│5│0 5 0│0 5 0│
│ │ ├─┴─┴─┼─────┼─────┤
│2│2│0 0 5│0 0 5│0 0 5│
├─┼─┴───┬─┼─────┼─────┤
│1│5 0 0│1│5 0 0│5 0 0│
│ ├─────┤ ├─────┼─────┤
│2│0 5 0│2│0 5 0│0 5 0│
│ ├─────┤ ├─────┼─────┤
│2│0 0 5│2│0 0 5│0 0 5│
└─┴─────┴─┴─────┴─────┘

This can be done as often as needed without changing the sums in the rows.

By using these transformations as often as needed we can reach all possible combinations of rectangles.

  • 5
    You're probably right, but could you explain how or prove that all possible combinations can be reached with these 3 transformations? – Ivo Beckers Nov 17 '15 at 10:53
  • @Ivo Beckers I think it can be seen like that and I actually don't know how i could prove it to you rather than solving each and every possible combination wich my 3 transformations. As a compromise i am willing to solve a single combination that you think might be impossible. For this i would suggest making a community wiki answer and then commenting again so i get a message and can do a step by step solution. – The Dark Truth Nov 17 '15 at 10:59
  • @ivobeckers Every row has to have 2+3*n vertical rectangles, Every horizontal rectangle you remove forces you to remove 3, or the gap can't be filled in. Now you might slide things around, but in the end, you will always have to make a 3x3 'hole' to begin putting in vertical rectangles. And you can always fill in these vertical rectangles so they have a 5 in each column. Since we're only concerned about the rows, sliding around horizontally has no effect on the result, Therefore all possible combinations are basically one and the same. – DrunkWolf Nov 17 '15 at 13:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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