3
$\begingroup$

With given chessboard $N\times M$ we have to put moving balls (they are moving in any direction, they can move from one square to any adjacent square).

If any ball touches border, it bounces from the border with angle 90 degrees.

How many balls can we put on the chessboard such that two different balls won't touch each other?

  • 0
    @Josh, yes ;) t2011-06-17

2 Answers 2

2

This is an incomplete solution, but it's a starting point and I would be open to any further suggestions to get the final solution

I hope my assumptions are correct, but I'm going to assume that you get to choose the initial direction of the balls, and that the balls are the size of 1 square each.

Using this, notice that the obvious upper bound are $N\cdot M$ balls. Just as obvious, the lower bound are $max \left\{ N,M \right\}$ balls. We get the lower bound by taking the side of the board with the longest length, and filling every square of it with a ball. Now we choose the initial direction to go straight, so it only bounces off 2 walls forever, going back and forth.

It's also important to note that with this setup, we can NEVER have 2 balls in the same column/row, since they are only going straight and their paths would eventually intersect. So in that sense, we have a potentially better upper bound of $N + M$ balls.

Now, WLOG, suppose that the bottom half of the board is the longest(w/ length $N$), and thus we use that bottom side to have $N$ balls going straight up and down. This is where I get stuck, is there a way for you to have a ball travel horizontally on the board while not ever hitting one of the vertically traveling balls? My initial thought is yes, if we have the horizontal balls move like a sine wave function, and just have the horizontal ball go through the flow of the balls, but I still think they would eventually hit... any suggestions guys/gals? O_o

  • 2
    In fact for a square board you can set up one loop of length $2M-2$ on white squares and another on black squares, for a lower bound of $4(M-1)$2011-06-16
0

Incomplete answer; too long for a comment;

The speed and movemend can be considered in two ways: in one second, the ball "teleports" to a neighbor square (in one of the three directions), or the ball is considered to move like in the real life, continuously, with constant speed. Both problems are interesting, and maybe the first one is easy

Suppose the balls move continuously

My first thought is that if there is a ball moving horizontally and one diagonally, then they must meet. First, we can find the "times" the diagonal ball is in the strip containing the horizontal ball. Since these moments of time would be some irrational multiple of the period of the horizontal ball (the ratio is a multiple of $\sqrt{2}$), by a density argument, the balls must meet.

As in the previous answer, if all the balls have horizontal or vertical direction, the situation is easy. Suppose now that all the balls move diagonally, and each one moves in a rectangular strip with cut corners if the dimensions are equal, but when the dimensions are not equal, the trajectory can cover a big portion of the board. Each two such regions intersect, as can easily be seen, visualising the problem. The problem is the following: can we position the balls such that even if the trajectories meet, they are never simultaneously in the intersection? Even in a $8\times 8$ chessboard this problem seems hard, although the trajectories have the same length (when not moving on the great diagonal.

I will not continue with this case, since maybe this was not intended by the OP.

In the case where balls move "discretely" from a square to another, again, I feel that if the balls move diagonally, fewer balls can be positioned on the board.

[edit:] Ok, here's what came to my mind. I'll take for example the $8\times 8$ board. And take a rectangular diagonal loop and fill it with $14$ balls all moving in a "snake" style. We can make another loop on the other color and get another $14$ balls. I think this is an example $28$ balls. Don't know if the previous comments refer to this kind of structure, at least I didn't understand that.

  • 0
    what you describe is precisely what I was describing as a 28-ball solution.2011-06-17