3

Part of 1992 Hungary-Israel Binational

Problems(2)

On 100 strictly increasing sequences of positive integers

Source: 3-rd Hungary-Israel Binational Mathematical Competition 1992

100

strictly increasing sequences of positive integers:

A_{i}= (a_{1}^{(i)}, a_{2}^{(i)},...), i = 1, 2,..., 100

1 \leq r, s \leq 100

we deﬁne the following quantities:

f_{r}(u)=

the number of elements of

A_{r}

n

f_{r,s}(u) =

the number of elements of

A_{r}\cap A_{s}

n

f_{r}(n) \geq\frac{1}{2}n

r

n

. Prove that there exists a pair of indices

(r, s)

r \not = s

f_{r,s}(n) \geq\frac{8n}{33}

for at least ﬁve distinct

n-s

1 \leq n < 19920.

combinatorics unsolvedcombinatorics

r-Fibonacci number

Source: 3-rd Hungary-Israel Binational Mathematical Competition 1992

We examine the following two sequences: The Fibonacci sequence:

F_{0}= 0, F_{1}= 1, F_{n}= F_{n-1}+F_{n-2 }

n \geq 2

; The Lucas sequence:

L_{0}= 2, L_{1}= 1, L_{n}= L_{n-1}+L_{n-2}

n \geq 2

. It is known that for all

n \geq 0

F_{n}=\frac{\alpha^{n}-\beta^{n}}{\sqrt{5}},L_{n}=\alpha^{n}+\beta^{n},

\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}

. These formulae can be used without proof. We call a nonnegative integer

r

-Fibonacci number if it is a sum of

r

(not necessarily distinct) Fibonacci numbers. Show that there inﬁnitely many positive integers that are not

r

-Fibonacci numbers for any

r, 1 \leq r\leq 5.

logarithmsnumber theory proposednumber theory