Here's an interesting and fairly simple problem I encountered a couple of weeks ago.

There is a grid with 11 rows and 11 columns with a ball in every cell. Move every ball to an adjacent cell (up, down, left or right - diagonals are not allowed). Show that no matter how you move the balls you will always end up with at least one cell with more than one balls in it.

  • 2
    Hello, welcome to Math Stack Exchange! What do you want that we do? As you say that it is fairly simple, I assume you have solved it yourself, but then is our job kind of done... – wythagoras May 11 '15 at 17:11

Color the grid like a chessboard with alternating white and black squares. Let white be the color of the corners, so there are $61$ white squares and $60$ black squares. Notice that applying the move means balls that were on white squares are now on black squares, so since there were $61$ balls originally on white squares, but only $60$ black squares, by the pigeonhole principle after the move some (black) square must have more than $1$ ball.

Notice that this generalizes to any rectangular grid with an odd number of squares.

Colour the cells in checkerboard fashion. The total number of cells is odd, so there is one more of one colour (say red) than the other (black). All the balls from red cells go to black cells, so ...

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.