0
$\begingroup$

assume we own a regular chess board (8 by 8), now we will randomly write in the slots of the board numbers from 1 to 64 (every number we will write exactly one time), show that the probability that {there are two adjacent squares (which share a rib - not diagonally) that the subtraction between the numbers is those squares is at least 5} = the probability of that equal 1 (or 100%).

means that need to show that there are at least one adjacent pair (row or column , not diagonally), so the subtraction of the numbers equal at least 5.

$\endgroup$
  • $\begingroup$ That is, there exist two adjacent squares such that the difference between the numbers on these squares is five? $\endgroup$ – астон вілла олоф мэллбэрг Oct 11 '17 at 10:33
  • $\begingroup$ Are diagonal squares adjacent? Or just squares in the same row or column? Edit: Well obviously we cannot include diagonals or the problem is trivial. $\endgroup$ – Tom Miller Oct 11 '17 at 10:34
  • $\begingroup$ i edited it , it does mean column or row and not diagonal $\endgroup$ – ned grekerzberg Oct 11 '17 at 10:42
1
$\begingroup$

First lets look on the place of the digit 1 and the place of the digit 64 on the board. we shell pick a monotonic walk (such a walk that if i went down once i cant go up anymore and otherwise, also if i went left once i cant go right anymore and conversed). now we will use the pigeonhole principle (for the general case),

Every edge will be a "hole" and every subtracting point (by absolute value) between two following squares will be a "pigeon". there for in the walk there is at least 64 - 1 = 63 pigeons and 7+7=14 holes for most (maximum length of a monotonic walk) and from the pigeonhole principle there i a hole with at least $\left \lceil \frac{63}{14} \right \rceil = 5 $ pigeons , means that there is two adjust squares that the subtraction between them is at least 5 !

$\endgroup$
1
$\begingroup$

I can do even better: There must be at least one place where the difference is at least $6$.

For contradiction, let's say we have distributed the numbers so that adjacent squares have a difference of at most $5$, and to help in visualising, take a piece that can move like a king, but not diagonally (a so-called wazir). Then the rules can be restated as "There is no place on the board where the wazir can move between two squares whose numbers differ by more than $5$."

That means that numbers that numbers with a big difference must be placed on squares that are many wazir moves apart. The biggest limitation on any pair of numbers is $13$ moves, which corresponds to starting in one corner and ending up one move away from the opposite corner (the biggest separation you can get between two squares is $14$ moves).

Look at all pairs of numbers that must be separated by at least $13$ wazir moves. Those are $$ 1-64\\ 2-64\\ 3-64\\ 1-63\\ 2-63\\ 1-62 $$ That means that on the three squares in one corner we must have $1, 2, 3$, and on the three squares in the opposite corner we must have $62, 63, 64$. Clearly, $1$ and $64$ must go in the actual corner squares, since each of them must be separated by $13$ moves to all the three numbers on the opposite side. However, we cannot place the rest of them in any satisfactory manner (no matter what, $2$ and $63$ will be separated by $12$ moves, for instance).

Thus we see that it is impossible to distribute the numbers in a satisfactory manner deliberately, which means that if you distribute them randomly, you can't possibly manage to do it either, so the probability of it happening is $0$.

$\endgroup$
0
$\begingroup$

I am going to prove the stronger:

Claim:

When you put different whole numbers on a $7 \times 7$ board there has to be a pair of adjacent squares with a difference of at least $5$.

Proof:

Proof by contradiction: Suppose there is no such adjacent pair of squares, i.e all adjacent squares have a difference of at most $4$.

Let $n$ be the number in the center square.

Given that adjacent squares have a difference of at most $4$, that means that the numbers in the squares of the sub-board can at most differ by $24$ from $n$, as all squares are within $6$ 'steps' from the center square. And since there are $49$ squares on the board, that means that the numbers on the board have to be $n-24$ through $n+24$.

But while the $4$ squares at the corners of the sub-board can differ by up to $24$ from $n$, the other squares can differ by at most $20$, and hence there is no way to place the $8$ numbers $n-24$, $n-23$, $n-22$, $n-21$, $n+21$, $n+22$, $n+23$, and $n+24$ on the sub-board. Contradiction!

Obviously, if we can't place different whole numbers on a $7 \times 7$ board with adjacent squares having a difference of at most $4$, then we can;t do it for a $8 \times 8$ board either, since if we could do it for an $8 \times 8$ board, then it would be done for any of the $7 \times 7$ 'sub-boards' as well, which we proved is impossible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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