On a Modification of a Problem of Bialostocki, Erd\H{o}s, and Lefmann

Research paper by Andrew Schultz

Indexed on: 27 Jun '05Published on: 27 Jun '05Published in: Mathematics - Combinatorics


For positive integers m and r, one can easily show there exist integers N such that for every map D:{1,2,...,N} -> {1,2,...,r} there exist 2m integers x_1 < ... < x_m < y_1 < ... < y_m which satisfy: (a) D(x_1) = ... = D(x_m), (b) D(y_1) = ... = D(y_m), and (c) 2(x_m-x_1) \leq y_m-x_1. In this paper we investigate the minimal such integer, which we call g(m,r). We compute g(m,2) for m \geq 2; g(m,3) for m \geq 4; and g(m,4) for m \geq 3. Furthermore, we consider g(m,r) for general r. Along with results that bound g(m,r), we compute g(m,r) exactly for the following infinite families of r: {f_{2n+3}}, {2f_{2n+3}}, {18f_{2n}-7f_{2n-2}}, and {23f_{2n}-9f_{2n-2}}, where here f_i is the ith Fibonacci number defined by f_0 = 0 and f_1=1.