xyz01(1).pdf

Podró»epoImperiumLiczb

Cz¦±¢15. Liczby,Funkcje,Ci¡gi,Zbiory,

Geometria

Rozdział1

1.Ci¡gi.funkcjeidziałania

AndrzejNowicki16kwietnia2013, http://www.mat.uni.torun.pl/~anow

Spistre±ci

1Ci¡gi,funkcjeidziałania

1.1

Ci¡gi Langforda

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

Zadania o sko«czonych ci¡gach liczb naturalnych . . . . . . . . . . . . . . . .

1.3

Zadania z niesko«czonymi ci¡gami liczb naturalnych . . . . . . . . . . . . . .

1.4

Liczby 6174 oraz 495 i inne . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.5

(A,B,n)-ci¡gi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.6

Funkcje z N do N oraz z N 0 do N 0 . . . . . . . . . . . . . . . . . . . . . . . .

1.7

Funkcje z N 0 do N 0 spełniaj¡ce równo±¢ f ( f ( n )) = n + a . . . . . . . . . . .

1.8

Funkcje z Z do Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.9

Funkcje z Z do Z spełniaj¡ce równo±¢ f ( f ( n )) = n + a . . . . . . . . . . . . .

1.10

Działania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Wszystkie ksi¡»ki z serii ”Podró»e po Imperium Liczb” napisano w edytorze L A T E X.

Spisy tre±ci tych ksi¡»ek oraz pewne wybrane rozdziały mo»a znale¹¢ na internetowej stronie

autora: http://www-users.mat.uni.torun.pl/~anow .

1Ci¡gi,funkcjeidziałania

oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

1.1Ci¡giLangforda

oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

Spójrzmy na 14-wyrazowy ci¡g

4 , 6 , 1 , 7 , 1 , 4 , 3 , 5 , 6 , 2 , 3 , 7 , 2 , 5 .

Wyrazami tego ci¡gu s¡ liczby 1 , 2 , 3 , 4 , 5 , 6 , 7. Ka»da z tych liczb wyst¦puje dwa razy. Pomi¦-

dzy dwiema jedynkami jest jedna liczba. Pomi¦dzy dwiema dwójkami s¡ dwie liczby. Pomi¦dzy

trójkami mamy trzy liczby, itd. Pomi¦dzy dwiema siódemkami znajduje si¦ dokładnie siedem

liczb. Podobn¡ własno±¢ ma 8-wyrazowy ci¡g

2 , 3 , 4 , 2 , 1 , 3 , 1 , 4 ,

którego wyrazami s¡ liczby 1 , 2 , 3 , 4 i ka»da z nich wyst¦puje dokładnie dwa razy. Pomi¦dzy

dwoma wyrazami równymi k , gdzie k 2{ 1 , 2 , 3 , 4 } , wyst¦puje dokładnie k liczb.

Tego rodzaju sko«czone ci¡gi nazywa si¦ ci¡gami Langforda ( [MG] 43(346)(1959) 250-255,

[OM] Chiny 1986 ). Je±li n jest liczb¡ naturaln¡, to ka»dy (2 n )-wyrazowy ci¡g, o wyrazach ze

zbioru { 1 , 2 ,...,n } i posiadaj¡cy omawian¡ własno±¢, nazywamy n-ci¡giem Langforda

1.1.1. Przykłady n-ci¡gów Langforda.

n = 3 :

2 , 3 , 1 , 2 , 1 , 3 .

n = 4 :

2 , 3 , 4 , 2 , 1 , 3 , 1 , 4 .

n = 7 :

4 , 6 , 1 , 7 , 1 , 4 , 3 , 5 , 6 , 2 , 3 , 7 , 2 , 5 .

n = 8;

4 , 6 , 1 , 7 , 1 , 4 , 8 , 5 , 6 , 2 , 3 , 7 , 2 , 5 , 3 , 8 .

n = 11 :

8 , 6 , 10 , 3 , 1 , 11 , 1 , 3 , 6 , 8 , 5 , 9 , 7 , 10 , 4 , 2 , 5 , 11 , 2 , 4 , 7 , 9 .

n = 12 :

8 , 6 , 10 , 3 , 1 , 11 , 1 , 3 , 6 , 8 , 12 , 9 , 7 , 10 , 4 , 2 , 5 , 11 , 2 , 4 , 7 , 9 , 5 , 12 .

1.1.2. Niech n 2 N . Je±li istnieje n-ci¡g Langforda, to

n 0

(mod 4)

lub n 3

(mod 4) .

([MG]43(346)(1959)250-255,[OM]Chiny1986) .

D. Załó»my, »e pierwsza liczba k stoi na miejscu o numerze a k . Wtedy druga liczba k stoi na

miejscu o numerze a k + k + 1. Wszystkie dane liczby zajmuj¡ miejsca z numerami od 1 do 2 n . Suma

