Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
This needs thought to carefully specify the problem. How big are the balls? Do you mean the balls reflect from the border (as you say they can move in any direction) or after one reflection they are moving orthogonally (as you say they bounce from the border at 90 degrees)? Presumably the duration is "infinite", but it would be good to say that. –  Ross Millikan Jun 16 '11 at 12:30
    
In addition to Ross's questions: are all ball speeds constant and identical? Are they supposed to be reflecting from the border in the way an unspun snooker/pool ball would do? That's only a 90 degree angle if the angle of incidence is 45 degrees: so is that angle of 45 degrees a constraint? –  EnergyNumbers Jun 16 '11 at 12:57
    
I assume that one ball fills one square on the chess board and that two balls touch iff they enter the same square at the same timestep. But what are the rules of reflection? And what are the rules of motion, can balls move like bishops along diagonals or only like rocks? –  Tim van Beek Jun 16 '11 at 12:57
    
Oh sorry, yes, speed of balls are constant, and time is infinite. @Tim, yes they can move along diagonals. If balls hits the border the move direction is changed by 90*, obviously if ball hits the corner the move direction is changed by 180*. Sorry for lack of informations. –  Chris Jun 16 '11 at 13:26
    
State more clearly in which direction can the balls move? Horizontally, vertically and along a diagonal(like the bishops do in chess)? If a ball touches the border, I understand that it reflects like in all reflection laws, that is if a ball moves horizontally and then hits the border, it continues to move horizontally. Please state more clearly what you want, so that you can get an answer. –  Beni Bogosel Jun 16 '11 at 15:05

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
1  
If $M = N$ then there's a lower bound of $2M - 2$ by having a single loop going diagonally, and in general you can set up a loop of length $2M - 2$ starting anywhere other than on a diagonal. For $M = 8$ you can set up two such loops, each alterating ball, non-ball; such that at $t=0$ one has a ball one cell to the right of the top-left corner, and the other one cell to the right of the bottom-left corner. Then parity arguments show that you can get a horizontal-moving ball in the top and bottom rows, for a total of 16. This is, of course, only a lower bound. –  Peter Taylor Jun 16 '11 at 15:23
    
@Peter That sounds right to me... it would look like a diamond inside of a square if I'm imagining it correctly, right? but I'm not sure it would be $2M$ balls if the paths of the balls do make a diamond shaped loop on the inside, since the board is discrete in shape. Another interesting thought is that if we can find the longest unique single loop on the board with these rules, then we can just place balls for each square the paths takes up. –  Nicolas Villanueva Jun 16 '11 at 15:29
    
it's $2M-2$. The extra 2 to get up to 16 are horizontal balls which manage to use parity to dodge past the corners of the diamonds. It's probably possible to squeeze in two vertical ones too for 18, now that I think about it. –  Peter Taylor Jun 16 '11 at 15:32
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)$ –  Peter Taylor Jun 16 '11 at 16:55

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.

share|improve this answer
    
in the discrete case allowing diagonal movement lets you fit more balls in. For 8x8 with horizontal and vertical movement only there's an easy upper bound of 16. Allowing diagonal movement there's a lower bound of 28 - see comments on Nicolas' reply. –  Peter Taylor Jun 16 '11 at 16:57
    
I'm no seasoned expert when it comes to solving problems like these, but I would've thought the discrete case might be harder than the continuous one... –  Josh Chen Jun 17 '11 at 10:34
    
In any case I do rather get the feeling that the OP's intention was the discrete case. –  Josh Chen Jun 17 '11 at 10:34
    
what you describe is precisely what I was describing as a 28-ball solution. –  Peter Taylor Jun 17 '11 at 11:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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