Problem of the Week 1230

Water Wave

Solution

Several solutions came in quickly, but many had an inconsequential error. The only solvers who had the correct answer — 48000 — on first try were Stephen Meskin (Univ. of Maryland, Baltimore County), Stephen Dupal, Joseph DeVincentis, and Witold Jarnicki.

The answer, for general n, is

8 Sum[EulerPhi(i), {i, 1, n − 1}].

For 141, this is 48000. The asymptotic behavior of this (from OEIS reference below) is 4 + (24 n² / π²).

Here is Meskin's solution:

The answer is 
      8 [(# of elements in the Farey Sequence of order 140) − 1]
    = 8 (6000 − 1) = 48000

Reminder: The Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, in lowest terms, have denominators less than or equal to n, arranged in order of increasing size. The cardinality of the Farey sequence is 1 + Sum[EulerPhi[k], {k, 1, n}]

Part I

  1. Let coordinate axes be placed upon the given grid so that the grid lies in the first quadrant with one edge running from (1, 1) to (141, 1). The other corners of the grid are at (1, 141) and (141, 141). Notice that the maximum distance along the x-axis is 140 units; same for the y-axis.
  2. For each element 0 < a/b < 1/1 of F(140), the Farey sequence of order 140, there is at least one line segment connecting two points (x, y) and (z, w) of the grid such that x < z, y < w, and (w − y)/(z − x) = a/b. For example, the points (1, 1) and (b + 1, a + 1). (There may or may not be other grid points on the line segment extended to the boundaries of the grid.)
  3. Conversely, if (x, y) and (z, w) are on the grid and x < z, y < w, and w − y < z − x, then (w − y)/(z − x) is equal to a rational a/b of F(140).
  4. For each adjacent pair of elements a/b < c/d of F(140), select an irrational number — a slope — between them. There are |F(140)| − 1 such pairs; hence we have selected |F(140)| − 1 different irrational slopes.
  5. Let (x, y) and (z, w) be the two points described in (C). Then they are on a line segment of rational slope (w − y)/(z −x) = a/b. Let a wave of irrational slope s cross the line segment. If s < a/b, then the wave will hit (x, y) before (z, w). On the other hand, if s > a/b, then the wave will hit (z, w) before (x, y). Thus in the permutations for waves with slopes less than a/b, the point (x, y) comes before (w, z); while for waves with slopes greater than a/b, (x, y) comes after (w, z). So none of the permutations in the first group is equal to any of the permutations in the second. For any two different irrational slopes selected in (D), there is at least one line segment with slope a/b, containing two grid points in F(140) which is between the two selected irrational slopes. Thus, the permutations induced by the two irrational slopes are unequal. It follows that the permutations for each of the selected |F(140)| − 1 different irrational slopes are all different.
  6. Moreover, these are the only such permutations, since for any adjacent pair of elements a/b < c/d of F(140), all the irrational slopes between them generate the same permutation.

Part II

  1. The preceding part deals only with waves that cross the grid from (141, 1) to (1, 141) at angles of between 0° and 45° to the x-axis. These permutations all begin (141, 1) (140, 1). Angles between 45° and 90° and waves that enter the grid at the other three corners are dealt with by symmetry.
  2. To deal with angles greater between 45° and 90°, we could flip the coordinate axes about the line running from (141, 1) to (1, 141) or — what amounts to the same thing — flip the given grid about the same line. In any case, the same argument works giving us the same number of permutations all beginning (141, 1), (141, 2), thus differing from the first set of permutations.
  3. Thus we have 2(|F(140)| − 1) for waves hitting (141, 1).
  4. We can rotate the coordinate axes or the grid itself to count in the same way the permutations for waves hitting the grid at the other three corners getting the same number of permutations in each case. The three sets of permutations will all be different, and different from the first, since their permutations will start with (141, 141), (1, 141) and (1, 1), respectively.
  5. Thus we have 4{2(|F(140)| − 1)} = 8(|F(140)| − 1) total permutations.
    6. For n × n grids, the answer is 8 (|F(n − 1)| − 1). These values can be found at the On-Line Encyclopedia of Integer Sequences® as the number of coprime pairs (a, b) with -n ≤ a, b ≤ n. Also, |F(n)| = 1 + Sum[EulerPhi(k), {k, 1, n}]; see the number of fractions in Farey series of order n.

[Back to Problem 1230]

© Copyright 2016 Stan Wagon. Reproduced with permission.

17 November 2016