wszystkich numerów jest wi¦c równa 1 + 2 + ··· + 2 n = n (2 n + 1) . Z drugiej strony:

( a 1 + a 1 + 2) + ( a 2 + a 2 + 3) + ··· + ( a n + a n + n + 1) = 2( a 1 + ··· a n ) + n ( n + 3)

czyli 2( a 1 + ··· + a n ) + n ( n + 3)

= n (2 n + 1). St¡d wynika, »e

a 1 + a 2 + ··· + a n = n (3 n − 1)

jest liczb¡ naturaln¡. To jest mo»liwe tylko wtedy, gdy n = 4 k lub n = 4 k − 1.

6 AndrzejNowicki,Podró»epoImp.L.15 Ci¡gi,funkcjeidziałania

1.1.3. Je±li n jest tak¡ liczb¡ naturaln¡, »e n 0 (mod 4) lub n 3 (mod 4) , to istnieje

n-ci¡g Langforda. ([MG]43(346)(1959)250-255,[OM]Chiny1986) .

D. Niech n = 4 m . Dla m 6 2 przykłady podane s¡ w 1.1.1. Załó»my, »e m > 3. Mamy wtedy

nast¦puj¡cy n -ci¡g Langforda:

4 m − 4 , ··· ( p ) ··· , 2 m, 4 m − 2 , 2 m − 3 , ··· ( n ) ··· , 1 , 4 m − 1 , 1 , ··· ( n ) ··· , 2 m − 3 ,

2 m, ··· ( p ) ··· , 4 m − 4 , 4 m, 4 m − 3 , ··· ( n ) ··· , 2 m + 1 , 4 m − 2 , 2 m − 2 , ··· ( p ) ··· , 2 ,

2 m − 1 , 4 m − 1 , 2 , ··· ( p ) ··· , 2 m − 2 , 2 m + 1 , ··· ( n ) ··· , 4 m − 3 , 2 m − 1 , 4 m.

Niech n = 4 m − 1. Dla m 6 2 przykłady podane s¡ w 1.1.1. Załó»my, »e m > 3. Mamy wtedy

nast¦puj¡cy n -ci¡g Langforda:

4 m − 4 , ··· ( p ) ··· , 2 m, 4 m − 2 , 2 m − 3 , ··· ( n ) ··· , 1 , 4 m − 1 , 1 , ··· ( n ) ··· , 2 m − 3 ,

2 m, ··· ( p ) ··· , 4 m − 4 , 2 m − 1 , 4 m − 3 , ··· ( n ) ··· , 2 m + 1 , 4 m − 2 , 2 m − 2 , ··· ( p ) ··· , 2 ,

2 m − 1 , 4 m − 1 , 2 , ··· ( p ) ··· , 2 m − 2 , 2 m + 1 , ··· ( n ) ··· , 4 m − 3 .

Przez ··· ( p ) ··· oznaczyli±my ci¡g kolejnych liczb parzystych, a przez ··· ( n ) ··· ci¡g kolejnych liczb

nieparzystych.

1.1.4. Wyrazami ci¡gu ( a 1 , a 2 , ...,a 50 ) s¡ liczby całkowite od 0 do 24 , przy czym ka»da z

tych liczb wyst¦puje dokładnie dwa razy. Wiadomo, »e je±li a i = a j dla i < j, to j − i = a i + 1 .

Czy taki ci¡g istnieje?

O. Istnieje. Przykłady:

(23, 21, 19, 17, 24, 22, 20, 18, 16, 7, 5, 8, 6, 4, 0, 0, 5, 7, 4, 6, 8, 17, 19, 21, 23, 16, 18, 20, 22, 24, 14,

12, 10, 15, 13, 11, 9, 2, 3, 1, 2, 1, 3, 10, 12, 14, 9, 11, 13, 15) lub

(23, 20, 18, 21, 24, 22, 16, 19, 17, 6, 7, 8, 4, 5, 0, 0, 6, 4, 7, 5, 8, 18, 20, 16, 23, 21, 17, 19, 22, 24, 12,

14, 11, 15, 13, 9, 10, 3, 1, 2, 1, 3, 2, 12, 11, 9, 14, 10, 13, 15).

Pierwszy ci¡g podał Z. Dimitri (Francja), a drugi ci¡g podali M. Eﬁmow i W. Sawczenko (Mołdawia)

podczas konkursu zadaniowego w Zakopanem 1995 roku.

F R. O. Davies, On Langford’s problem , [MG] 43(346)(1959) 253-255.

C. J. Priday, On Langford’s problem , [MG] 43(346)(1959) 250-253.

N. Shalaby, T. Stuckless, The existence of Looped Langford sequences , [Crux] 2000 86-92.

oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

1.2Zadaniaosko«czonychci¡gachliczbnaturalnych

oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

1.2.1. Sum¡ liczb naturalnych a 1 ,a 2 ,...,a 1995 jest 3989 . Wykaza¢, »e istniej¡ takie liczby

