Let (X n ) be a sequence of nonnegative, integrable, independent and identically distributed random variables, with common distribution function F. We consider the problem of finding all distribution functions F such that N n −cM n is a discrete time martingale, where N n is the counting process of upper records, M n =max {X 1,…,X n } is the process of partial maxima and c is a positive constant. We solve the problem by explicitly giving the solution with finite support and using this for constructing the solution for the general case by a limiting process. We show that the set of solutions can be parameterized by their support and the mass at the leftmost point of the support.