15th Balkan 1998 Problem 1 How many different integers can be written as [n 2 /1998] for n = 1, 2, ... , 1997? Solution
: 1498. Let f(k) = [k 2 /1998]. We have k 2 /1998 - (k - 1) 2 /1998 = (2k - 1)/1998 > 1 for k ≥ 1000. Hence for k > 1000, f(k) ≥ f(k - 1) + 1. So the 998 values k = 1000, 1001, ... , 1997 generate 998 distinct values of f(k) all at least f(1000) = [999·1000/1998 + 1·1000/1998] = [500 + 1000/1998] = 500. If k < 1000, then k 2 /1998 - (k - 1) 2 /1998 < 1. So the real values 1/1998, 4/1998, 9/1998, ... , 999 2 /1998 are spaced at intervals of less than one and hence every integer from 1 to f(999) must lie between two of them. Thus for k = 1, 2, ... , 999, f(k) generates every integer from 0 to f(999) = [999·999/1998] = [999/2] = 499, a total of 500 integers. 15th Balkan 1998 © John Scholes jscholes@kalva.demon.co.uk 11 Apr 2002