naturalne n,m, »e a n +1 + a n +2 + ··· + a n + m = 95 . ([OM]Indie1997) .

1.2.2. Dane s¡ takie liczby naturalne x 1 ,...,x n i y 1 ,...,y m , »e

x 1 + ··· + x n = y 1 + ··· + y m < nm.

Wykaza¢, »e w równo±ci x 1 + ··· + x n = y 1 + ··· + y m mo»na skre±li¢ kilka składników tak, »e

równo±¢ pozostanie prawdziwa. ([WaJ]248(77),[Kw]7/197836) .

AndrzejNowicki,Podró»epoImp.L.15 Ci¡gi,funkcjeidziałania 7

1.2.3. Niech a 1 ,...,a n b¦d¡ liczbami naturalnymi ( niekoniecznie ró»nymi ) . Niech f k ( dla

k = 1 , 2 ,... ) oznacza liczb¦ tych liczb spo±ród a 1 ,...,a n , które s¡ wi¦ksze lub równe k. Wtedy

f 1 + f 2 + ··· = a 1 + a 2 + ··· + a n . ([OM]Leningrad1964,[Fom]32/64) .

1.2.4. Spo±ród liczb 1 , 2 ,..., 99 wybrano 50 takich liczb, »e suma ka»dych dwóch jest ró»na

od 99 i ró»na od 100 . Wykaza¢, »e wybrano liczby 50 , 51 , ... , 99 . ([OM]StPetersburg1996) .

1.2.5. Dla jakich n > 3 istniej¡ takie parami ró»ne liczby naturalne a 1 ,...,a n , mniejsze od

n + 2 , »e wszystkie liczby | a 1 − a 2 | , | a 2 − a 3 | , ..., | a n − 1 − a n | , | a n − a 1 | s¡ parami ró»ne?

Odp. Dla n = 4 k lub n = 4 k + 3 . ([Kw]3/198347) .

1.2.6. Niech A b¦dzie takim podzbiorem zbioru liczb naturalnych, »e | a − b | > ab

25 , dla wszyst-

kich a,b 2 A. Wykaza¢, »e zbiór A ma co najmniej 9 elementów. Poda¢ przykład 9 -cio

elementowego takiego zbioru. ([IMO]Shortlist1985) .

1.2.7. Dla jakich liczb naturalnych n istniej¡ takie liczby naturalne a 1 < a 2 < ··· < a n , »e

zbiór n ( n − 1)

wszystkich dodatnich ró»nic a i − a j , gdzie i > j, jest zbiorem

1 , 2 , 3 ,..., n ( n − 1)

Uwaga. To jest mo»liwe dla n = 4 , mianowicie 1 < 3 < 6 < 7 . Czy to jest mo»liwe dla n > 4 ?.

(Newmanproblem92) .

1.2.8. Ka»dy wyraz ci¡gu a 1 ,a 2 ,...,a 2 n ,a 2 n +1 jest równy 2 , 5 lub 9 , przy czym a 2 n +1 = a 1

oraz ka»de dwa s¡siednie wyrazy s¡ ró»ne. Wykaza¢, »e

a 1 a 2 − a 2 a 3 + a 3 a 4 −··· + a 2 n − 1 a 2 n − a 2 n a 2 n +1 = 0 . ([Kw]6/2001M1772s.20) .

1.2.9. Niech n b¦dzie liczb¡ naturaln¡ i niech A b¦dzie zbiorem wszystkich 3 n-wyrazowych

ci¡gów, których wyrazami s¡ 0 i 1 .

Je±li , 2 A, to piszemy $ , je±li ci¡g powstaje z ci¡gu przez zamian¦ miejscami

dwóch trójek kolejnych wyrazów. Mówi¢ b¦dziemy, »e ci¡gi i s¡ podobne, je±li istnieje liczba

naturalna s oraz istniej¡ ci¡gi 1 ,..., s 2 A takie, »e

= 1 $ 2 $···$ s = .

(1) Podobie«stwo jest relacj¡ typu równowa»no±ci w zbiorze A.

(2) Moc zbioru wszystkich klas abstrakcji wzgl¦dem relacji podobie«stwa jest równa ( n +1) 3 .

(3) Je±li = ( a 1 ,a 2 ,...,a 3 n ) jest ci¡giem nale»¡cym do A, to oznaczamy:

1 = ( a 1 ,a 4 ,a 7 ,...,a 3 n − 2 ) , 2 = ( a 2 ,a 5 ,a 8 ,...,a 3 n − 1 ) , 3 = ( a 3 ,a 6 ,a 9 ,...,a 3 n ) .

Ponadto, przez | i | ( dla i = 1 , 2 , 3) oznaczamy liczb¦ zer ci¡gu i . Dwa ci¡gi , 2 A s¡

podobne wtedy i tylko wtedy, gdy | 1 | = | 1 | , | 2 | = | 2 | i | 3 | = | 3 | . ([Kw]3/197440) .

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: