2
$\begingroup$

A certain chessboard is infinite in size. There is a frog sitting in the center of every square. After a certain time, all the frogs jump such that

  1. They may jump to any possible square in the infinite chessboard
  2. They may jump and land at the same square again

Prove that its possible for all the frogs to jump simultaneously such that there are exactly two frogs per square after the jump.


Let there be n frogs sitting on n squares where $n\rightarrow \infty$

Lets choose our king frog who's sitting at a particular square, now

CASE I: King frog wants to stay at his original square, then its probability is $\frac { 1 }{ n } $. Then we are left with n-1 frogs who have n squares left. I am stuck at this point, I know the probability of remaining frogs to choose king's square is $\frac { n-1 }{ n }$ but how to proceed after that?

CASE II: King frog doesn't want to stay at his original square, then he has $n-1$ ways to go, also the probability of remaining of the n-1 frogs to land at king's square is $\frac { n-1 }{ n } $. So we have

$$\lim _{ n\rightarrow \infty }{ \frac { n(n-1) }{ n } } $$

$\endgroup$
15
  • $\begingroup$ I'm fairly sure this basic problem has been raised before. What I don't understand is what your question is, and whether it might be different from those previously raised. It looks as though you should be looking for a systematic process rather than a random one. $\endgroup$ Commented Apr 14, 2014 at 14:18
  • $\begingroup$ Choose a definite orientation of the board so as to have all the frogs "facing" to the same direction (say, "the front"). Now, what about having each frog on a white square jumping onto its same square, whereas each frog on a black square jumping precisely to the black square in front of it? $\endgroup$
    – DonAntonio
    Commented Apr 14, 2014 at 14:23
  • 2
    $\begingroup$ I thought a chessboard has just two dimensions? What would be a chessboard that is infinite in dimensions? Or do you just mean infinite in size? Fun aside, in an infinite chess board the ranks wouldn't be numbered 1 to 8, but rank numbers would be all integers. If a frog is on rank 2k it jumps to rank k with the same file; if a frog is on rank 2k+1 it also jumps to rank k with the same file. Two frogs on every square. $\endgroup$
    – gnasher729
    Commented Apr 14, 2014 at 15:21
  • 2
    $\begingroup$ It seems to me that the introduction of probability makes this a more interesting problem than posters seem to think, if we interpret "it is possible" as "there is a positive probability". Of course we could have the situation where ranks $2k+1$ and $2k$ all jump to rank $k$, but the probability of this particular outcome happening by chance is 0. (However, I'm inclined to suspect that the probability of ending up with 2 frogs on every square is also 0.) $\endgroup$ Commented Apr 14, 2014 at 16:17
  • 1
    $\begingroup$ Actually, now that I read it again, if we want to intepret it probabilistically, we need to specify the probability distribution with which frogs choose a new square. There's no uniform distribution on an inifinite lattice. $\endgroup$ Commented Apr 14, 2014 at 16:19

3 Answers 3

6
+100
$\begingroup$

Suppose you describe the squares of the board $B$ using integer coordinates: $$ B = \{(x,y) \mid x,y \in \mathbb{N}\}. $$ Use the following map, which I will describe in steps: first map $$ (x,0),(x,1) \mapsto (x,0) \quad \forall x \geq 0; $$ this takes care of the first row, each square of which now has exactly $2$ frogs occupying it. Next map $$ (x,2),(x,3) \mapsto (x,1) \quad \forall x \geq 0; $$ this takes care of the second row, each square of which now has exactly $2$ frogs occupying it. In general, the map is $$ (x,2i),(x,2i+1) \mapsto (x,i) \quad \forall x \geq 0, i \geq 0. $$ I think you can see this will have exactly the property you want!

$\endgroup$
0
3
$\begingroup$

This problem has nothing to do with probability, but your idea of picking a king frog is useful. Starting with the king frog, enumerate both frogs and squares in a spiral (like the starting point for Ulam's spiral). Then simply have frogs 1 and 2 jump to square 1, frogs 3 and 4 jump to square 2, and so forth.

$\endgroup$
1
$\begingroup$

Think about doing it for one layer of the chess board. It may be helpful to split the layer into two parts. I.e consider the split line being the natural numbers. Tell 0 to jump and 1 to move 1 left. Tell 2 to move 1 left and 3 to move 2 left.... tell $2n$ to move n left and $2n+1 $to move $n+1$ left.

Find a similar algorithm for $\{-1,-2,-3,\ldots\}$. And then just order that this rule should be followed on all levels of the chess board.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .