Maths Olympiad Prep

Library / /412 of 520

Combinatorics Difficulty 7.3 National olympiad, round 2 Find the answer

Sixteen dots are arranged in a four by four grid as shown. The distance between any two dots in the grid is the minimum number of horizontal and vertical steps along the grid lines it takes to get from one dot to the other. For example, two adjacent dots are a distance 1 apart, and two dots at opposite corners of the grid are a distance 6 apart. The mean distance between two distinct dots in the grid is mn\frac{m}{n}, where m and n are relatively prime positive integers. Find m+nm + n.

[img]https://i.snag.gy/c1tB7z.jpg[/img]

A number or a short expression. Spacing and $ signs are ignored.

Solution

To find the mean distance between two distinct dots in a 4x4 grid, we need to calculate the total distance for all pairs of dots and then divide by the number of pairs. We will use casework to count the number of pairs for each possible distance.

1. Calculate the number of pairs for each distance:

- Distance 1:
Each dot has 2 adjacent dots (one horizontal and one vertical), except for the dots on the edges and corners.
- Corners (4 dots): Each has 2 adjacent dots.
- Edges (8 dots): Each has 3 adjacent dots.
- Interior (4 dots): Each has 4 adjacent dots.

Total pairs:
4×2+8×3+4×4=8+24+16=48 4 \times 2 + 8 \times 3 + 4 \times 4 = 8 + 24 + 16 = 48
However, each pair is counted twice, so we divide by 2:
482=24 \frac{48}{2} = 24

- Distance 2:
- Horizontal or vertical distance of 2:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
- Diagonal distance of 2:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
Total distance 2 pairs:
18+18=36 18 + 18 = 36

- Distance 3:
- Horizontal or vertical distance of 3:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
- Diagonal distance of 3:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
Total distance 3 pairs:
18+18=36 18 + 18 = 36

- Distance 4:
- Horizontal or vertical distance of 4:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
- Diagonal distance of 4:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
Total distance 4 pairs:
18+18=36 18 + 18 = 36

- Distance 5:
- Horizontal or vertical distance of 5:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
- Diagonal distance of 5:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
Total distance 5 pairs:
18+18=36 18 + 18 = 36

- Distance 6:
- Horizontal or vertical distance of 6:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
- Diagonal distance of 6:
- Corners: Each has 1 pair.
- Edges: Each has 2 pairs.
- Interior: Each has 4 pairs.

Total pairs:
4×1+8×2+4×4=4+16+16=36 4 \times 1 + 8 \times 2 + 4 \times 4 = 4 + 16 + 16 = 36
Each pair is counted twice, so:
362=18 \frac{36}{2} = 18
Total distance 6 pairs:
18+18=36 18 + 18 = 36

2. Calculate the total distance:
Total distance=1×24+2×36+3×36+4×36+5×36+6×36 \text{Total distance} = 1 \times 24 + 2 \times 36 + 3 \times 36 + 4 \times 36 + 5 \times 36 + 6 \times 36
=24+72+108+144+180+216=744 = 24 + 72 + 108 + 144 + 180 + 216 = 744

3. Calculate the number of pairs:
(162)=16×152=120 \binom{16}{2} = \frac{16 \times 15}{2} = 120

4. Calculate the mean distance:
Mean distance=744120=6210=315 \text{Mean distance} = \frac{744}{120} = \frac{62}{10} = \frac{31}{5}

5. **Find m+n m + n :**
m=31,n=5 m = 31, \quad n = 5
m+n=31+5=36 m + n = 31 + 5 = 36

The final answer is 36 \boxed{36}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.