7
$\begingroup$

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.)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
13
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you please tell us how you came up with this answer ? What was your intuition/thought process ? Thanks $\endgroup$
    – Hemant Agarwal
    Jul 21, 2022 at 20:36
  • $\begingroup$ @HemantAgarwal As far as I remember there wasn't really a big thought process. I wanted to generate a regular pattern which always generates a sum of 5 for three consecutive fields. This can be done in several ways (e.g. 500 or 410), but using 311 has the additional property of giving a prime sum for the rows. $\endgroup$
    – Sleafar
    Jul 23, 2022 at 3:56
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ You're probably right, but could you explain how or prove that all possible combinations can be reached with these 3 transformations? $\endgroup$
    – Ivo
    Nov 17, 2015 at 10:53
  • $\begingroup$ @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. $\endgroup$
    – The Dark Truth
    Nov 17, 2015 at 10:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – DrunkWolf
    Nov 17, 2015 at 13:15

Your Answer

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

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