6
$\begingroup$

You are in a casino and a weird game is happening where there is a grid-board $11$x$11$ and people are trying to put some chips on them. After hearing the rules you want to play it too, the rule is actually so simple:

  • You are supposed to put as many chips on the board as possible.
  • No diagonal on the board can have more than $4$ chips.
  • At most one chip for each grid.

What is the maximum number of chips that you can put on the board with the rules above?

If you can find the maximum number of chips that you can put on the board, you will also win all chips you put on!

$\endgroup$
2
  • $\begingroup$ Define diagonal? Does that include all diagonals, anti-diagonal, $\endgroup$
    – qwr
    May 7, 2018 at 18:21
  • $\begingroup$ @qwr any diagonal $\endgroup$
    – Oray
    May 7, 2018 at 18:22

1 Answer 1

7
$\begingroup$

If

I am not allowed to put multiple chips on a single space

then I think I will get

11^2-7^2 = 72 chips

because

by filling the outer two lines on each side of the board with chips, I fill every diagonal with min(4, number of spaces on diagonal) chips. Considering just the diagonals running in one of the two possible directions (which exactly cover the board), we can't do better than 1+2+3+4+4+...+4+4+3+2+1 chips, where the total number of diagonals is 21, the number of 4s therefore 15, and the total number of chips therefore 6+60+6=72.

The following diagram may help if my description above isn't perfectly clear:

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

[EDITED to add:] Since I wrote the following, Oray has updated the question to clarify that the alternate interpretation used below is not what he intended. I'm leaving it in, though, just in case it's of any interest.

However,

perhaps we are allowed to put more than one chip in a single space.

In that case I believe the best that can be done is

to put four chips on all but one of these diagonals, and likewise on all but one of the perpendicular diagonals -- e.g., by putting 4 chips on each space along one edge, and 4 chips on each non-corner space along the opposite edge. This gives us 80 chips in total.

I think this is best possible because

of those 21 diagonals listed before, the first and last can have at most 4 chips between them (because each of them is a size-1 diagonal and they are both on a common perpendicular diagonal); the arrangement above achieves this, and puts the maximum of 4 chips on each of the other diagonals in that direction. (And these diagonals exactly cover the board.)

$\endgroup$
0

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.