Sixteen distinct positive integers from 1 to 16 are placed in the cells of a 4x4 grid in a random order, with each number occurring in a cell exactly once.

Determine the probability that the absolute difference between an integer and any of its neighbors (including diagonally) is more than 2 but less than 13.

As a bonus, determine the probability that the absolute difference between an integer and any of its neighbors (including diagonally) is more than 2, but less than or equal to 16.

Assuming I made no errors:

A number can be positioned in
a corner (p = 4/16 = 1/4), adjacent to 3 cells;
an edge (p = 8/16 = 1/2), adjacent to 5 cells; or
a center (p = 4/16 = 1/4), adjacent to 8 cells.

It maybe found that if the integer was 1,2,3,14,15, or 16, there are 5 of the 15 integers where all neighbors of a the cell can meet the criteria of more than 2, but less than 16 (the absolute difference can never equal to 16 as the largest integer, 16, minus the smallest integer, 1, is only 15). For the remaining ten integers, there are only 4 of the 15 integers where all neighbors of a the cell can meet the criteria of more than 2, but less than 16.
For a corner cell, for each of the integers 1, 2, 3, 14, 15, and 16, there are 5!/(5-3)! = 60 permutations of the 15!/(15-3)! = 2730 possible permuations; and for each of the other ten integers (4 to 13), there are 4!/(4-3)! = 24 permutations each of the 2730 possible permuations for each.

((6 x 60) + (10 x 24)) / (16 x 2730) = 5/364

For an edge cell, only the integers 1, 2, 3, 14, 15, and 16 permit the possibility that all neighboring cells may meet the criteria of more than 2, but less than 16. For each edge cell, there are 4!/(4-3)! = 24 permutations of the 2730 possible permuations.

((6 x 24) + (10 x 0)) / (16 x 2730) = 3/910

For a center cell, there is no possibility of all adjacent cells meeting the criteria of more than 2, but less than 16.

(0 / (16 x 2730) = 0

The probability is, therefore,
Corner (1/4 * 5/364) + 
Edge    (1/2 * 3/910) +
Center (1/4 * 0)
= 3367/662480

Posted by Dej Mar on 2009-10-27 20:15:59