Elemente der Mathematik

Kieme Mitteilungen

133

fe - Tuples of the First n Natural Numbers

In connection with the problems of infinite sets investigated by Erdos and Hajnal m [1], Erdos proposed a problem of the Ä-tuples of a finite set. This problem m its most general form can be formulated as follows Take a system of Ä-tuples of the first n natural numbers Suppose that the set of the i^-st, tg-nd, . . , г^-th (/< Â — 1) numbers of an trary /г-tupie of the system does not coincide with the set of the /i-st, ]2~^^> • • • » U~^^ numbers of another Ä-tupie of the system. At most how many Â-tuples can the system contain ? In this paper we solve the problem m a special case.

Denote by / {n, k) the maximal number of Ä-tuples which can be chosen from the first n numbers (1 < Ä < n) such that the last k — 1 numbers of a Ä-tuple do not coincide with the first k — 1 numbers of another selected Ä-tuple.

It IS trivial that f{n, 1) = n.

It will be proved that if Ä > 2 then

, , ,, v" (n-l-2m\

f { n . k ) = 2; k-1 )■

The proof uses induction onn. li n = k, f [k, k) = 1 li n — k -\- 1, only the Ä-tuple of the first and the Ä-tuple of the last k numbers cannot be selected at the same time, consequently f(k-\-l,k)=^k Thus the statement holds for n ~ k, k -\- 1, and it may be supposed that n > k + 2 and it holds for the numbers less than n.

Put N = {1, 2, ... , n) and M = {2, 3, . . ,n — 1). Consider a maximal system 9^ of Ä-tuples of N, satisfying the condition. Denote by л; a [k — 2)-tuple, x с N and x с M will mean that the elements of н are m N and M, respectively. Divide the {k — 1)-tu pies of N into two classes ^ and 5B. If a (Â; — 1)-tuple consists of the first k — 1 elements of a Ä-tuple of 9^, then put the {k — 1)-tupie into %, otherwise into S. Denote by cil{x) the number of (k ~ 1)-tuples of ^, the last k — 2 elements of which form x, and similarly ß(H) denotes the number of (k — 1)-tuples of 58, the first k — 2 elements of which form x. Because of the maximality oi ^ li x consists of the last k — 2 elements of a (^ — 1)-tuple of Щ and it IS at the same time the set of the first к — 2 elements of a (Ä — 1)-tuple of Ъ, then ?l contains the Ä-tuple which is the union of these two {k — 1)-tuples It is obvious that this IS a unique representation of the elements of 9^1 as certain unions of elements of Ш and Ф. Consequently

f ( n , k ) =2Ja { x ) ß { x ) .

xcN

If X contains 1, ol{x) = 0 and if x contains n, ß(x) = 0. Thus it can be supposed that X с M m the sum above. On the other hand li x с M, the (k — 1)-tuple consisting of 1 and of the elements of x must belong to % So if a'(«) denotes the number of {k ~ 1)-tuples of 41 m M, having x as the 1st Ä; — 2 elements, then (x{x) = ol'(x) -f- 1. The number ß'{x) is defined similarly and ß(x) = ß'(x) -f- 1. But then

f ( n , k) ^2Joc(x) ß(x) =2J(ol'(x) + 1) (ГМ + 1)

xQM hQM

= y«.'(x) /3» + X'KM + /*'M) +2*1 < /(" - 2. Ä) + ( ь I ? ) нам кем "CM ^ '