Diszkrét matematika 978-963-2790-85-5 [PDF]
155 54 4MB
Hungarian Pages 0 [296] Year 2006
![Diszkrét matematika
978-963-2790-85-5 [PDF]](https://vdoc.tips/img/200x200/diszkret-matematika-978-963-2790-85-5.jpg)
- Author / Uploaded
- Lovász László
- Pelikan József
- Vesztergombi Katalin
Datei wird geladen, bitte warten...
Zitiervorschau
© Typotex Kiadó
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
! " # $# $% &' ()* + , - .*/ 0 '# ( 1#2)' #* #)" , 3' $ $'" 4* 5 6 7 *# )* ' 8'! #! 5 9%/ * # 4 3! : * 5
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
!
" " #$ %#&$ ' ( $ ) *$ +,,-
./ 0 $ ) *$ +,,123 4-5 4--6 ,+ + !
) ;%< = )2 # 8 (!'&!! #2*)2 >2 ' ?'/"@ / !> / !@/ A" )* + % %% >#"% ! # &# !/ .>2 #*/" ' 8 /' '% /" '! # " /* ()2 )" 9 >B )% ' CDE5+ >& 7 8 )% ! 8 + "'( F @!! " G( )% $ H2' 7?' ''( I G 9")# C C J5 & 1 # ! 88 > 1 #)
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
7 7 7 + 7 5 7 6 7 : 7 - 7 ; 7 &#'*# ! >* '*# /#'* #'!
7 #)/2
6' &2 ' C ' C L ! ' C , '*
'"2 /
m
! n #? /#' #'! '*#**%K
|A ∪ B| + |A ∩ B| = |A| + |B|
)"2 # #& !' '*# Z+ ! >* !' '*# /#'* '##2 ) *"* 4 C = AB 7 >2 / ' A ! C /#' '##2 ) + *"* !>''@K
E = {. . . , −4, −2, 0, 2, 4, . . . }
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
<
9 & ) 8 & $ ) ! 9 9 n 9 E ' / 9 9 3 8 $ 9 9 $ a, b, c . . . 8 8 9 9 ! K 8 9 L {a} 9 9 ! {a}$ ∅ 8 9 A 9 J / {a, b} 9 J 9 ! ∅, {a}, {b} {a, b} ( / {a, b, c} 9 9 9 & ! ∅, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}. K7 :L A & 9 / ! A , 7 + 5 N9 7 + 6 < $ 9 9 + 9 ! n 9 9 2n K
L 3 9 $ 9 D 8 9 n A 9 ! a1 , a2 , . . . , an A 9 9 $ 9 a1 $ $ a1 9 &)) 9 8 2 9 / $ a2 = 8 ! 8 9 $ 8 9 & 2 · 2 = 4 9 8 a1 a2 #$ a3 = 9 8 9 9 9 4 · 2 = 8 & 9 #! 9 8 A 9 k $ D 9 F 9 n 9 / /$ 2n 8 9
9 / 2 / 9 !
" n 2n
7 + {a, b, c} 9 8 8 &$ 9 / 9 S 9
)) 9 8 & K & 8L 8$ 9 88! a S 9 E 9 K$ L & K L 9 9 / 1 = /! b S 9 E & = =
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
a∈S
I
N
b∈S
I
N
c∈S
I {a,b,c}
b∈S
I c∈S
c∈S
N
I
{a,b}
{a,c}
N
N {a}
I {b,c}
c∈S
N
I
{b}
{c}
N ∅
7 + O & {a, b, c} 9 9 9 9 8 $ 9 & 98 / / # ! S 9 E = 9$ 9 # & # ?= @ & S 9 9 9 9 / F # 9 ) = $ / # T 8 23 K. n 9 $ 2n L c
;%%&) 99 9 # ' 8 KA ) ) D #$ & 8 L . 8 /$ 9 & &8 & $ 8 # ) / $ # / K & / # 9 9 / $ & L 7 5 7 & 9 / 9 $ 9 9 & $ /$ / / 9 $ 9 / / 9 ,$ 7$ + & . 8 9 $ ) / $ 9 9 +5 = 9 K ) 9 # ,$ 7 ) 7 $ A &/
/ 9 & J / / / , L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
<
A 9 9 # & )9 8 ( 9 8 ) / 8 9 $ & 9 / 9 $ K7 :L ) / / A 9 8 9 & A # 9 #$ 9 9 / K) L # # {a, b, c} 9 ∅, a, ab, abc, ac, b, bc, c.
)/ # 9 $ ) 8 & /$ 9 7, 9 9 & / J / $ +55 8$ 9 & E 39 & Q . 9 E '8 9 K L # 8 =& {a, b, c} 9 ' 8 9 ! # & # 9 $ 9 / 7 $ $ 9 / , {a, c} 9 ?# @ & 101$ 9 a $ b $ c A # 9 9 9 =$ # 7 ,# # ) $ ) & 9 & 9 # ,7, ) / {b} 9 ?# @! , $ 9 9 a $ 7 b $ 9 9 # , ) c 9 / /) ,# 7 # # # ( K & L / 8 1 8 8 7, ! 0 = 02 1 = 12 2 = 102 3 = 2 + 1 = 112 4 = 1002 5 = 4 + 1 = 1012 6 = 4 + 2 = 1102 7 = 4 + 2 + 1 = 1112 8 = 10002 9 = 8 + 1 = 10012 10 = 8 + 2 = 10102
K # * D $ 9 7,$ 9 + / L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
0, 1, . . . , 7 9 9 ?# @ 8 $ 9 , # 8 7 $ 9 A = 9 8! J 9 8 J$ , /$ 9 9 R / / $ & )/! 0 1 2 3 4 5 6 7
⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔
02 12 102 112 1002 1012 1102 1112
⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔
000 001 010 011 100 101 110 111
⇔ ∅ ⇔ {c} ⇔ {b} ⇔ {b, c} ⇔ {a} ⇔ {a, c} ⇔ {a, b} ⇔ {a, b, c}
{a, b, c} 9 9 9 0, 1, . . . , 7 # 9 # F $ n 9 9 /E 0/) / 8$ $ 9 = & 8 $ , #
$ ) # n $ & 9 n + 1 8 $ 2n $ 9 & 9 ! 0, 1, 2, . . . , 2n − 1 1 # 2n $ 9 n 9 9 F 9 / 8$ D $ 9 7, 9 +55 9 A99 & / +55 F +55 ) $ / # 7 . / / # A & $ 9 # / $ 8 / +$ ! (233 − 1)/2 = 116 A ) $ ) # 9 , . / , $ (116 − 0)/2 = 58 )/ , $ = 9 /$ ! (58 − 0)/2 = 29 A ) $ / # 9 7$ 9 (29 − 1)/2 = 14 ) )/ F , 9 /$ (14 − 0)/2 = 7 )/$ =
/ 7 $ )/ (7 − 1)/2 = 3 $ = 9 / 7 $ (3 − 1)/2 = 1 $ 8 ) , )/ +55 9 777,7,,7$ ,,777,7,,7 # & . 9 7, 9 / a1 , . . . , a10 $ +55 9 {a3 , a4 , a5 , a7 , a10 } 9
;%%&) 7 5 7 / B# & 89 ! 8 E 3 # # #$ 9 99 $ 9 /
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
<
# =
$ = 9 / ? 9@ J 8 & Q ( & & / $ 9 B# 8! 8 & / $ =
9 = / 99 $ 9 ) 8 O & / J 9 9 # $ &)) /E ! #
$ ) ) 9 # ) / 9 # &8
/ 8 $ ? & @ ) / A99 9 & & / 9 & J 0, 1, 2 . . . # J 8 1 & # 8 ! / K 8 9 9 L &$ 9 # / K 8 0, 1, . . . , 2n − 1 L & 8 A & ! J 9 9 ) $ J 9 ) 9 & ) 8 . 9 # 9 $ 9
C L C 9! #*) ' &** * #! ' #+ '*# )@ ' #? !'/#'/'Q ' !' /#'/'K 7 /#' ' >* '*#/'K
.* !'/#' n #? /#' # #! #'' /#' "8 #!K
'"2 / #) #@ /#' 2 >* #'*#A !'/#' # >* #'*#A
.* !' '*# # &' '*#)' " Q > n '*#" ( *K 1 )''@ # % / #2 !' '*# >'& ! & /
n
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
/ / 9 $ 9 7,, 9 ) 2100 9 A J E %# / $ 9 K L 9 # ) 9 / K2100 = 1 267 650 600 228 229 401 496 703 205 376L$
8 &$ 9 8 # ) F / / ?@ 8
E / /$ 9 23 = 8 < 10$ K 55 9 L )/$ 9 299 < 1033 A 9 2100 < 2 · 1033 2 · 1033 K L 56 K + 55 , L$ 2100 & 56 9 / / &8$ 9 210 = 1024 > 1000 = 103 T D 8 & $ 9 9 A 2100 > 1030 $ 2100 31 A 2100 9 # / ) 9 8$ 99 /) ) 8 8 F $ 9 n E ! $ 9 $ 10k−1 $ 9 $ 10k k / 9 9 $ 8$ 9 10k−1 ≤ 2100 < 10k . 2100 & 9 / 10x K ) x $ ! x = lg 2100 = 100 lg 2 Klg 7, )= / L )/$ 9 k − 1 ≤ x < k, k − 1 9 $ $ x / = $ 9 k x $ x
x k = )9 # $ 9 x &$ 8 && ) x ' 8$ x # ) K / L )/$ 9 lg 2 ≈ ≈ 0, 30103$ 100 lg 2 ≈ 30, 103$ / k − 1 = 30 A 9 2100 57 .* '*#" ? '*#)' 2100 K R"2 !> # #)" 2n '*# '*#" '*#* C+ '*#)' ½ ( 1 3/$: 210 - )5# 0 103 1 = 22+ .+&8 * ( , #> ( /&: #1 2(!; !2 65/!#:? " # $: /8 . ) (+2 " # 2 $) & # 1 # - &/"!) 0 9 ( 6$: # 2 @A "!) / ) & # 1 # 4 5 $ @@@ "!) / 1 && # + " # 4+&5!6& &/$8 ? &1 &: 4/# /2 # @@@ $8 ? / ) & # 2/#&B #1 - $ "!) 0 220 1 # 4 5 $ $: && B "!) C + 2(! D264!# - '( &; ,& $0 $: #&,
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E FG
F / 9 # / # 8 9 $ 9 # / # # 9 $ 8 $ 9 9 n 9 =
= )9 8 J / a$ b c J &9 / 9 #$ 9 8 9 /$ 5 9 & ! / 9$ 9 = 5 8 9 /$ 9 9 32 = 9&)) 9 8 F ) #$ 9 n 9 =
= 3n 5 8 $ /
9 $ 9 #!
- k n
kn
" / & $ /
8 &$ 9 /9 ) < $ K$ 3L$ 9 J J9#J) $ 9 &9 J 8 / K / 9 8 7> 8/( '! # 13 + 1 #!('! '>K
.* /! # )% !' )** / @8! '@ 8'8 / ( ,+ '* C+ / ( C+ ! #*) ,+ )2 K 9 @ / ) "*)!* 2 C 8'8 + ' 1# #) # > # ()2/ /* / #) "*)! 2 ' ) >" .* !!>> '/"2 ' "*)!K
.A'! "*)!2 ! #) ( )( !' * + )'!@ .* !!>> "*)!'/2 # C / # 8'( #) @ ) # ' ' 8"@ / 2 % ' "*)!+ &>2% #) # 8" >/K
! "#$
8 ) / & 8 ) $ 9 9 &) ) 8 9 n n K# n = 6 n = 7 /$ # 9 #L . /$ 8 ) $ 9 & 8 1, 2, . . . , n K 9 / / $ 0, 1, . . . , n − 1L & = & 9 /! 9 &)) 9 n $ 9 & K L 9 # $ / K) L )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
H IJ
1. a
b 2.
2.
b abc
c
c
a
acb
bac
2.
c
a
bca
cab
b cba
7 5 O & {a, b, c} 9 ) / # 9 9 . n K # 9 $ $ L 8$ = ( 8 / # 8 ? @ $ 9 9 K / ! 8 9 ?9 @ 8L {a, b, c} 9 ) / - ) / # ! abc, acb, bac, bca, cab, cba.
9 ! 9 &)) 9 n / $ ))! 9 ) / # n 9 E 8 ) 9 ! 9 n 8 9 8$ ) J / 9 J n − 1 9 8 $ 9 n − 2$ 9 9 9 n(n − 1)(n − 2)&)) 9 8 & /$ / # 9 + 8 9 /$ / # 9 J / 9 J 9 n · (n − 1) · (n − 2) · · · 2 · 1&)) 9 F 8$ n! 8 K ! ? n & @L A 9 n / # n! 8 9 8 9 / !
n !" n! / 9 / K7 5 L $ 88! 8 E 9 9 9 & T ) / 8 &! 8 8 E A ) # $ 9 8
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
K 8 & $ 9 / Q A ! /) $ 9 J J$ 9 # L . ) /$ 9 9 & 88! / # J 8 J )/ F ) #$ 9 9 n 8 $ n&)) 9 /$ & ) # n / $ K&8L 9 n ) 9 # A n − 1 / $ n(n − 1) ) / # )) n! ) / $ K8L 8 & ) / # 9 # n! 9 @ / ** n OA ! n * .* @88'( >*+ / / 8"@ / OA * * >) OA *K
.* !!>> '/ T )! ) !#'! 'K $+ ** !> ) / '% '*# 2nK
%
A 7,, $ /) . & K # L 9 E 7,, 8 9 2 $ 9 44 ) 9 $ 9 9 100 · 99&)) &/ 9 . $ 9 9 4 > > #@ !)! 8'@ # + /( ' C T C 9! >* !K
!'&@ **'
n k
!!( / 0 ≤ k ≤ n ≤ 5
R"2 nk !! k = 0, 1,nn− 1, n ' C P 8'@! >"* #") !#''@ #2* k #2 "! ' 8 9 # #
9 / A 8 9 / &$ & & /
" # $
n n ; = n−k k
n, k > 0
n n−1 n−1 ; = + k k k−1 n n n n n = 2n . + + ... + + + n n−1 2 1 0
K7 ;L K7 > /
6' &2 !!!>> /
n k
0≤c≤b≤a a b a a−c = . b c a−c b−c
=
n n−1 k k−1
!
(
# ) * .* !!>> @/@ C # ! ! P '#! 8 A '/'K ' / # ! @!) @88'( @ # !#? )"2 # @88'( !#'! #( #)*
)"2 # /#' # #'*# LP5 C D ) CC 5 C,
"2 ' {a, b, c, d, e} /#' 8' !'/#'* # !'/#' c ' # #
{a, e}
'*#/#' ! # )2 # ' 8' !'/#'+*% A "@ >!)*2 Z ⊆ R .* *% *&/% ∅, N, Z+ , Z, Q, R /#' 8'8K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
7 #' L+ !'()( ! L+# '/% >'& !' '*#Q ' 5+ '/% ! >* >'& !' '*# /#'*K
4 A = {a, b, c, d, e} ! B = {c, d, e} "2 ' A /#' 8' !'/#'* # B /#'' #' #?
.*# /#' #'*# ) 5 C ! C5 .* # / /*# /#' 2%"* #'!K
/#' 8#* '##2 ) *"K
7 /#'
4 C = AB 7 ' ' A ! C /#' '##2 ) *"K
A
4 A, B ! C /#' # "@ / '"2 /
A ⊆ C
A ∪ (B ∩ C) = (A ∪ B) ∩ C.
'"2 >!) &!! / ' A ⊆ C ! % '@! 7 /#' A \ B / A >&#'*# B >) >* '*#Q / A #& B >) M#>'&N % '*# /#'K
6' &2 / '( A, B ! C /#' ! ((A \ B) ∪ (B \ A)) ∩ C = ((A ∩ C) ∪ (B ∩ C)) \ (A ∩ B ∩ C).
4 A /#'Q "8" A2 ' A /#' !#? !'/#' /#'* 7 ' ' * 8'@K
A∪B 2
A∩B 2
=
A
=
A
2
∪
2
∩
B 2
B 2
;
A∪B
;
A∩B
2
⊇
2
⊆
A 2
∪
2
∩
A
B 2
B 2
; .
4 B ' A /#' !'/#' |A| = n |B| = k .* !'/#' A+ # B + #' #? /#'K R"2 5 ! L5 + '*#)' "* #") )"2 8' ( * M8')%*N >"* F(''@ > )#! ! '*# C+ '*#)' '*#& 8' + '*#)' " '*#&**
'"2 / #) !' '*# &/% @88'( +/* 8'+ ! 722 # / ' &* )"!( !+ #?
.* '*#" 10100 * >'*%"*K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
K
L
/% )2 ! ) '!' /* !!>> */+ 2 # 88 ' U 5 *#* (* 8'@K .* " ? >'& !' '*# # *# ! #* # '*#" @88'K )* C @88'( )*" )* ( ! > '" ' 8'@ *' # * ! " ! ' ! !' '" ' "** )) " #& # > ) #) .* !>!( * ' "**K '"2 / '% % )#! '( "** '*#
10 9 3 2 · ··· · . 2 2 2 2
VW#2* !>'"@ ' "** '! X !>> 2 @) C *2 ' @' /*#! !+ >> >/% .* !!>> @)/"@ @)8'@ / #)/*# &>2% )( !' ! #) #( > @)@Q )( '*#A !>> !' ! #( * 8 #)+ '* @88'( > )/2Q #)/*# !>>% , ) ! #) #( > !>> @)@K .* !!>> '&'/@ n * /*# '& / * + ' #) '& "2 /'*K 2'*"2 * ) #)** / /* !!>> "*'+ / P # 7 *''2 # #! /'** ) !>> ' * .* ! @88'( M'%N C ? ' /% '%%K )"2 # >'& !' a b ! c '*# # a b a =2 . b c c
6' &2 /
n n−2 n−2 n−2 = +2 + . k k k−1 k−2
8 A '* 20 ( / .* !!>> *'/2 /*# # #* # @( #K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
+ #!"#$ A $ 9 8 & # ( 8 & !
n ( * ( n )/! 1=1 1+3=4 1+3+5=9 1 + 3 + 5 + 7 = 16 1 + 3 + 5 + 7 + 9 = 25 1 + 3 + 5 + 7 + 9 + 11 = 36 1 + 3 + 5 + 7 + 9 + 11 + 13 = 49 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 = 100
$ 9 $ $ ) ) = $ 9 n ) )) n2 7, /$ 9 # $ 9 9 #$ 9 n E F 9 / )$ 9 $ / . 9 E
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
JIJ
8 9 T n ) K 8QL 2n − 1$ / 9 $ 9 1 + 3 + . . . + (2n − 3) + (2n − 1) = n2 . K+ 7L / # 8 n−1 ) ! 1 + 3 + . . . + (2n − 3) + (2n − 1) = 1 + 3 + . . . + (2n − 3) + (2n − 1).
# 8 (n − 1)2 $ n − 1 ) 9 # (n − 1)2 + (2n − 1) = (n2 − 2n + 1) + (2n − 1) = n2 , K+ +L / O / ) Q )) 9 / &$ / . # $ 9 /Q F 8 $ 9 ) # 9 / & n − 1 ) # 9 / &$ K K+ +L )L ) / n ) # & / F )) & /$ 9 / Kn − 1L $ = K nL A 9 / $ 9 n F /$ 9 n = 1 9 $ 9 n = 2 K ) / $ /$ 9 # 8 8L . #! #$ 9 n = 2 $ 9 8$ 9 n = 3 $ n = 3 $ n = 4 $ 9 n $ = / / 9 # n A # J J 8 K 8 / D #D / #& L # ! 8 &$ 9 / ! /
) 8 & $ 9 KL 7 # & # /
$ 9 KL 9 n − 1 /
=$ n K9 n > 1L / # KL KL $ = n /
) 8 1 /$ 9 7 ) ? @ )) 12 $ /$ 9 n − 1 )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
MJ J
(n − 1)2 $ n n2 $ n > 1 / # ) 9 9 8! n ) n2 / # 9 # A / n = 1 KA / # 8 L A/ )# / n $ 9 &9 9 / n 9 n − 1 K / # '$ L 8 8 9 &8 n − 2$ n − 3 K ! k$ k < n 8L #
$ / &9 9 / / # 9 & / ! 9 /
$ 7 $ #
$ ) /
= K. ) / ) # 8 /
$ ##
# $ # & # L A& /$ 9 n = 1 9 n = 0 8 K / # L 9 $ 9 8 K9 / n = 1 $ L )) /$ 9 n! n ≥ 1 ( ( 9 8$ 9 n = 2 K#! 2! = 2$ # ) L$ 8$ 9 /
n−1 n K#$ 9 (n − 1)! ) $ n! = (n − 1)! · n ) n$ 9 ) L A 9 n! 7 ) K n = 1 L '"2 )2% ! !@ / ! >*
n(n+1)
#) n >'& !' '*#
6' &2 " )2% / ' ( n #!' '*# 8'
n(n + 1)/2
)!''@ #!'@ / n + 1 # *' n(n + 1)/2 !'+ * @)8' #* 9 @ / #) ' !'* '*+ #" # #* * )( ! ' '* #)K '*#*" 8 !'*K .* '*# P !'*K 9 @ / #) @88'( A
!)! ) *' >"* )"2 A" ' &* C )
6' &2 C ) C * >"*
'"2 ' * '* 1 · 2 + 2 · 3 + 3 · 4 + . . . + (n − 1) · n =
(n − 1) · n · (n + 1) . 3
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
JIJ
2(1+2+3+4+5) = 5 . 6 = 30
1+2+3+4+5 = ?
+ 7 n ) + 7 + & ) 0 9 H/ K7;;;J7"* *"2 / n+ ' 8 '/% / n(n + 1) = (n − 1)n + 2n.
' '>( (n−1)n ' )2% ! ' >* 2n >) >*
' n(n+1) '*# /* >* ! >* '*# 8' ! # # >*
' *&* ' *% /#Q ' n = 10 >!)*2 10 · 11 = 110 ' >) >* '*# 7 " ' &*K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
N MI
;2 O # ' * )2% ' &*
n
! ' *&* *% ' ' n = 1 (
/ n = 2 ! ! ! ' # >*/2'# 9 @ /* / ' *&* '( n − 1 ( *% /#' ' ' )2% ! >"* *"2 / ' *&* n ! ' 9@ /* ' ' n ( *% S = {a, b, c, d, . . . } /#' # # 8'8 ! >*/2'# $ @ S +( c "8" #)! /#'* S 7 S # '*# n − 1 ' )2% ! ' P > # S #) # ') >* # a ! b *# P > P ' a ! b #'!>" 7 @ ' c+ ! @ d+Q ' & > A" n − 1 #? /#' "8" S ' )2% ! ' S # > ') "8"@ ' > P + 7 ' P ' a ! b #'!>" * / P = P F ' *% / c+ * # P + 8 '! *# P + ' /* P + #) ') 0&*2 # *% /# . /K
, -" 3 $ 9 K) / n!L 8
) $ & $ 9 9 )8 #$ ! 9 100!E n ( 8 F $ n 2 E . n = = 2, 3, 4$ n2 1$ 3 -$ n = 2 9 $ n$ n = 3 $ 9 ) = 4$ ( n 9 #$ 9 9 n ≥ 4$ n = n1 < n2 A 9 /! n n−1 2 = n 2
9 $ n . ) / /$ 9 $ 7,,,$ $ 9 n > 2001 &9 8 ! n 2 →∞ n
(n → ∞) .
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
MJ J
A ! $ n2 2n E ( n ! 12 < 21 $ 22 = 22 $ 32 > 23 $ 42 = 24 $ 52 < 25 1 2n $ 8 $ n2 / 210 = 1024 $ 102 = 100 1 9 #$ 9 2n /n2 &9 $ 9 n
6' &2 / / n ≥ 3 2n > n3 ) !' >"* '"2 / 2n /n2 *# !! + / / n !
A 8 / )# 9 / $ 9 8 8 100! J $ n! = 1 · 2 · · · n J
# K 7 L D 8 9 9 /$ ) +$
$ 9 n! ≥ 2n−1 . #! n! ≤ ≤ nn−1 $ / n − 1 K 7 =& D 8 9 /L$ $ n KF / # 9 $ n$ / $ nn−1 L 2 / 9 $ 9 2n−1 ≤ n! ≤ nn−1 .
K+ 5L
n! & # /$ 9 #! n = 10 # / 29 = 512$ & 109 K+ 5L ) ) / 9 $ 9 n! 2n 8 / ! n 9 ) / # 9 E ( n 9 ! 21 = 2 > 1! = 1$ 22 = 4 > > 2! = 2$ 23 = 8 > 3! = 6 1 ) ! 24 = 16 < < 4! = 24$ 25 = 32 < 5! = 120 '
$ 9 n $ n! $ 2n n n + 1 )8 $ 2n /) $ n! (n + 1)
/
&2 ' #! )# )2% ' &** *2 ! n! > 2n
n≥4
" ) $ # n! 2 $ / / $ # $ 9 /
U & /V n! ∼
n n √ 2πn. e
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< J O
1 π = 3, 14 . . . / = 8 $ e = 2, 718 . . . / )$ ∼ ) $ )) 89 ! n! n n √ e
2πn
→1
(n → ∞).
8 & $ 9 $ e π / & / ) F 9 / 8$ # ! 9 E & /
100!
100! ≈ (100/e)100 ·
√ 200π.
$ 9 9 $ = )/ $ 9 / 7, )= / $ && 8 lg(100!) ≈ 100 lg(100/e) + 1 + lg
√
2π = 157, 969 . . . .
100! ? #@ 7:< K ? #@! 8 ) L
# *! A 6, /# 8 / &) 7< /# 2 ) $ 7- N ) 7+ A ) K $ /L . $ 2 N ) 8 $ : 8 9 2 A))$ 9 $ N A) 8 ( /# & ) ( / ! 9 $ 2 $ N $ A) E A )# 9 / 6, /# $ / 9 6, 2 ) K7 OA% *% '* CT+ ' L+ ' ! C+ A*' 92)"2 / D OA ' ! ' P ' ! A*' C ' ! A*' E+ ' ! A*' ! C+ ' ! A*' ! '! ,+ ! A*'* L+ '! ! A*'* 5+ '! ! A*'* D+ ) '))( *2 $ L OA #) > /%) 92)"2 !@ / ! 8'@ * ' #) OA ?' .* OA ' '* K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
MJ J
! . / 9 / 3X Y $ ) / 9 E . / 9 E A / /$ 9 &8 9 9 $ 3X Y # K ) 8 9L ' 9 & #$ 9 / A $ / $ 9 :,, 9$ 3X Y 7, # . 3X Y $ / 9 $ & 9 8$ , 9 K ) L$ & $ 7 $ 8 & 9 $ & K) L :,, # # 9 A $ 9 3X Y & :,, ,,7 9 F / /$ 9 9 $ 9 / ! $ 9 3X Y $ / 9 )) & 9 / ()8 :,, ,,7 9 / ! ?3X Y , 9 = @$ ! ?3X Y 7 9 = @ / # ) ?3X Y :,, ,,, 9 = @ . / / $ 7, # 8 / F /) :,, ,,7 / $ $ 9 /$ $ 9 /! + n n" A 8 $ ) # $ $ 9 8 ) $ ) & / ) / / ( 8
K / $ ? @ ) L
,- & & & .- $ / $ 0 ( $ $ 1. ½ $/&5!2 +85 22+$ 1 3/$: "!8 " &! 6 1 3/$: * # + 1 6$: # ##: 3 )2(!&& & 8 #5 &? (, P Q/8 ? 1 5 & $D2 +&: "" & +4( &+2%# 2 #D2 88B&1 3/$: # &!&3 #!# $ , = !" $: #; #!# + 9 # /4 2( 9 & /28B& ( 1 3/$: 6$: # ##: 3 )2(!&6 * #1 $: #R# $ (/&!2 &+#: $+" # & 3 & # > ( &: # " (/#:; !2/ 62/ # * (
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A QF
% 8 8 ) $ ) 9 $ -6$ 9 64 F :, $ $ 9 2 /$ 9 )
$ 7: ? @ √ 7, = $
# 200 ≈ 14, 1 2 /$ 9 (∗) ( $ ) #$ 9 )
9 # $ & 9 $ / 8 & 9 $ 9 8 P Q )
$ # 9 %8 = A, B, C D N /
P Q ) $ P Q ) K + + L P Q 9 $ P Q $ J & 8 J 9 #
C
B
Q'
14 .1
10 cm
cm
Q
D
P P' A
+ + ( $ /
8 & 9 8$ 9 P ) AB K9 $ 8 = L Q P A Q P B 8 90◦ $ & 9 8 K=&
8 8L$ 9 Q P A A AQ Q P A 9 $ $ P Q $ # 9
Q 9 Q # ) = )/$ 9 $
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
MJ J
# A $ ) = 9 $ # J 9 9 # Q $ 9 (∗) A 9 /$ 9 ) $ 7: 9 9 $ $ 9
/ $ 76$+ & / . B# )/= $ 9 $ 9 ) # / 8 / $ 9 & 8$ 9 9 $ & 8 8 # J J ) & / K / &/ ! 9 & /$
8 9 J 9 & 8$ # /QL 6' &2 / * 1Y Z+ 2 '* /"
0#12 $ # ! F/ / $ & & 9 / J $ 9 $ / 8 )Q 39 ! J F 5-- 9 8 ) $ 9 $ 9 5-; F /) :, /$ ) & = & R & J ) F E A $ 9 5-; $ & 9 8 =
$ $ 9 A 5-- & /9 $ 9 $ 9 9 9 $ 9 :, E ! +5 9 :,Z Q A 9 # / $ ( 2 8 # / 8 &$ 9 )# ) 8 ) # :, ) ) 7 : & & ) 36650 8
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E -JS0 G GJ
. $ E 1 7 ; & & /$ 9 / ! 366 · 365 · · · 317 # 9 $ 9 366 · 365 · · · 317 . 36650
# ) K ) 9 # # )L 8 9 9 /$ ! & # $ J 8 ) n$ ) k J ( 8 9 ! n(n − 1) · · · (n − k + 1) nk
E 0 $ 9 K7 L
nk . n(n − 1) · · · (n − k + 1)
K+ :L
) & / A n 9 8 / $ 9 / $ # P9 8 $ 9 # / )$ &8 & 9 /! n n n nk = · ··· . n(n − 1) · · · (n − k + 1) n−1 n−2 n−k+1
A 9 $ /
8 F $ 7$ J 9 J F $ 9 $ 9 / ! $ 3 R
ln
nk n(n − 1) · · · (n − k + 1)
n n + ln + ... n−1 n−2 n . + ln n−k+1 = ln
K+ -L
& )/ J e = 2, 71828 . . . J )= / / (&8 # $ 8 / / /#$ 8 9 E ½ J (( & ( $:2( 8T2; +22 & +&%# 1 3/$: #5 # 2(%& +2# 4 $:./8!# * &B2(;#T ( #: &*!#* &B # # $ (U . "86!8 V? 4+&5!6& . & 3 , # 2/ & 8 !"" # ./856& &,1 # ( +* '"" # 4) !2.+& = ##+& &+#: $ 2 # 2 ""> & +8+2 '"" # 4 * &B2(;#T2+$+" # 2 & 3 # 1 ( 8,& (/#" # " &! 3 B1 3/$: #!8 2+&: #'* & ¾ &*+$8 &/$ 8 62 M6 8$ +2 4 8 +44 # (+8 * ( " = W 2(!( 5" #>1 3/$: 2 $; 2+$+* & 2(/8(!2 ( '22( 5!28 * ( 3 22% * 22( 1 +2 $:/82 "" # &*+$ (3 22%
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
MJ J
1
1
2
3
0
–1
–2
+ 5 e )= /&8
D T 19
D x − 1 9 + 5 /&8
D $ y = x − 1 9 8 8 " 9 #$ 9 &8
D 9 $ 9 x = 1 9 K ) 9 /L P 9 ln x ≤ x − 1. K+ ;L F ) # E 79 x D
9 A 9 /! 1 ln x = − ln ≥ − x
1 −1 x
=
x−1 . x
K+ *'%! c A*'%! >) d '% ! '( OA '*# x '% ! A*'%! y '% ! '(! u '% ! A*'%! v '( ! A*'%! >) w 1# 2)"2 / /* OA >!)*2 ' ' ! A*+ ' ) # / * ' ! ! #) @ ) 2 &* / /* OA "* ' '* 722 # >!)* &!! / #*% >"* !)! # 2)"2 #*' '"2 / ' '* !'*# " a + b + c + d ! * a + b + + c + d − x − y − z − u − v − w
*'2 LT * C+! >'& !' '*# '"2 / 8'@ # @8! * P
F O% P >* 5 >* /! 5 >* > ! , >* '8) ' 4* /* ' @ O%% / ' 8'8@ ! # '&?K 4* /* ' @ O%% / ' 8'8@ ! @88'( '&?K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
!" -## #
7 & 8 nk $ " 8 A $ 9 / 8 8 9 #
?&)@T
8 ()8 $ 9 (x + y) & 9 / ( 8 9 ) ! (x + y)2 = x2 + 2xy + y 2 , (x + y)3 = (x + y) · (x + y)2 = (x + y) · (x2 + 2xy + y 2 ) = = x3 + 3x2 y + 3xy 2 + y 3 ,
& 9 /! (x + y)4 = (x + y) · (x + y)3 = x4 + 4x3 y + 6x2 y 2 + 4xy 3 + y 4 .
) 8 9 # 8Q / 8 J ) / J 7 *%" >"*
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< MJJJ GQ I? G
8 &$ 9 n 8 / k = $ 9 / /$ 9 ) R 9 G n 2 n / K =
L 9 1, 2, . . . , k 9 /$ n1 , n2 , . . . , nk $ 9 9 ) 8$ 9 n1 + n2 + . . . + nk = n$ / ! 9 &)) 9 / E )) 9 n 9 =
= / ) K# L n1 $ n2 $ 9 n3 k K L ) / # kn '
$ 9 9 /$ 9 KL ) n! 8 9 / A $ / $ $ / 9 K 8 $ 9 )L $ 9 9 $ ) / # 8 1 // 9 # 8 $ 9 ) $ ) T $ $ 9 R ) / 9 n1 !&))$ n2 !&)) 9 & n1 ! · n2 ! · · · nk !
8 9 $ 9 n! n1 !n2 ! · · · nk !
&)) 9 / ' "*)! '** /(! 8'(!>> #/*'+ /"2 F('8 *'"2 ' ( # '* n1 ) "*)! ' n +!!>> /"@ # F'2* #)! n − n1 "*)!% *'"2 n #*) # k2 ) "*)!* ! & * F!'&@ )# ! '"2 / ' )#! 2 ' # # ' #! >2 8'( >* #* #) >!#* >"* "% #( / 7 *''2 # #! 1
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< < G
)
n = k n1 = n2 = . . . = nk = 1
Q
n1 = n2 = . . . = nk−1 = 1 nk = n − k + 1
Q k = 3 n = 6 n1 = n 2 = n 3 = 2
Q
k=2
5 7 3 ?@ 9 .* !!>> / '/@ ** n * * A / # ( *#)" #* L C * K G'@ / * * #* / /* ( !@ ' ' / '! # *' .* @88'( / '! / * * # 8'@ ! *% ! >) !*% !'@K .* !!>> / '/"@ * * / O2* 8'8 ! #K
( B# E / # J / $ 9 J$ )# / ) $ K) L &9 /$ 9 /
A)9 8 ) / / D= $ 9 ) ! J J
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< MJJJ GQ I? G
A K L $ J / J ?##@ 9 # ) & 8 9 /$ 9 9 8 A 9 &
J / / $ 9 8
.* ##* !'&/@ '%%K
9* 2 !( !'&/( 8 ##K
7 CL ? M'%N !'&/( 8 ##K 7 ( K 8 & & $ #! n ?##@ 9 # # &8
$ 9 # 9 9 8 & 9 $ 9 k K L$ 9 n # n1 K9 n1 , 9 L$ n2 k 3 #$ 9 & n1 +n2 +. . .+nk = n A n1 $ n2 $ ) nk 8 9 9 / A ) ) #! & / $ 9 n k /$ $ 9 9 ) 9 & n! . n1 !n2 ! · · · nk !
$* / ! '% 2 6!/(2!2!) = 180 ## !'&/( F' ' ' ##* '#>"*% + * M! 'N '/"@ #)( !+! ? #+ !' ! * ( # ' )2 ( 1''@ ! '% M!+ @88'(N / # ! ' .* /? # !@ !# '% K ' *!! L5 ?( * .* /? '% # ! ' '%K .* ! @88'( P+? '% !'K ) 0*&2 ) ! *>&2 # /* ! @88'( n+? '% !' . # @ #) )"@ 8+ '( "' * 2* #! ! !/@ * '
9 / ) 8 & ! 9 &)) 9 / n & k E
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< A
¢
¢ A
¢
¢
¢ B
¢
¢ C
¢
¢
¢
¢
¢
D
5 + . &)) 9 / n & k E F ) & K $ 7,, = L . & 9 E F $ / $ 8 ) /) 8$ 9 9 )$ $ 9 ) ) /) F #! 8 9 $ & K 5 + & & 8! 9 n & / $ n1 $ n2 /$ /) 9 8 L / #$ 9 # / & K $ & L (# / $ 8$ 9 K# L 9 = 8$ 9
$ 9 8 8$ # / K5 + L 4 " ) $ & n − 1 # 9 $ 9 ?9 @
K ?# @ 8 8$ 8L A (n − 1) 9 # 9 (k − 1) 9 / 9 n−1 k−1 A 8 & /
"# * n & & k
$ n−1 k−1
8 9 # J / J = &/ Q A 8 9 # & K
L # $ 8 $ 9 ) K 9 8$ 9 ) / )L A 8 & = ) 9 8 (8 & $ / J 9 n+k J = $ 9
) A )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< MJJJ GQ I? G
& $ ) &8 ) ? @ ) n & J & 8 k ) n + k & k n+k−1 k−1 &)) 9 / $ / 9 ! "# n & k n+k−1 k−1 $
&
.* !!>> '/2 n '*' k 8'8 / 8"@ / #) @ * ! !#! >K
F 2 ' n ) '*' k OA ! * 8'8 A / #) * > * !#! OA '% ' ! 8! ' '** *" .* !!>> /"@K
-% k ( >" * ' # @ ' )( !
"*! ')! #) @ p > " ." #) @ 8'+ '*#" /* > " #) 1# ) 88 #* & @ # '&/ p > ! 8 .* ! @88'( '*% /!K
" 3 8 9 # 8 9 0 /$ 9 8$ 9 8 ?/ @ 2 2 0 2 K L 10 11 $ $ 0 1 2 $ n n0 , n1 , . . . , nn ) 9 S 98 $ 9 )) / ) 8T
) ) & 2 K7-+5J7--+L & /D #&/ / 5 " 8 9 9 /
6 0
5 0
4 0
6 1
3 0
5 1
2 0
4 1
6 2
1 0
3 1
5 2
0 0
2 1
4 2
6 3
1 1
3 2
5 3
2 2
4 3
6 4
3 3
5 4
4 4
6 5
5 5
6 6
. 8 9 # 9 8 /$ 9 K L !
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< H G I? GM
7
7
7
#2 8'@!
4 n /*# '/% >'& !' '*# +#2 >"* n !!! @"@ # n/3
'"2 /
n 10
∼
n10 10!
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
#!!" 4#-""# * " / 7+ & K =
L & !
4) G
& ( " $ ( $ " 7 # ( " + " n ( $ 8" 9 & " *
( n 9 / 9#) 7 / $ 9 9#) $ ) 9 = 9#) 9 9#) & + $ 9#) ) 5 $ = +$ 5 9#) 9
3 9#) / 8 = 9 = $ 9 9#) : / / ) & 9 $ 9 &D 8 $ 9 9#) ) = 8 $ 9 9#) = $ =$ 9#)) F #! 9 / $ 9 9 = $ 9#)$ /
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A OJMIIJ O
9 9 9 ! 1, 1, 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 5 = 13 . . .
K3 #$ 9 ? @ ) & P /
/ $ 9 ? @ L 99 $ 9 D 8 ) &98$ Fn / n 9#) A n = 2, 3, 4 . . . & $ 9 Fn+1 = Fn + Fn−1 . K6 7L / /$ 9 F1 = 1$ F2 = 1$ F3 = 2$ F4 = 3$ 9 F5 = 5 F0 = 0$ K6 7L n = 1 K6 7L ) ) 9 #! 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, . . . .
& /# 7 " 8 " / 9 $ 9 K6 7L F0 = 0$ F1 = 1 9 F0 $ F1 $ K6 7L 9 D # 9 8 A 8! D # 8$ 9 9 $ 9 J ) / ) ) J $ Fn $ /) / $ 8$ 9 ) $ D # #$ :# 8 / D # / #
$ 9$ 9 # 7! ' ( ! G+'*# )2 # ! # /*#K F ) $ / &
( n ' $ +'(( ' " ( $ $ (' (* . n = 1$ 7 9 8 . n = 2$ 9 ! ) ) 8$ ) & )8 n = 3 9 5! 9 & )$ & / & $ & / & G/ $ / K. B# )) $ 9 n ) & 9 n$ ! 6 ) & # # ) :&)) 9 8 &! 1 + 1 + 1 + 1$ 2 + 1 + 1$ 1 + 2 + 1$ 1 + 1 + 2$ 2 + 2 L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A OJMIIJ?
9 )# / %8 9 Jn 8 &$ 9 Jk 1 ≤ k ≤ n 8T 8 & # ) 9 $ 9 Jn+1 . )8 ) & )8$ n ) & Jn &)) ) 9 8 &$ 9 )8
$ 9 n − 1 ) & Jn−1 &)) ) 9 8 & F 9 8$ Jn+1 = Jn + Jn−1 .
A / $ Fn / D # ) &8
A 9 Fn = Jn E ! $ 9 /$ 9 9 / F3 = 2$ J3 = 3 F /) $ 9 Fn Jn 7 ? =@ 9 ) ! Jn = Fn+1 .
F n = 1, 2 $ n $ F2 , F3 , F4 , . . . J1 , J2 , J3 , . . . / ) )8 / 9 @ / n )* 8(>!'@ 7) > *'/2 C )*! 2* )*! '@ .* !!>> 8/"@ >!'@K .* !'/#' ' {1, 2, . . . , n} /#' # # 8'8 ! '#'!) '*#K
# &8
9 / F ) / n E " / 9 ! 0 = 0, 0 + 1 = 1, 0 + 1 + 1 = 2, 0 + 1 + 1 + 2 = 4, 0 + 1 + 1 + 2 + 3 = 7, 0 + 1 + 1 + 2 + 3 + 5 = 12, 0 + 1 + 1 + 2 + 3 + 5 + 8 = 20, 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A G G
3 $ 8$ 9 ) 9 = $ 9 / # / )/ 8 9 ! F0 + F1 + F2 + . . . + Fn = Fn+2 − 1.
n / # / K / # $ 8$ / D # ? @L n = 0 n = 1 8T 8 & 9 $ 9 n−1 n F0 + F1 + . . . + Fn = (F0 + F1 + . . . + Fn−1 ) + Fn = (Fn+1 − 1) + Fn ,
/ D # ) ) )/$ 9 (Fn+1 − 1) + Fn = Fn+2 − 1.
A & 8 *#
! >*
6' &2 /
'"2 /
6' &2 8'( '*
)
F5n
F3n
n
'/% 5+
F1 + F3 + F5 + . . . + F2n−1 = F2n F0 − F1 + F2 − F3 + . . . − F2n−1 + F2n = F2n−1 − 1 F02 + F12 + F22 + . . . + Fn2 = Fn · Fn+1 Fn−1 Fn+1 − Fn2 = (−1)n
9"'@ G+'*# )O&%"* M& * N '' + @ )O&% ' Fn '*# & n+ ! , C 2'% 8'@+ ! * !! "2 & >!)*2 F−1 + F0 = F1 >"* ' >"2 / F−1 = 1 ' F−2 +F−1 = F0 8'@!( >) 8'/+ @ / F−2 = −1 . ' 2 & )B? G+'*# >'& )B?/'K '*#&2 !/* "@ # / *' '* ' &2 " / /
!
K6 +L n 8 9 $ 9
$
/ . 9
$ E ! 9 / # )# / K / 9 2 Fn2 + Fn−1 = F2n−1 .
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A OJMIIJ?
8L$ #$ 9 /# &8
A 9 / 9 $ 9 8 F2n &8
$ / / ( K EL 8 9 $ 9 Fn+1 Fn + Fn Fn−1 = F2n . K6 5L n # 9 9 &9 / K6 7L /# &8
! Fn+1 Fn + Fn Fn−1 = (Fn + Fn−1 )Fn + (Fn−1 + Fn−2 )Fn−1 = 2 + (Fn Fn−1 + Fn−1 Fn−2 ) = = Fn2 + Fn−1 = F2n−1 + F2n−2 = F2n .
K / # ) K6 +L &8
$ ) / # & / L K6 +L
9 # ! 2 2 Fn2 + Fn−1 = (Fn−1 + Fn−2 )2 + Fn−1 = 2 2 2 = (Fn−1 + Fn−2 ) + 2Fn−1 Fn−2 + Fn−1 = 2 2 = Fn−1 + Fn−2 + Fn−1 (Fn−2 + Fn−1 ) + Fn−1 Fn−2 = 2 2 + Fn Fn−1 + Fn−1 Fn−2 = = Fn−1 + Fn−2 = F2n−3 + F2n−2 = F2n−1 .
K / # ) K6 +L &8
$ ) = / # & / L G/ ) Q F& E K6 5L
&9 / K6 +L
$ K6 +L
K6 5L Q 3 ) $ /) # #$ 9 / # ) 9/ 9 . / /$ 9 n K6 5L$ K6 +L $ 9 / K6 +L n K 9 /$ 9 ) # n 9 /$ / # & &9 / K6 5L
L A & $ / # 9 /$ 8 '"2 / >* )B? G+'*# >* )B? " O # &@ / 8'( 2'% *&/"2 ( F2n+1 = 3F2n−1 − F2n−3 .
)"2 # &!! , ! , L '* '#2* !@ ' &**
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A G G
8"@ 3+/*#'8 * ( #! ' ' C+ .)"2 !>! #") !>! !' ! " ''@ # '*#/' "22 G 2 ' )) #& # "22 /*#'8+ ( #") )"2 8' ' 22 * " ' '*# 7 '*# >"2 / /*#'8 @88'( "!( )2+ 2K F( >%*"2 #" #)* '* ' &2 R"2 )#! @ #* @/% &!! 8 &$ 9 & & ) A =8 / $ 9#) K ) / L ) B − A $ =8 $
B 1 / ) $ 9#) A + B $ 9 9#) A + 2B / $ . / n 9#) E F E0 , E1 , E2 . . . /$ E0 = A E1 = B $ ) & En+1 = En + En−1 &8
K / ) # $ /) /#
L AM ? # @ A B D 9 / F 8 ? @ #E A B 88 /E 9 = ! En 9 & 9 / Fn A / En 9 K A B ) ) & L!
E0 = A, E1 = B, E2 = A + B, E3 = B + (A + B) = A + 2B, E4 = (A + B) + (A + 2B) = 2A + 3B, E5 = (A + 2B) + (2A + 3B) = 3A + 5B, E6 = (2A + 3B) + (3A + 5B) = 5A + 8B, E7 = (3A + 5B) + (5A + 8B) = 8A + 13B . . .
( $ 9 9 ! En A B $ 8 9 # ) 8 9 ! En = Fn−1 A + Fn B. K6 6L ) & J K / #L $ 9 B# 9 / K6 5 7, & L
/ ) $ / ! A = Fa B = Fa+1 A En $ P 9 Fa+b+1 = Fa+1 Fb+1 + Fa Fb . K6 :L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A OJMIIJ?
1 2 2 4
3
3
4
1
8·8 = 64
5·13 = 65
6 7 $ 9 64 = 65
$ ) /
9 / K9 & /L 6' &2 , ! , L '* , 5 >"* , 5 '* &!! *2 , C ! , ) 8+ '( **&** / n k '*# 8'88 Fn ' Fk 8'88 $*"2 ! !' ** ! "2 5 × 13 #'(( *% !> , C ** $" ' 8' ( / 5 · 13 = 82 K . 2 #K 7 8' G+'*#/'K
4#-""#3 F E " ) $ n &8
Fn E R K $ L
#" Fn 0 !!$ &
1 Fn = √ 5
√ n √ n 1+ 5 1− 5 . − 2 2
( 9 8$ 9 n = 0, 1 8$ n / # 8
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A < OJMIIJ?
6' &2 n ' )2% ' '* B# )
9 ) " 9 8 $ ! 9 8 E F& 99 ) 9E F 8 9 9 $ 9 K $ # L / D ## K 8 )9 9 #L *) ) )/E 8 9 6 5 7 $ )# / ? ) 8@ Fn ) 9 = )# 9 J ) E ()/ # )8 $ 9 / 9 !
1 1 8 5 34 21 144 89
3 5 = 1.5, = 1, 666666667, 2 3 13 21 = 1, 600000000, = 1, 625000000, = 1, 615384615, 8 13 55 89 = 1, 619047619, = 1, 617647059, = 1, 618181818, 34 55 233 377 = 1, 617977528, = 1, 618055556, = 1, 618025751. 144 233 = 1,
2 = 2, 1
S $ 9 9 K 9 # L 1, 6189 A / $ 9 ) # K 9 / L " / 9 $ $ D # /# &8
" 9 Gn = c · qn K9 c, q = 0L A Gn+1 = Gn + Gn−1
&8
c · q n+1 = c · q n + c · q n−1 ,
)/$ ! q 2 = q + 1.
F c$ n ½ c +2 ( n & T#+2 # &) 2 # *!8 & # 6$: # 2 &+ ( /&: # +8 # 2/8/? ( 1 &:# & &+$; O "/# DD ?.+& 8 68( B2 '22( .%$$+2 1 /8 ## 2/8/( # * & ##: $)! 6$: # (( & * &B2 2(! & $2(/8/(* 2( # +# $: -)B0 2/8/( / 46# 2( 8 # c?8 */# /(B # 2 .+& #./8!D B8 # 2(!; 3 6# ( # . &%&1 3 $: 2/8/( & &+$; 2(B" # ./8$B 8 68( B 1 /8 2/8/( &2, * & 3!#: $)! &3 $:* 6$: #D2 -)B0 2/8/( / 46# 1 ;$: ( !# n?8 */# /(B # 2 2(!; 3 6# 2 .+& $2(/8; !28
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A OJMIIJ?
) & = ! √ 1+ 5 ≈ 1, 618034, q1 = 2
√ 1− 5 q2 = ≈ −0, 618034. 2
A 9 8 9 = $ D # /# & K c 9 L!
Gn = c
√ n 1+ 5 , 2
Gn = c
√ n 1− 5 2
Gn $ Gn ! 99 / $ 9 G0 = G0 = c$ 9 F0 = 0 ' 8 $ 9 /# & Gn − Gn ! Gn+1 − Gn+1 = (Gn + Gn−1 ) − (Gn + Gn−1 ) = (Gn − Gn ) + (Gn−1 − Gn−1 )
K(9 /$ 9 Gn Gn /# L A F0 √ √ $ 9 G0 −G0 = 0 G1 −G1 = c 5 A c = 1/ 5 9 9 9 / F1 = 1 Fn Gn − Gn $ / /# &8
Fn Gn − Gn 9 / / $ 9 K # L ! Fn = Gn − Gn Gn Gn ) 9 )) 6 5 7 ) & / )/ () 8 =
9 9 √ ) q1 = (1 + 5)/2 ≈ 1, 618034 > 1$ ) & $ 9 −1 < q2 < 1 n $ Gn $ Kn ≥ 2 L |Gn | < 12 $ n Gn A 1 Fn ≈ Gn = √ 5
√ n 1+ 5 , 2
$ 9 n ≥ 2 $ 12 $ ,9 $ n 9 A $ 9 Fn Gn 9 √ τ = (1 + 5)/2 # ! $ ) &/ R 9 ) / # 9 9 / )) ! 9 b/a = τ $ (a + b)/b = τ . 9 ) τ $ )#
9 9 # ) )/
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A < OJMIIJ?
:O*"2 >'& !' '*#% *% Ln ' 8'( 2+ '% L1 = 1 L2 = 3 ! Ln+1 = Ln +Ln−1 F' '*# $" % ' 6' &2 / ' Ln '*# &/% a · q1n + b · q2n / q1 ! q2 ' &* '>( '*# ! /*''2 # a+ ! b+
:O*"2 ' In ' & I0 = 0 I1 = 1 ! In+1 = 4In + In−1 @ #2 >!#* # ' In '*# )"* #)** @ !> In +
) ' *&" / # G+'*# #* !> / e = 2, 718281828 . . . #!' #2 >" ' K
Fn = en/2−1 n = 1, 2, . . .
(
# ) *
.* !!>> /2
2×n
#!? M**N )#%K
.* !'/#' {1, 2, . . . , n} /#' # # 8'8 ! #* 2* 8'( '*# / + ! n+ #* 2* + "@K
.* !'/#' {1, 2, . . . , n} /#' # # 8'8 /*# #* 2* 8'( '*#K @ 2'% !>
7 '*# 2100
F100
K
6' &2 ' * '* F2 + F4 + F6 + . . . + F2n = F2n+1 − 1Q 2 F n+1 − Fn2 = Fn−1 Fn+2 Q n 0 F0 + n1 F1 + n2 F2 + . . . + nnFn = F2n Q ) n0 F1 + n1 F2 + n2 F3 + . . . + nn Fn+1 = F2n+1
'"2 , , 8'@!
'+ / / Fn >&#'*# n 'K
9@ ' b0 , b1 , b2 . . . '*#' # b0 = 0 b1 = 1 '*# >)
b2 , b 3 . . .
bk+1 = 3bk − 2bk−1 .
2'% )"2 # .*''2 # bk !!!
9 @ / (a0 , a1 , a2 , . . . ) ' !& an+1 = an + 2an−1 .
2'% 8'@! 92)"2 /
a0 = 4
! a2 = 13 7 a5 K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A OJMIIJ?
'"2 / , L ) )O* Ln 42+'*# * 8'( '* F2n = Fn Ln Q 2Fk+n = Fk Ln + Fn Lk Q 2Lk+n = 5Fk Fn + Lk Ln Q ) L4k = L22k − 2Q L4k+2 = L22k+1 + 2
'"2 / / n '/% ,+ Fn '/% L+#
'"2 / #) >'& !' '*# &/% @88'( G+ +'*# 8'! '"2 / ' ( *&** 8 ' #) >'& !' '*# &/% @88'( G+'*# 8'! # " 8'8 ! #* 2* 8'( G+'*# 6' &2 / ' + &* # !#? + ' #* '
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
$ %& 5 . / $ 6 # ) # & 8 A /$ 9 # J )& J 8 B# 0/) 9 # / 8 &
/ / # / &
= J J / A99 9 # 8 #$ 9 # . D 8$ 8$ =T / $ & # 9 # )$ 9 J J 8 D K 8 8 L 9 9 J S J 9 )& $ 9 ! F K&L$ I K LT 9 S = {F, I} F )) $ S = {1, 2, 3, 4, 5, 6} 9 A & 8$ 9 9 S = {s1 , s2 , . . . , sk } 9 S 9 8 S 9 9 8T 9 $ 9 K D L # & # 9 ) / E = {2, 4, 6} ⊆ ⊆ S $ $ 9 ) / . #! L = {4, 5, 6} ⊆ S 9 & $ 9 5 /
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E MJ J F NX G
9 8 & T L ∩ E = {4, 6} 9 ) / & $ 9 / 5 ) A B 8$ 9 9 $ 9 A ∩ B = ∅ O = {1, 3, 5} K) /L E ) / ! E ∩ O = ∅ 7 #! # ! #! 2%"K " 9 S = {s1 , s2 , . . . , sk } 9 9 S 9 $ #) $ $ 9 & 8$ 9 si ∈ S P(si ) ?# @$ 9 = $ 9 # # 8 ! KL P(si ) ≥ 0 si ∈ S $ 9 KL P(s1 ) + P(s2 ) + . . . + P(sk ) = 1 . & 8$ S 9 P #
# 8 A ) & ) / P(F ) = P(I) = 12 . # # $ )#$ P(i) = 16 i # $ / # $ ' # 8 # /& # & /$ / )$ / # / 9 # 9 / B# D $ 9 / & K / & L # 8 8 9 . ) / /$ 9 ) $ 8 S = {, } 9 $ S ) # A A ⊆ S # A # 8T A # P(A) C& # P(A) =
|A| |A| = . |S| k
'"2 / #! %'&?! # / # C
7 %'&?! ' E >* '*# )2 T /*## '/% '*# )2 #! K
6' &2 / '*%
'"2 / '( A ! B #! !
= P(A ∪ B)
A
!
B
#! !
= {3, 6}
P(A) + P(B) =
P(A ∩ B) + P(A ∪ B) = P(A) + P(B).
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E N OGG GJ
7 * # 1 8 n . ? @ 8$ 9 S 9 ) n 9 =
= T 9 S n $ S n 9 ? @ . S 9 k $ kn F & # 8$ /& # / . 9 (a1 , a2 , . . . , an ) ? @ 9 $ P(a1 , a2 , . . . , an ) =
1 . kn
8 $ / & ) A S = {F, I} K&$ L$ ) S 2 = {F F, F I, IF, II} 9 9 # 14 OD # 9 $ # &8
8$ 9 ?&8
@ # 9 /$ ? 9 & 9 & @ A98 8 & & D #D ) $ / D # $ J ) ) J ) 9 /$ 9 ) & & & # ) ) ' " & 1 / ! &8
$ 9 ) & # K 8$ 9 $ L & # & D #! A B ' 9 P(A ∩ B) = P(A) · P(B) 8 & " A $ 9 $ B ) $ 9 & A P(A) = = P(HH) + P(HT ) = 14 + 14 = 12 $ 9 #! P(B) = 12 $ &8 ) P(A ∩ B) = P(HH) = 14 = 12 · 12 A B 9 &8
K9 /L F ) $ / ) " F $ 9 & $ K ) $ 9 9 /T F # 12 $ K # ) 13 H ∩ K $ & $ ) : - / T H ∩ K # 16 $ 7+ 9 KF 1, F 2, F 3, F 4, F 5, F 6, I1, I2, I3, I4, I5, I6L 8 / + & & A 9 P(H ∩ K) =
1 1 1 = · = P(H) · P(E), 6 2 3
/ $ 9 F K &8
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E MJ J F NX G
&8
& $ & 8 $ 9 & D ) 8 ) / E = {2, 4, 6} T = {3, 6} K) /$ 5 9 # /LT E T &8
$ 9 E ∩ T = {6} K5 9 # ) &)) 9 /L$ P(E ∩ T ) =
1 1 1 = · = P(E) · P(T ). 6 2 3
' E, O, T, L #! 8'@ # @ #! >*K 7 '*% #! >*K
'"2 / ' ∅ #! #) #* #! ( @ $+ #* #! # )' '' 2")*K
4 &! #! S Q #!"@ # &! n+' / 4 s ∈ S 4 A M N &! ' #! # 8+ ' / ' ( &!! B >) ' ' #! / ' 2% &!! s 8' 722 # / A ! B @ #!
n≥2
7 ) ' ;% /* # ! G8)8 '@!>" ' " '@!>"*K [ 2 ' > '@ # ' " ' >" ! /*'*K
. /. A & & /$ K # &8
8L n / & ) & 8$ 9 n ) $ m n = 2m n 9 =
= $ F $ I n = 20 ) / F F IIIF IF IIF IF F F F IF II
)/ $ 9 9 / & $ & 88 / $ . 9 ) & E ! & /9 $ 9 K ))
L /$ J / J / & 3 9 /$ 9 / $ &$ /) $ 9 / # =
4 $ #) n" '$ ' ; 0$ 9 8 b ÷ a $ r $ 0 ≤ r < a . 9 q$ & $ 9 b = aq + r.
9$ 9 8 8 B# & 9 & & 9 $ 9 )O&% >"* '"2 / 1 | a −1 | a a | a ! −a | a *# a !' '*# !
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
H N
4 a !' '*# . #)"2 #* '% ' / 2 aQ 0 | a
)
2 | a
Q
6' &2 / / a | b ! b | c a | cQ / a | b ! a | c a | b + c ! a | b − cQ / a, b > 0 ! a | b a ≤ bQ / a | b ! b | a a = b a = −b
4 r b ÷ a '* #)!Q @ / # / c | r
c|a
! c | b 722
9 @ / a | b ! / a, b > 0 4 r c ÷ a '* s >) '* #)! )"2 # ' s ÷ a '* #)!*
c÷b
'"2 / #) a !' '*# ! a − 1 | a2 − 1 ! / ! 8 ' #) a !' '*# ! n >'& !' '*# !
a − 1 | an − 1.
A p > 1 (# 8$ 9 #$ 1$ −1$
p −p F ))! p > 1 ) $ 9 9 # & ) n > 1 $
) $ 8 K 7 / ) $ L 2, 3, 5, 7, 11 9 ) $ 4 = 2 · 2$ 6 = 2 · 3$ 8 = 2 · 4$ 9 = 3 · 3$ 10 = 2 · 5 - 7 :,, ) / 9 / ) # # & & ) 9 $ ) & F / ) /$ 9 ) K3 /) / ! QL )
$ J - 7 / J ?/@ & / F 9 ?/@E " ) E 8 & J ) 8 $ ) 8 Q ) # ) 9# = )/ / . 9 8 n ) #$ 9 ) E ) = ) 9 / K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
H G 1 N
1 1 1 A1 1 H1 1 K1 V1 @1 1 1 1 A1 E1 H1 1 K1 1 @1 1 1 1 A1 E1 H1 W1 K1 1 "
4!'+ * # > '*# 2, 2, 3, 3, 4, 4, 5K
Q
0, 2, 2, 2, 4, 4, 6
"'"2 * # &'#2* % # #*+ #2 #" ! &'#2 #" 8'8 !# 8! **'"
F > / D OA ! P * #2 #) OA * #* ' 8' * "'"2 ** .* ! *K )"2 # > '*#*
.* !'*" ,+8K
6' &2 /
G
! G 8'@ * ' ' 8'@(
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
W GO
4 G 8'@( * # * ! >" + '"2 / * >" # ! /''* >%)% 8' ! ' *&* 2* ##)% * 8'@(
4 G 8'@( * # # A '"2 / *+ /*# >" / ' 8'@ *# *& * 8'@( #)
4 G * # *# ! ! 8'8 !>" '"2 / G " *
F '* (m − 1)n + 1 # %') '"2 / '* m # 888 # #* * n #* #
6' &2 D L C 9! !'!
D L C 9! 8'@( * ' 7 # 8'@( *+ F2+!K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
# & / >"#$ & & ) # 8 $ ) & 8 8 G = (V, E) & ' 8$ &8
& ) # # 8 & & $ )
'"2 / *# ! >" 8'8 > A ' 7)& ' &2 / / G * *# ! >" 8'8 >+ A ' *
& . / * ? & & /
% & # - &$
" 9 G &$ ) 2 /$ 9 G 7 & = ) $ ) $ 9 $ B# 9 / KA = ) ) $ 9 9 L 1 // & v0 ) #$ 8 & A ) # 8 $ 8$ 9 8$ 8 7 & = ) . ) 8$ 9 / J / F/ / 9 $ 9 / # . $ 8 ) $ $ $ ) J G & J 9
)# ##!!! '"2 / C '*#A >"
G
+ * #!
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
K O
& = =
F / /$ 9 # && ? 9 8@ # #!
F @ ( F 0 $% G ' ( $ ' & ( G $ ( $
&
' # ( & & $ & " "
= / $ /$ 9 & /
/ & # # ' / 9 & $ & ) ) / F /# & &$ $ 9 9 )/ & $ &$ 9 G &$ G ) &$ = )/$ 9 = v ) 8 G u ) $ G & A #! G &8
$ ? @ ) 9 $ v ) ) w ) 9 vu u# w = ) A &8 G 9 ! v ) & 7$ 9 9 $ $ v $ G & 9 9 $ # & 8$ 9 & F ! / / $ 9 & / 9 # & ) / # / . & ) $ & # J ) J 8 &$ 9 G & ) A " * "8 * v > F > #) *A ) / #* * 722 # / /# ' > # #) ! > *A %') )"2 # >"* T L 9! A" ' &**
. * 88"@ v >"* ' ' ! @ # ') * >2 # #) 8'@( #> F' #> ' ) v > ''@ 6' &2 / *# * > / ' )2% * 8'@ 8 >" # >" '*#*
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
K O
& . ! * ? & / $ 9 ) ) $ 9 & 8 ! n (& ' * F )# $ & ! 8 & 8E & 9 $ 9 / ' 8 8 ) / n !2 & nn−2 ) $ 9 / Q 9 $ ) 0 $ ) $ / # F /$ A 9 / / ! 9 9 # & E
& . ! * ? 8 &$ 9 & J / %) >"* / &#!' * '*# " nn−1 => F 8 # J 5'" J$ n ) = & n − 2 = K , n − 1 L 9 / $ ! & / $ 9 9 9 9 8 & A K #$ L & 8 n ) = & n − 2 = $ 0, . . . , n − 1 F ))
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
K O
nn−2 $
& = 0 / 8&# K L ) )# ?D / @ 9 8 , & $ ) ) = 8$ 9 ?D=@ $ K ) L ))$ & ) 9 8 S 8 9 $ ) & $ , # ) ) &$ ) ) # $ 9 9 8 R = ! 8 , # 8 7 & = ) 8 $ 8 $ ) ) A 8 9 ) 16 A/ 8 # & # ) $ 8 & ! 8 7 & = ) $ 8 $ T / ) ) 30 F 9 / ) $ & 8 8 & /$ 8 ) & $# 5'" 8 K 8 ? @$ J & / J ?# @ 8&# L ) G ! 6' &2 / M*% !N / # ' /''* G 8!/' #
'"2 / #> /
n
e
>+
>A ! m !? * * n − m 8'@(
'2 / / * d '*#A > * *
d
.* P >A &#!' !'K
'
" ''@ ' * # > ! >" # # ! .* &#!' n >A ( !'K
2*"2 * n − 3 /'A*A A% A / '@ ! A" > ! ' 8'8"@ ' A 2 ' !>"* .* @88'( &#!' * >/2 #%)K
9@ % ! n − 1 '>% *% **'Q ' ( #*) # >) '( C ! n 8'8 '*# !'&@ ' * # ! **' '> >" 8'8 /)
1, 2, 3, . . . , n − 1
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
K O
3!) &!! '"2 / ' & > * # !@ 6' &2 / / ' & > * 8'@( 722 # / * #) 8'@( #>! * 8
6' &2 / * *# ! # # A 8'8 >" & '' # (&/( 2 ' *&* # '
. e
F
. k+ ! l+>A " * ! 8'8@ (k, l) #*%
8 ! # '#'!) A* 8'8( ! e+ C 8 G * L+* '*#A >" G+ 8 # * /A VW#2* 8@ ! ' &** # ' #) * C '*#A >" X C
#( ''@ '"2 / /
n
>A 8 8@ 8' ! M#*)'#'!)N > .*
) )( ' & > *K
) >2 .* '&( *" A '%*K
6' &2 / / n ≥ 2 T 5 C 9! '>( #)! (! 'A
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
+( 9 -- * ()8
$ n
& $ 9 # 8 # 9 & # 9 9 !
& ' 9 = $ 9 9 ) 9 #$ ) 8 K /$ #9 $ 9 $ & / ! ) $ 9 9 # &8
L 9 &8
& $ & ) F / /$ 9 & $ n − 1 & 8 ' $ 9 & E 3 $ J ) / ) J 8 9 . #$ 9 $ & 8$ & 9 & $ K 9 # L O 9 / /$ 9 E A )
$ ) / $ 8 A ) & ! 8 & $ / & $ / & $ ) / ' $ & & / 9 ! 0 K& ! / ) = & $ # & & $ # & & ) # =
4!'+ 8) A E L ** */%*K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
O V JJ G
'"2M / / #) ! 8! * ' ! /'* 8) 8A # #'/ #*
(
# ) * 6' &2 / / ' !/' ) 8! #) @88'( > % !'
)"2 #%)' '&( * #!! # ! ' ! 8! '' #B#* !8! ##*
%) #* ! ' ># ! >'# !'(> #"%+ / #%) *' / ' ) @ / #* #* & !/ % !>& # # # 8 #* #!( #* ' M/N #(& )** #& # "2 /' # ' 8'@(! #* !@ # ! '/ / ! ' # !>& '"2 / ' M)'%N @? #* /! % /*%' !>& #
. #* ' r * '! /( ' r+ 8 * 8'8( %* ') /*%'!>&! 4 ' #)"2 ' rs ! F'2* % 8' # r+ s+ #* * 8 8' ! & * # /* ) ' r (* #'% 8'@( * * /#'* S !'/#'* 8'( !>! % #!>&! # S # >"* S + &@ > 8 8' '"2 / '' #%)' % * >"2
@ # 8) 82 3 × 3+Q 4 × 4+Q ' +8 ! '* ) 0*&2 ' )#! n × m+ *
5×5
722 # >!)* / / # 8"@ # /*#'8+ (! "@!! M*%N^ #2 > 8A 8! * ' >#* 8A 8!! C+' /
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
% ; 5 . " # - A 5,, & 8 $ / /$ 9 :, D= $ D= :, K $ & 8$ 9 L B $ ( & ( F #$ / # # & & 9 / K )9 8
& L N / 9 5,, ) $ 8 $ ) A 8 & ! $ 9 D= $ ) ) # 8 $ # 8 & ) 9 8 = $ 9 D= & ) $ ) # ) 9 $ 9 & ) ) 9 A$ B ) ) & ( ' 8T ) J ) # = ) ) # J & 7, 7 / 9 / T (# 8 / & ) D # A & ( 9 ) J / A B J 9 9 # = $ 9 & A B ) & E 9 (# 8$ 9 & ) ) E K ) '& ' L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ N
7, 7 & ) F 8 / & )) & 9 / & ! /$ 9 9 5,, ) = )
& ) & :,$ & ) F & / $ # $ 9 ) = & / = $ 9 & 8! 5,,$ :, & ) & $ 9 ) / K ,L & / 9 $ 9 / $ ( O # K( & ## L
* & & & 2 $ 9 / 9 & $ J & J ) / 1 *% / >* * !'/ " >*&* / |A| = |B| '"2 / / > '*# # ' ' '@+ ! ! 2#2 "@
722 # >!)* &!! / ! '>( ! # / /% '' # >* * #! # !' !@ " >*&* / #) > '*# 2 'Q >* * " >*&* !'!!/' # )( / #) > '*# >'& ) # #) !@ (
6' &2 C C C 9! d = 1 ! d = 2
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ G GQ N
7, + 9 8 9 & 9 $ 2$ 0$ O$ A $ & 7$ +$ 5$ 6$ :$ -$ 9 & $ 9 # 9
; @ . A 9 9 # ) ) $ 8 ) 7,, 8 -,, / )
) $ 9 - & $ 8 8 F $ 9 $ 8 & / / /$ 9 9 & 7,, 8 $ 8 & 9 ) K 9 &L 9 8 K7, +
L & ! / $ 9 9 ) & & 89 . ) / 8 $ 9 & 9 / $ 9 9 J / J & +,, 8 A & /9 $ 9 8 & $ 9 8
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ N
1/ / ) M & ) ) $ ) ) ) ) $ 9 & 9 8 K29 # $ 9 & / L ) $ ) ) #$ 9 ) & )/ K7, 5 L P / E )! $ 9 & ) Q A
1
B
2
C
3
D
4
E
5
F
6
7, 5 & ) 9 9 # & & K QL & 9 ! /$ 9 & ) 7, 7 7 99 $ 9 & ) / & A =
& $ ) 8 K B +$ D 6 ) 8 9 L F & 9 9 ) E # & ! ) E 3 ) /$ 9 8 A $ 9 & , & = ) A & $ ) K #L$ 9 8 & $ / 8 A & +,, 8 & $ & A& /9 $ 9 9 8 & E 3 ! / & / 5,, 8
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ <
& $ 9 7,, A ! k 8 8 k & & & ! ) 8 k / $ k ) $ # & # )
; F / / ) # ## ) A K L # $ $ $ ) K / L
" =A% )> & $
2 |A| = |B| + . A A " B k # A
# #
k
$ 88 9 & / / A # &8
8 H /$ ( O$ 8 . & & 8 / . ?@ ? @ & 8$ ) ) O 9 K8 L & E ( 9 #$ 9 & K /L 9 /$ 9 9 B / k ) #
# S 9 $ S ) k A ) " n = |A| = |B|T 8 S ) A ) & $ ) &9 K7, 6 L &9 ) & n − k ) 9 K S ) L F & ?# @ 8$ &9 ) & n − k$ & ) & k 9 J & 9 ? # @ 8
N 8 7, 5 7 & & ?#@ & 8 A ) & 9 ?#@$ 9 / ) $ k ) k ) 3 #$ 9 & ?#@$ ) $ / 9 & ! ?#@ & ) . & ) $ ?#
@ $ 9 ) A & & ) $ 9 + ) = ?#@ & # # ( # K ) # $ 9 & ) / 9 /$ & / $ / 9 ) L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ N
n-k
k
7, 6 . & # ?#@$ # ! & ?#@ /$ / # / / ?#@ ) #9 $ 9 A99 /$ 9 >" (& 8 9 ( ' $ 8 9 ( ' ( # # 9 8 ) #! / a ∈ A b ∈ B ) $ T ) # 9 {a, b}$ ) ) # # 9 88 ?#@ & 8! / 9 $ k ) # # S 9 $ k ) K7, : L & S ) k ) $ ) = 9 $ 9 k ) b % T S ) K &L ) 9 3 8$ 9 |S| = = |T | # / ) #! S ∪ T K 8 9 # L$ ) K L ) K / # 8$ a ) ) / L 2 /$ 9 & ?#@ ( 8 8 ) / S K & L ) j 9 F & ?#@$ 9 ) j )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ A GQ G N Z a
b
k-1 k
7, : ( ) ?#@ D 8 $ T KT D # L & 9 # # 9 #$ 9 ?#@$ ?@ ? @ & 8 A # / 7, 7 7 A 9 ) $ B# / K7, 5 7 & L 6' &2 / / >* * #) > '*# ' * M"%N ! & !' " >*&*
9 @ / >* * ' A /#' #) X !'/#'*+ /' !' * |X| > B /#' # X # 8' 8 C L C 9! ! ' # # 8"@ # / + *" |A| = |B| '"2 / *'/% * !( /#' # # A #) >"* 8'8 B >"* ()2/ / B !# # M>*N #)
; . $ ? N 8 9 ) & '
9 8E ! 9 8 ) & $ # # 8 9 ) E P 9 $ 9 *
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ N
A $ 8 |A| = |B| & K9 $ $ $ B ) 9 L A $ 9 8$ ) F )# 9 / $ 9 / 9 $ 9 ) $ / A ) J $ 9 9 ) ) & 5,, ) $ |A| = |B| = 150T & :,$ 150·50 = 7500T 9 27500 > 102257 9 $ ) Q ' /$ 9 9 9
/ A B 9 9 ) $ 8$ $ ) A 8 ? /) @ 150! ≈ 10263 ) J Q 9 / 7, 5 7 E ) 8 & 8 9 A S 9 ) /$ 9 S B 9 $ S A 9 2150 ≈ 1045 9 J / $ $ 7, 5 7 9 8 8 $ 9 8! & ) ) / /$ 9 /
& # ) K L 8 A ) A ) $ 9 8 (# & ! ) 8 9 $ ) ) ) $ & ) & K ) & ) L A ) ) 9 ! 8 9 # 9 ) # / ) / = $ 9 8 9 # / ) 8 & ( / ) $ $ 8 A/ = $ ) / )$ ) /$ 8 M ) $ (# $ 9#$ D 8 9 # # / . $ 9# ) $ O 9 $ 9 M E ( 9 8 $ 9 & ) E 3 ! 9 $ 9 & ) $ 9# # )"2 >!)* * # " >*&* ) / '! #/% #%)' ' # *" # A
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ A GQ G N Z
'"2 / / G * " >*&* *# #/% >*&* ) G >" * !
u
v
7, - % # = ) & M ) $ P # = M
8 & 9 $ 9 / & $ A & )# / $ 9 = $ 9 9 / 9 $ )# / O 9 / E & / B P / 8 G$ 8 ! P ) u v ) $ M ) & $ M K7, - L / $# & 8 3 #$ 9 P # = ) = 9 $ 9
M ) $ M . / P # / $ M ) # 9 9 / P $ 9 8 P = M 8 ) M ) #
$ M K $ 9 M ) $ # $ 9 M 8 P ! P ) & $ )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ N
) $ M $ 9 / L 9 9 8$ ) 9 $ M ) 9 / /$ 9 # = r? U
W
S s
T
q
r?
7, ; P # / 0 = M 8 8 & ( 8 &! KL 9 / # / K LE KL 9 # = $ $ 9 ) E ( 8$ 9 ) 9 / K 9 L %8 U A$ W ) B 9 ) ) A 8 # = ) = ) 9 $ U ) W # / / $ U ) # / F / $ 9 Q = #$ 9 U ) # /$ A ) $ M # / ) ) 9 $ ) / ) M 9 B A ) 8$ # = 9 A 8 $ 9 U ) K, 9 =
=L # / 8T U ) /
S = U 9 # /$ S 9 ) / S 9 ) ) # &
$ / /$ 9 # = 9 %8 T S 9 ) B ) 9 K7, ; L F U ?) @$ 8 S $ )/$ 9 |S| = |T | + |U |.
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ A GQ G N Z
B 8$ s ∈ S ) r ∈ B ) $ T " Q # = $ u ∈ U ) # s 9 ( /! J . r ) K W L$ Q = 9 sr 9 P # / )/ A M 9 8 KS T ) & 9 8L J . r ) q ∈ A ) $ sr rq Q9 # / )/ U # q A q 9 9 8 S 9 . 9 / $ S ) T ) ) $ M / / $ KM / 9 L S 9 A / # 9 ! M ) K /L$ M / $ $ S ) T 8 ) F 9 8 / # E Q . $ ) '#! S 9 ) T |T | = |S| − |U | < |S|$ $ 9 & ) 7, " / * / #) ) / ') K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ A GQ G N Z
7, 4 H &$ / )# 9 # 4 G >* * # ! )* 2 > 9 @ / ) > *# #@ A !'/#'* |A| + 1 '#'!)" " ) '"2 / G *# ! !'&/( " >*&**
9 @ / G * ) >" *# #@ A !'+ /#'* 2>* |A| − 1 '#'!)" " ) '"2 / G+ !' >*&* # + ! ! ) # >+ "* )
4 G >* * # #)! )* m > 6+ ' &2 / / #) > '*# # m/2 * " >*&*
$+ " >*&* C C ** */% *K
7, 7,
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ N
"'"2 * # >" ' {a, b, c} /#' !'/+ #' ! # ' > ! 8'8 # > # ! #*% .* >" ! /* ! *K 92)"2+ !K ='@(+ ' *K $+ " >*&*K [ .#+8K
"'"2 ' * # >" ' {a, b, c, d, e} /#' !+ #? !'/#' ! # ! > > ! 8'8 / 8'8 #@ 722 # / 3+* >2 D CL * .* " >*&* )/% # 3+*K
.* " >*&* !' n >A AK .* # !@ " >*&* !' n >A AK V @ 2'% 8'+ @! X .* >*&* n >A 8K
7 +2* n >A >* * 8 " >*&*K
.* " >*&* 2n >A !* C CC * K
... ... 7, 77 &
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
( $ # ) 9 ! 9 E ) $ / # 9 # $ & & /$ & # 9 & / 8 n = = * Kn L KA *$ $ 180◦ L 8 &$ 9 9 # / ) . ) #E K = 8 # ) $ 9 # 8 ) 77 7 ) ?#@$ 8 D 8 9 ) L
77 7 $ # & 8 ! / # ) $ / (8 # * 9 K77 + L 8 # $ 9 ?
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ MJ J G J
@ = $ / A C AC # B /# # $ 5 ) F -
# $ 6 · 3 = 18 ) 9 / C
C
D E
B
A
F
C
D E
B
A
F
D E
B
A
F
77 + ' / # $ 9 ) $ / A D # 9 #$ 9 # ) F 5 # $ 3·4 = 12 ) / . $ # 18 + 12 = 30E ^ 8Q AC BD # ) /! AC $ BD # ) C ) ) ! 8 9 / +$ K 9L 9 7: K ) / 9 /L # n 9 /$ / 9 =
/ $ n K)# / L ) 9 9 / %8 # ) # ) R ) / AC BD # ) ABCD $ AD CE # ) ACDE $ ' # E ! 8$ 9 8 ) 8 ? @ )E #! A, B, C, D / ABCD * KAC BDL
# ) 9 9 / A &8 6 = ) # ) $ ACEF ) / AE CF # K77 5 L # ) 9 = 6
# 9 . ) / n = 6$ 4 $ 6 6 6·5
9 /$ 9 & 8$ 9 4 = 2 = 2·1 = 15 G ! * n # n4 )
.* *%" B n+'8K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
Q
ABEF
A B
F
C E D ACDE
77 5
+ . N / n . E 8 $ 9 9 &8
( ) 9/ ) / 5 $ 9 $ 6 )/ N ! 8 &$ 9 ) 9/ A + 6 )/ . 5 8 $ # &8
)/ -$ ; $ 9
) $ K77 6 L 4 1 2 3
1
6 3
2
5
5 4
1
3 2
6 1
7 2
4 3
77 6 N ! 8 &$ 9 8 9 / ) B# # 9 $ 9 6 = & 8 8$ 9 / 6 $ ) 9/ 9 / ) $ 77 # )/ '# / 9 $ 9 = /! / K8 77 : L . = 9 $ 9 88 ) 9/ $ 9 / ) $ ) 8 . ? @ / $ # $ 9 88 ) 9/ $ 9 9 88 / )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ MJ J G J
77 : 3 77$ 7- $ 9 $ 9 & / 9 8 O 9 & 8 $ 9 n 9 / $ / /$ 9 9 H 8 K 8 $ 9 , 7 $ 7 ) + L , 7 + 5 6 7 + 6 ; 77 . 8$ 9 8$ 9 # & $ 9 A / ! n n $ # n − 1 ) D " $E & $ # n" $ 1 / . = E S $ 9
) $ 9 = . 9 = E A ) $ = J 9 &8
J &)) 9 / O )8 ! 9 / / = $ ) = # )8 = 9 7 = # ) = K9 ) 9/ L$ 88 $ / ) K8 5 $ / ) L 9 n − 1 ) 9 / $ n 8 A /$ 9 ) D 8 n A ) 8$ 9 , ? @ 7 # 8$ 99 9 / 1, 2, 3, . . . , n A ) K 8 &= H/L!
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
Q
1 + (1 + 2 + 3 + . . . + n) = 1 +
A 8 & / !
n(n + 1) 2
n 2 1 + n(n + 1)/2
CC C 9! ' &* %"* ' '*# ' )2% Q )"2 # ' &* !>! 77 + 7 /
A= / # /$ 9 )# / & & A99 ) 8 1 + n + n2 /
0011
77 - 8 &$ 9 / & K77 - L$ 99 $ 9 ) 8$ 9 K9 9 $ 8L$ 9 99 $ 9 # 9 8 $ 9 K9 $ & / L 8 # ) F # # ) $ # K L $ 9 #
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
@ MJ J G J
8 ) # ) ) $ # ) $ # F ) ) ( ) ) / $ # & # ) ) 88 ) ) # ) 9 = )/ $ 9 / ) $ # 9 ) $ # F $ ) 8 K 9 / $ 9 & 9 #L$ # ) n2 + n + 1
7/1 / 8 / / & 9 $ ) ) / &8 + (( "( $ & A 9 ( H $ J A J $ 9 9 ( 8 & 0 # . ( & " " $2 A ) *$ 9 # 77 ; 9 # 8 *$ )
77 ; A * ) ) 8$ 9 88 9 ()8 $ 9 K 9 L ) 8 8 & '8 K = ) L ) $ 9=/ 8 / * 9 $ = ) $ ) 8 $
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< FS G
= ) $ 9 $2 8 K77 1 9 # 2n−2 9 ) $ 8 9 # * n $ 9
) * n 9 #
$ 8 n
(
# ) * ) & n ≥ 3 ** / '? # ( # >*+ /2'# ! 8'@ /*# # 2 > #'! + #* 6' &2 / ' * /* &!' 8'8 + * /*#'8
.* !' '" & ! /*#'8K
.* !' '" & ! ! '8 / #)( B / # !@ BK
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< FS G
.* !' '" & ! B n+'8K
4* ! " /* !' '/" & n 8K
'"2 / & *# P ** / '? >" * /*# B ! '8 /*' #
4 S & C >"*% *% /#' # 8'@ # L # ') 6' &2 / B '8 # A #) S # ! # "! A @ > 5 S + >
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
"* 5 .
- . $ 77 & ) /$ & & 9 # ) /
& 9 /! 9 9 # & E '#! 8 ) & = $ ) 9 & K 8 & # 9 & ) 8 L # ' #$ & #$ 9 # = $ 9 8 $ 9 & &8
& J ) J $
8
$ A & $ A/ && 9 $ 9 &8
) ) 9 /$ 9 ) 9
)
9 + = + :
/$ )
8 &/ # & 9 $ 9 $ ) ) & 8 &
$ 9 ? @ 8 ? @ $ J J K7+ 7 L $ 9 9 8 ? #@ ! 8 ## T
9 9 $ / / ?
@ J J &
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
GQ G
MQG
7+ 7
&$ 76 $ K L ; 74 9 / A/ ! 14 + 7 = 19 + 2 A ) $ = $ 9 $ 9 / 9 $ 9 ! $ $ 9 $ ) A / K & L 98 $ / $ 9 ) = 7+ + 9 1 2 6
3
5
4
7+ + . 9 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
O ?O
/ ) 9 %8 K = L c$ KL e$ ) K # /L l K. /$ / L l−1 9 ) l − 1 / 9 / $ & / K7+ 5 L
7+ 5 ! 75 ) & ' 8 $ 9 & $ / F $ & &8
$ K L $ ) ; + : & KL ) / /$ 9 &8
& / &8
H &/ 9 &8
$ & F / /$ 9 c ) = & c − 1 >& ! e − 1 c − 1 9 ) ! (c − 1) + (l − 1) = e
! l + c = e + 2,
) )) A/& /
.* !' ' *% B n+'8 ! / /*# *% # *# 2 ' > K
F 8 A ' n A * !>&@ ( A / *# ( #' #* ) > # /*# #'! #* ' F2+!> &!! /*''2 # / /* !' '"* * ' .'*"2 C , ** 2 >!#* ' #* /#) #)* '
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
NM GO
7+ 6 &$ n
:- $ * F & 9 # E /) A/ ) # & $ & J ) /
J 8 A & 9 # 8$ 9 ) ) 9 #$ 9 / = $ 9 & ) 8 ) $ ) $ K ) L ) / ' & $ 9 8 E A/) 9 /
& (K5 ) " 2 9 / K & L /
) A/ & / &9 9 /
1 /$ & 8 9 $ 9 K5 9 # = $ 9 KA99 8 $ )) / $ 9 9 L / $ 9 9 ?
@ ? )@ & : ) 52 = 10 $
A/) 10 + 2 − 5 = 7 F
9 9 $
3·72 = 10, 5 K / +$ 8
8L & 9 $ 9 K5 9 #$ / /! ) /$ 9 10 > 10, 5 .) 8 9 9 $ K5 9 #
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
O ?O
$
8 9 $ # & # J ) J 9 & ) H $ 9 : ) = & 9
) = 77 5 & ) E 9 : ) $ 8 R : ) = & )/$ 9 # $ 9 $ ) 9 # $ 9 * A/& / = / ! 9 9 n ) 9 # &E
n 2 " & & 3n − 6
) & 9 # 7+ + 7 9 8 &$ 9 &/ n ) e $ $ 9 l A/& /
n + f = e + 2.
9 &8
& 9 /$ 9 ? @ 8 F 5 9 $ 3l F /$ / 3l/2 A 9 f ≤ 23 e$ ) A/& / 2 e + 2 = n + l ≤ n + e, 3
/ ) e ≤ 3n − 6 )/
>2K
& "'/%+ ' * # K5 +( ' ! / ** +
$ /*# /*' ! /*# A 4/!+ A "' /*' ! 2 8'8( 2 / #) /*' #) A 8' 8 ! A # #*K ' 2 # !@
5! 3*! # # / $ 9 8 ?
@ K L l A ( # A/ ) )# & $ ( ! $ ) $ = 9 ) /
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< ?O J
9 )= 9 )= 9 )= =
= < 6 7, +, 7+
7+ 4 7: 7, 5, 5,
) 6 : ; 7+ +,
7+ 7 ) / 9 ) = $ ) K7+ 7 L K B#$ $ 7+ : 9 8 ) $ = 9 9 L
7+ : ( ) ! 9 8$ 9 &8
8! ( + & = + > A ) / $ A/) $ /) 8 $ 9 ) 9 = #$
9 ) ) # 8 A 9 #
! ) # ) )9 / & &8
()8 $ 9 ) 8 / # 8 '
/ ) / $ &=/ &$
# J ) / 9 J # &=# 3 #
! 7+ - 9 # ) ) / $ 9 K =# / L &=# $ & ) &=# # K ) ! * &=# L ) K) L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
O ?O
/ ) 9=/ $ 9 A ) )/$ 9 $
) ) ) # A/& / )) ) # A/& / K &8
A/ ) L
7+ - ( ) $ #/ &=9 #
(
# ) *
& "'/%+ P !( *% 8 #>#K
"'"2 '* /'8 /*# /' *%"* & "+ '/% * >2K
'+ ' F2+#2 C P ** */% !>K
6' &2 / / " 2n − 4 !
&
n
>A >* * & "'/%
' F2+#2 >"* '"2 / 3+* # "'/%
6' &2 / / B >!) #) >" 8+ /+ '8 /'8 '*# C
9@ >!) # * 5 A ! # #) A '*# L '"2 / / >!) n A ! '*# " 5(n − 2)/3
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
( * % + . N / 9 K / nL T 75 7 / 9 /$ 9 9 ?& @ 9 8 ! 9 E 2 /$ 9 ! #!
" n 2
2
K. J J ( $ / 9 L
75 7 (
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
O
&/"2 8'( '
/ R >* '*#A 8 "! / ') !
/ >) >* '*#A 8 "! / ') > 6' &2 / ' % & /'*"2 CL L **
'"2 / & n * #/*' #* '&'/( ! '& )"2 # #%)' '( "8 #* '&! #*>&**
A* %# 9 $ / 0 # 2 $ A $ A K0 8L # O$ # ) 2 = K L ) %# = 9$ 9 ) 8 8 89 E F ; & $ $ 9 8 # & # 8 / ?
& @ F & 8 & ) $ ) 8 $ # & 75 6 KL / %# & $ 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
O
2 & $ &8
) d + 1 ) = & $ 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
O
'*# " d '' " d+! '*#A > / '"2 / * '&'/( d + 1 '& '"2 / / G #) !'*"* >" # '*# " d G '&'/( d + 1 '&
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< A
N GQ N
75 ; 3
+ . & 8$ 9 8 $ F 8 8 $ 9 8 E ) # 8 & ) !
8 8 ) /
$ 9 K) / 9 9 L$ ?#@ 9 9 # ) / $ ) 9 $ 9 ) 9 8 8 ( 9 /
$ 8 9 K75 ; L$ 89 & 8 8 8 ? @ ) ! C K L ) 8$ 9 ?
@ K L &8
$ 9 9 $ J 75 '*# + " d ! * > # '*# /*' # d '"2 / G '&'/( d '&
4 G 8'@( * # d + 1 !! #) ! '*# " d #)% d + 1 ! '*# d+! / '"2 / G '&'/( d + 1 '&
2*"2 G * 8'(!>> >" K5 ' 5 >A " * ! ' 8'@ ( > @ '#'!+ ) / #( K5 + ! 8'8 !>" .*''2 # G #2 '*#*
4 Gn ' * # Kn +( ' n >A " *% >2 .#+8 / ** .*''2 # Gn #2 '*#*
722 >!)* / # # 8+ '!> F2%>* # #) '* 8'@( ()2/ / !!> '&'!!/' C '& # )(
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
< A
N GQ N
'"2 / / & "'/% * #) #* * >* '*#A ! /*" * >*
'"2 / / !!> #) >" >* '*#A ' '* ! '& '&'/(
9@ !!> # #) > '*# L 9 @ / !!> '&'/( L '& '"2 / !!> *" >* V1# 8 ? X 722 # / ' *&* #)&* ' / & "'/% >* * #) >"* '*# L * #* '&'/( L '&
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
, ' '
7 # /# 7 "# K76 7 L #
! ; ) # ;
$ 9 8 9 ? @ K 9 ? =@L$
# & ) = 9 $ 9 ? =@ 9 ) $ K L ) ) J &$ 8 / &
/
76 7 # 8
/ A $ 9 J 9 / $ 9 F ) /$ 9
/
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A J FJG
KL ( ( ( 9 8$ 9 # $
9 8 &$ 9 K) L
/ A #
$ 9 / KL ( ( $ A /
/ K9 ) 9/ L # F 9 / / ! / ?=
@ K76 + L &9 / D 8 ! 9 / # KL KL # ) ) ! ? $ 9 J J$ 9
/ K L $ ( 9
76 + P ?A D/ KL$ KL K L
#
/ /
$ ) / ! K L ( $ 9 . 8$ ! ?" K L T KL K L $ 8 ) p K L /
) K $ 8 L " 9 q K $ r ) L p 8 ) T KL q r M " s M J K L J 9 ) K76 5 L s x p
x´
q r
K L
76 5 F / ) # . x K ) $ 8 s ) L x ) K / #
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A FG G J1 1 J GQ
9 8 = $ 9 K s ) # L 8L F & $ x / )) x )/ 9 # K L $ & / ) 9 @ ? / J & J$ 9 KL ( 9 ?A / ) / @ J 9 )) B # 8 & 9 ! ? D/ J 8$ J ) $ 9 KL$ KL K L / $ 9 5 ) $
$ 6$ : - ) A ) )9 D/ &8 $ 9 // $ ; ) #
$ @+ 8! F ( ! >% /! #! @88'K 9@ M!N > ' A" >) * A" >/*# # M)N > *#( 7 2A* + >2K G+& % #)"* / /*# > / ' # ') C, C ** /*#'8 A >!)*2 8 F 8 ( ' ' ' # 8 > 8'8 >"2 '"2 / #) 8 #) >"* > !(" G+& % ' #)"* / ! > " # + 8'@@ # /*# # ') '"2 / /*# > ! # ') />2 / '+ ) ! #)& G+& D >"* !>( ''* )8 * !)! 7) ## '' '' ' @88 '* ' 8'& # 8! /# ' / /*# >"* !>( #* '' ' ( 2 !! @ 6' &2 / # )2/ ( / ! !>( #)* )8! /' ! / #) ''* * # !>( )8 *
'"2 / ! * !'& #(& ' ) 2")* #) '
# !@ % / ' #(& % M! *N # (&! *2 G+&% A )88 / @ ' M! * N >" >) ! * >
##) , > ! P + & ' #)+ #*K
'** / G+& #) >" !!? )''@ * > A / 8'!>( #)"2 @ @ ) #) !> . !/"@ ' K
! #) >" D ! /! & ') $!+ G+& >" ! % 2#2 /%*K
B / " & $ 9 &8 )
= / $ / = / . = V 9 K ( 8L$ $ V 9 # # 9 K L$
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A FG OOJ NF N
8 / & KL$ KL K L /
$ $ ( #$ # 8 K H /# ) L ) / ) K( & /$ 9 ; ) = ) L ) # ) F 8 $ D/$ 9
/ / ) T n + 1
8 K9 8 $ 9 L$ ) n ) 8 9 +$ ) 5 # / $ 9 9 ) n$ ) n + 1 '"2 / n )? >"& & n2 + n + 1 > ! n2 + n + 1 B / = /$ KL K L ?) 9/
*# @ 8$ J =E E J # 8$ 9 ) / = I 8 ?) 9/
*# #@ $ 9 L ) 9/ ) 9/ K9 / # 8 p ) $ $ p ) 9/ LL L ) 9/ ? @ $ I ) & $G ) !10 1 / # 9 # ) 9/ 8 ? @ ) $ ) / / ? @ $ )) ) # A KL ! ? @ ) K/ $ L$ ) / K L$ 8 ) 9 # K ) & ? @ ? @ ) L F $ 9 ) & 9 / A 8 KL ! 9 $ ) / $ 9 ) 9/ $ ) ? /@ & ) T 9 # ) B# / K L$ K L KL T K&L J J 8 ) G 9 # 76 7 - & / # ) J ) J 9 8 ? @ )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A FG G J1 1 J GQ
I # ) I ? @ / / = & /
# % # //' K . B# & $ / $ 9 9 ) 8 J 9 = $ 9 ) # E F 8 8 )) & 8 9 D 38 9 ) R )/ A 4 ) 8!
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A FG G J1 1 J GQ
A E 3 $ 9 & $ 9 9 ) $ 9 7+ 9 # = ) /$ 9 ) 9 / 9 # K ) & ) L . ) / $ 9 8! ) $8 @$ 9 ) 9/ & 9 ( / & 7: # K # ; ) L & $ / 3 #$ 9 # 9 #$ 9 # # J 9 = 9 $ v = = 6j + 3$ # 74-4 N 09/ 9/ / ' 8 ! N09/ 9/ $ 9 v = 6j + 3 v = K )) & L A 9 # & 9 $ $ K 7:L 9 ) 8 ( 9 #$ 9 99 153 /5 = 91 ) 8 # 9 $ / ? @ K 9 9 9 # L ) 9 $ ( &$ ! 74;6 2 _
D # . ' / 4 × 4 F $ 9 ,$ 7$ + 5 = $ 9 ) ) ) /
= K4 × 4L 8 , 7 + 5
7 + 5 ,
+ 5 , 7
5 , 7 +
, + 7 5
+ 7 5 ,
7 5 , +
5 , + 7
K76 8'( 7 * >*% >/2 8 #*2 ! 'K " 4 × 4 $ K76 7,L
) E " ! B# /$ 9 )# & $ / K76 7+L ' 8 $ 9 9 / $ 8 , 7 + 5 + 5 , 7 K76 7+L 7 , 5 + 5 + 7 ,
6' &2 / # !' 4 × 4+ ! ' # C, E ! C, C #)/*# ! ' * >* 9@ C, CL ! ' F' #")# 2 ' # ' C, C + ' ' (/' ' *< # !' * ! '
/% ?( ! ' 8'8 /* ! ! 8) / @8!
! I ')* @888 ! '# ! & * 6' &2 / *# ! #2* / > !"'* 8 @ @ + ! / /! *# ! !"'*"* "8"@ #2* #)! ## @ 7 > ) ! G+& 8'8K
? * "*! '* 8'( > D > # #) ! C L # ' 8 /*#'8
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
A H
! ' */% ' ' '& > ! '8) ) > ' #+ ) 2 '&? $ /* > * # '8) /*#'8 # /*# > 8 ,* '@ /*# *+ > / #)/*# 2 #)/*# @88'( '*#A ' / #)/*# 2 #)/*# @88'( ' */% / #)/*# 2 '&? #)/*# @88'( '&? ' "*! A ')() / '@ >"* ! * > # 8'@ # 2)"2 !''@ ! '@ "% /*#Q / #* "% /*# )&2 L A" >
# ! 2 "% /*#% "*! ! ! .* "% /*# K '"2 / *# ! > ! > # '% % ! > "% /*# 7 > ! L #? _ & 8'8K ) 6' &2 / "*! !! * / * # #)
.* >" ! >"& &K
CL #? >&# '( x ! y # ! @ /*##? /#'* '"2 / ' /*# )' ! /*''2 # )' >#!
{x + y, 2x + y, 3x + y}
0>&2 # !'+ )' ' * >#! v = 15 k = 4 λ = 1Q v = 8 k = 4 λ = 3Q v = 16 k = 6 λ = 1
v=9
6' & / ' #(& ' +)' #
722 # / /! >" P T "' #2 8')%+**" ! ' 0*&/%+ ' #O !K
G+%) #*"* &"2 L #? >"& & * #/*' %) .* /* !> ' %) # "&K
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
(- (. ! # . !/-∗ 9/ / 9 = 7:, K L 7:, 9 9 $ 9 9
## 8 ! 9 / 9 $ 8 9 9
$ 9 # 9/ )# $ / A9 9 F $ # $ ) ! 9 = $ 9 & ) & )
/ ) $ 9 150! 9 ) & &$ F F /) #$ 9 9 $ & ! J # ) J $ J 8 & Q F ! & ) 9/ $ # $ J & 9 # J $ 9 = # 9 # ' 9 9 $ # :- 9 $ 4: ) $ ) 9 9 & / ! ∗ ( &. ) ( 1 &: 8 5 & $ Q & $: # 8 / &, 5!2/ 2 $+5 #: $ */& 1 = 2 B5/2; !2/ &> /*!2( !2(&B +2 &6 8 D '#:*+",& = 5+ 5B1 /8 3 /&& #51 M65 4 2 1 VKH> * % ! 1 &6 8 2(;* 2 #? $ 5+&:+* &
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E JQ FM
J ) 9 $ $ 9 &9 E J 3 Q J & 9 = 9 F 9/9 & / ! J $ 9 9 $ 9 :- 9 & $ :: 9 # ) ) E R $ # ) 8 $ / # $ $ 9 9 $ = # 3 $ 9/ = 9 # P / $ 9 9 & 7:, 9 / 8$ # J # J 9 ) 9/ / & ) $ = 9 9 F $ ) ! 8 $ # & 9 & ) # ) $ 9 7:,Q 9 8 &$ # F 9/ $ F ! J C $ $ $ 9 $ / ! 9 9 # 9 $ & = $ 9 9 9 9 $ & ! F # & J / Q /
$ 9 & /
$ & & ?) #@ 9 $ 9 & ) . $ = ? 9 / @$ 9 / / $ 9 ) & ) $ = ? 9 /@$ 9 / ? @ ) X 9 $ J 8 J |X| B# = 9/ 7: 7 G / D & ) K L$ / # & ) K
L 9 8 & /
) # . /
& 9 # K 9 #L$ # ) / # # & # H5 3 /
K. $ 3 " ( & $ 8 & 98 8 L F & ) J ) . J
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E SJ J GOJ
7: 7 A ) 8 ) & # 3 /
1 /
& $ 8 / & 3 /
) / $ 9 "% $ 9 n $ n = ab & 9 / K9 a, b > 1L A ) #$ 9 89 F $ & 8 & ) /$ 9 8 # 8 A
9 9/ $ 9 # & ! 8 $
$ K $ 9 8 L A ) $ 9 ? & @ /
$ 9 . $ 3 /
O 9 9 $ 9 9
8 # 8 $ 8 8 / $ 8 K 9 L J 9 & 8 $ E F 8 ) . E ) B# ! ) ) & 3 /
K 7, 5 7 & /
L$ $ 9 & . $ & 3 /
K. ) 8! / # $ # L ' 9 3 /
$ & 3 /
$ 3 /
& 3 /
& $ 8 3 # & 8 9 / 3 /
$ 9 9 ) # K / / L 9/ 9 $ 9 9 #! $ 7, 6 &
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E J J GOJ
/ A ) &
$ & 9 # 9 $ F & ) 9
8 M$ M # 9 /
/
8 K ( $ M # # 9 #
) $ 9 9 L A & J J /
$ ) / &8
$ 9 ) $ $ ) J 8 8 Q K - 7, & / ! / a ) ) ) L ) 3 /
& )* 8 9 & / /$ 9 # )* ( : / & 8
7 #! # > & # $ 89 $ 9 8 $ )) 8 K ) DL / & = 9 ) D )9 ! &$ / 9/ $ 8 8 $ 2 $ 9 0 / & 8 $ / $ K ) L 9 F 8 $ K0 / L 9 $ K 8L # $ 8 8 # 9/ " # 2 )$ ' 8 99 $ 9 ) 8 $ 8 & $ & # 8$ 0 / ! & # & $ 8 $ 9
$ 8 / # $ 9 # & # # A / $ $ 9 9 2
9 $ 9 # # & 9 7: + 7 &
/ $ 9 9 # 9 8 J & $ 9 # ) #$ ) O 9 # 9 $
& # # & 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E SJ J GOJ
$ , ? " ( @ 9
! # ) /
9 = C # 9 /8 $ 9 9 9 = ?) @ 8 9 $ / /) 9 9 # A ) $ ,# 7 # $ ) / ! 11000111000010000110010100100100101100110010101100001110110000010
9/ 2 K # 8 L 9/ 8 8 2 ! 0( FB3O Y A99 8 = $ 9 /) ,# 7
3 $ 9 ) # # $ B# ! 9 9 / ) / 011# $ C F / =
$ 9 7 +- 8$ ) / & K / /$ 9 : L ,,,,7$ 2 ,,,7, & 8 00001100101001000001000110101100000011010111101110001000000111001
A / $ 0 / K / # # / # L 8 ) & 9/ = 8 $ 9 ) 8 9 K ,9 L ) K7 L $ ) # 8 ! 0 ⊕ 1 = 1 $ 9 $ 9 # ! 0 ⊕ 1 = 1$ 0 ⊕ 0 = 0$ 0 ⊕ 0 = 0$ 1 ⊕ 0 = 1$ 1 ⊕ 1 = 0 . . . K3 & 8 $ 9 8 # 9 /$ 1 ⊕ 1 = 0 L F ))! 9 ) k 7$ 9/ 8 k & K , 9 7 $ & L$ 9 ,$ 8 k 9/ 8 ! 11001011101011000111010010001000101111100101000010000110110111011.
A 8 2 $ ) & $ ) 8 0 / $ ) J / # J 9 ! / $ 9 8 8 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E <
89 ) $ 9 8 & # / $ 8 D $ 9 / 8 9 $ 9 8 # KA / & / 8 ) 9 $ 9 8 8 J / 8 ) D L . 8 8 8 / $ 9 $ 9 = = &9 $ 9 2 / ) $
7: + + 7: + 5 & B#
9 #$ 9 8 # K 9 # L * 8'( @' / &! #%)' + & I2 ' @' ! 8 )! # " !> ' ;% K ! " ! " #
/2 ## /* 8 ' @' ( ! + # >) #*) ! ' @' #*) ! >) /#) ! & ! & * F' ' !' # @)8 #* A ' @' % / 6! # ! # ' @'! 2 '' +# >)) A" & #*)' #* / ! ' @) 6!* I2 #)! @' ! #" ' @' . K
* +# >)( ## & 6! !>> 2 '' >)) %) *' # /2 #* ' @' @) I2 ' @' ! #)( #" . K
! $ ) D ;, 9 $ & $ 9 8
/) $ 9 & ' 9 $ 8 # " ) ) 9 8 2 & ) $ = $ 9 &$ $ 9 $ 9 ) A
/ # ) $ #$
& $ ) # 2 # 8 $ 9 $ 9 & 8 $ / # ) J / J 8 8 ) F )
K & L$ = 8 8 $ & #
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E SJ J GOJ
J / J $ ) 2 / 9 # & # ) & ) ! 2 9 ) $ 9 / 8 & $ ) $ 9 # & ) A 9 Q . 8 ) 2 / 9 ) $ =
9 / / 9 $ 9 ) 8 & # $ & 9 $ )
8 J ?/ @ J & 8 9 . & # / 8$ # 9 A ) 8 )* ! / $ 9 & # $# J ' " / 9 ) $ /) K 9 L 2 $ 9 ) # ! 9 / ?77@ ( $ ?-@ & $ ?5@ ) $ ?77-5@ ! ?(&5@ A ) $ /) A/ ) # / 74- = $ 9 +,, p = 1163 . . . ) ) H $ +,7 q ) $ N = pq K )) 9 9 # $ # ) L 6,, 6,7 N / 8 2 F )
2 ) p q ) ) p K L ) / 9 #$ 2 9 $ 9 ! $ 9 pq # ) N 2 9 #$ 9 # A $ 9 ) $ / N ) # ) 9 $ 8 N 2 $ D / O 9 N & # & $ 8 2 E A 89 J 99 # ) ) ! 6,, K 6,7L ) A & / 9 & F 9 $ 9 p , q ) ) 8 )
E 3 $ 9 2 9 p q $ 9 $ 9 N KA ) ) & - 5 7 9 / L ) p ) 9 9 $ 9 p ) / # 74- q ) & && /$ 8 ? /@ 2 & # $ )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E A GQ J GQ J Z
& / J N ) & ) J 9 # /
! 9 $ 9 / ) & ) / / # # 9 8 / / & / ? 9 @ 8 F # $ / $ / # / ) 9 # A # 9 = ! # )
$ $ # / 9 8 8 #
) )/T & # K) L 8 ) 8
+# >) ! 2')2 )! 8'( "** "" > 2% !>!! &** F &" !>! # + (& ! / /' !@ * C+' + # >) #%)'/' /% #") #*> @) 6!* ' @' F)"+ 6! "K
)! #*'" ' "** ! C+' / '! ! #)'* !# '8 " 2 7 @ '*#* "* ' ( 8K
. )# ) . # $? A # / # ) 8 &
$ # 8 ' ) ! # ) # $ # ) / 9 #/$ 9 9 )* 9 $ 9 = 9$ / 8 & # $ 9 A 9 9 9 J / # ) ?
@ 9 & /Q ) # )/ 8 &$ 9 # 7,, p ) K ) ) 9 9 = #$ ) / 9 # L 8 & # $ 9
q ) $ ) N = pq $ ) N # ) $ 9 ?#@ # N ! 9 $ & A
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E SJ J GOJ
+,, 7,, # # ) & 8 &$ 9 8 & & # & # N 99 $ 9 & # 9$ N 7,, # $ ) & J J ) 8 9 $ 9 N & & # & $ ) & /
& #
8 &
. ! . ? ? ) D @ / # ) J = $ 9 J ) 8 8 F / /$ 9 ) K- 6 7 L$ +,, ) $ 77-5 K $ LE F) 9 ) ! CCPL LDC +,, $ 77-5$ 1163 · 10196 A ) $ & 9 & 8 # ) Q - 6 & / 9 9 # / $ 9 1, 95 · 10193 ) 8 9 A # 9 J 9 / 88 E 3 9$ 9 & K# 9 L 9 $ / 2 $ & 9 $ ) $ $ $ 9 ) ) . ) $ = )# 9 - 6 & /! +,, 88 6-, ) $ 6-, )# ) & A 9 9 $ # )) 9 ) ! ) / ) / ! CCPLC,PDCTDP555DPLDEEED,55EPPPETTLP5,DPPP PTTDLTC,,TEL5,PP,D,LP,CETECC,PT,CCCLTTPTE5TT 5D,5DC55D,TE5PEPLECD,LLLT5,5T,CT5EL5L5,TTPL LDTLCD5DD55ETP,DLEP5DCCDCDDEDDTLTE,P5,C,5TE
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E H QJF I L J N
" / 9 $ 9 & # ) 9 - 7, & 9 /! $ 9 ) K 9 9 #L$ $ 9 ) & 8 9 & K /
& 9 L
E.# / ! " ' #
) D $ & $ 9 # ) / A & $ N # ?@ 8 K # 9 && ) ! N $ 9 L
$ ! ) $ p q $
m = pq A/ +,, $ d 8$ 9 (p − 1)(q − 1) # ed − 1 K. 8 $ 9 9 L m e & 9 ) K & L$ p$ q d d ($ $ e ) $ # K p q ) & 9 $ 9 8 $ )8 L 8 &$ 9 2 8 8 ` x K /$ 9 9 8 L x 9 m K9 9 $ 8 8 L ) 8! 2 xe / m F x e K+,, L $ xd 9 10200 A / $ # #
$ /) m # ) 8 8 A / # $ & + 5 " 9 r # & # $ 2 8 8 d ) / $ 2 & ! rd / m P &
K
$ 8 L! )) x ? @ P 9 2 E A99 2 8 / ! 9 Kp q L ) $ m $ d e ) $ 9 e d − 1 9 # (p − 1)(q − 1) $ 8
9 m e A/ 8 9 J J 8 e $
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E SJ J GOJ
$ ! % ?5 % @ # ?@ K- : 7 L )/ A 8 $ 9 8 x $ 8 ) r! xe / m A 9 /! r ≡ xe (mod m).
8 # 9 / d 9 ! rd ≡ xed (mod m).
! rd m # x $ ) xed / m 2 /$ 9 )) x F 0 ≤ x < m$ $ 9 xed − x 9 # m F ) m = pq 8 ) $ / $ 9 xed − x p q 9 # " / J / J p # 9 #
e d / & /
$ 9 ed−1 9 # (p−1)(q−1) $ ) p − 1 A ed l ed = (p − 1)l + 1 9 # R )/$ 9 xed − x = x x(p−1)l − 1 .
x(p−1)l − 1 9 # xp−1 − 1 K- 7 - & L$ (p−1)l − 1 9 # xp − x$ / # J ?@ x x J 9 # p A%& 0)%' 1C /$ 9 # 9 / ) ! /) - 7, & & / $ e f (88 J / e J 1, . . . , (p − 1)(q − 1) − 1 8 A $ 9 ) (p − 1)(q − 1)9$ - - & / / = 9 . $ (p − 1)(q − 1) ) $ & 8 ) $ 9 $ 9 8 )# # / 8 $ / / / $ 9 e $ (p − 1)(q − 1) ) $ / ? @ K - - & L u v )$ eu − (p − 1)(q − 1)v = 1.
eu − 1 9 9 # (p − 1)(q − 1) . d u / (p − 1)(q − 1)$ ed − 1 9 # (p − 1)(q − 1)
$ / 9 & /
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E H QJF I L J N
A / ! 9 / xe / m$ xe '
E ! = $ 9 - 7, & / / *! !( 1) ) %& N 8 9 # 8 & ) /$ 9 8 ) 2 # . 9 #$ 9 8 # 2 8 E #$ 9 ?2@$ 8 9 2 )) 9 A # 8 $ $ = $ J J # ) 8 $ # A J J 8 ) ?2@ A/ $ 9 8 8 2 # & A)9 $ 9 8 2 #$ 9 9 K #L & E 3 ! # / 2 ) # K9 / # 8 $ 2 # ) 8 $ /)
& 8L . # 8 N # / 9 9 #$ / D # % N )
/ $ 74;; # / # & 2 # $ 9 $
8 K= $ 9 9 L 39 $
()8 $ 9 & / 2 8 $ / & 1 8 r K 8 L$ e # m ( &8 ! )# 9 / d # $ # 8 $ 9 8 # x xe / m $ $ 9 & 9 # ) / 8
9 ! $ ' JI4" m (# ' K7: - 7 & L ) & & $ 9 # J # $ 9 N
9 @ / 6! )' #2 # ' +)' ' #! & ( * % !> 8 )! * m ! e %)"* #+ ! 2)" '*#& d %) 722 # / >"* #! '*#&/" (p − 1)(q − 1) '*#
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
E SJ J GOJ
! / ' 2% &!! #/*'/" ' m = pq >&#! '( *
$ %&! F 9 / E S $ 9 & 9 / ) $ 9 N # # $ 9 B# 9 Q N 9 " K / "L$ / # ) 9 ) K
9 )L
/ K) / 9 /$ 8 L$ # )8 / # $ $ 9 9 J 8 J A # 8$ /) $ 9 ) 9 9
7,, ) )/# #
! +,,$ / # 6,, ) 9 x e 9 9 8$ =
= $ 9 8 # $ & $ 9 8 / 8 8 H 9 / ) $ 9 $ ) / OA KO A ) L A / / 9 8 9 /$ / $ 9 # 9 /$ & 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
/ : ! F
7 · 6 · · · 2 · 1 = 5040 0! 15 · 23 = 120 O#! 15 · 3 · 2 · 1 = 90 " 2! 9·7·5·3 = 945 0! 945·25 = 302,40 O#! 945·5·4·3·2·1 =
= 113 400
KL / 9 T KL ) ) T K L 44
T K L & T KL 9 T K&L KL ( T KL T K L T K L " KL A ) & T KL ) ) T K L ) T K L & T KL ) ) T K&L 2/ ) # $ 9 $ $ 7 - 3 ∅, {0}, {1}, {3}, {0, 1}, {0, 3}, {1, 3}, {0, 1, 3} < 9 / 3T ) T Y 9 # {a}, {a, c}, {a, d}, {a, e}, {a, c, d}, {a, c, e}, {a, d, e}, {a, c, d, e} 3 Z Z+ ! {0, 1, 3, 4, 5} KL {a, b, c, d, e} KL /# K L A 9 # # 9 /# / 9 $ # & # 9 8 {A1 , A2 , . . . , Ak } 9 /# 9 $ Ai 9 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
6, 9, 10, 14 " /# $ n m 8
$ & n + m # KL {1, 3}T KL ∅T K L {2} - 9 $ n m / / # (A∩B)∩C = A∩(B ∩C)
9 $ 9 9 )$ A$ B C . # K7 5L
T K7 6L ) # K7 7L / A B 9 8 D T $ A B 8 ) $ KL ) ) ) 9 KL B
" KL 29 T KL 2n − 1T K L / # K L
# 9 " 2n−1 "" / 9 # ) $ /) 8 8 F ) ) ) 9 $ 9 $ 9 "# KL 2 · 10n − 1T KL 2 · (10n − 10n−1 ) # 7,7 # 1 + n lg 2
- - -" -# -- -
& 4$ 7+ 5 · 4 · 3 = 60 313 6 · 6 = 36 1220 (220 )12
!
n! KL 7 · 5 · 3 · 1 = 105 KL (2n − 1) · (2n − 3) · · · 3 · 1
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
"
/ K B# & 9 & $ 1020 $ ) 77 9 # / KL 100!$ KL 90!$ K L 100!/90! = 100 · 99 · · · 91 n! = n(n − 1) · (n − k + 1) /" (n−k)! /# $ #
$
(& T #T " 9 ## 5 & n = n " n0 = nn = 1$ n1 = n−1 # K7 ;L &8
#
K7 b$ & ! # ) 9 # ) n+1 2 = 9 A / ) #! A k 9 9 / = $ 9 8 Kn 9 L$ / ) / n − 1 9 # (k − 1) 9 K n−1 9 L k−1 A k 9 ) k /$ 9 / k / F $ 9 9 &)) 9 a = 9 9 $ a−b$ b−c c 9
7-# #! $
% !
F n n + 1 8 ) $ n(n + 1) 1 / #!
= 0 T 9 ) n > 1$ / # & ) n(n + 1) = (n − 1)n + 2n$ n(n − 1) ) $
n = 1 T 9 ) n > 1$ 1 + 2 + . . . + n = (1 + 2 + . . .n + (n − 1)) + n =
n(n + 1) (n − 1)n +n= . 2 2
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
" D n & 9 $ ; ) - & > 9 1 + 2 + . . . + n & T / /$ 9 & n(n + 1)/2
# / 8 & #
- n / #T n = 2 . n > 2$ 1 · 2 + 2 · 3 + 3 · 4 + . . . + (n − 1) · n = (n − 2) · (n − 1) · n + (n − 1) · n = 3 (n − 1) · n · (n + 1) = . 3 . n ) $ 1 + n = 2 + (n − 1) = . . . = n2 − 1 + n2 = n + 1$ & n2 (n + 1) = n(n+1) . n ) $ ) 2 =
9 /
/ . n ) $ 1 + (2n − 1) = 3 + (2n − 3) = . . . = (n − 1)+ +(n + 1) = 2n$ n2 (2n) = n2 . n ) $ 9 #$ /) / # 8
1 / #T n = 1 T 9 n > 1$ 12 + 22 +. . . + (n − 1)2 = 12 + 22 + . . . + (n − 1)2 + n2 = =
(n − 1)n(2n − 1) n(n + 1)(2n + 1) + n2 = . 6 6
3 1 / #T n = 1 T 9 n > 1$ 20 + 21 + 22 + . . . + 2n−1 = (20 + 21 + . . . + 2n−2 ) + 2n−1 = = (2n−1 − 1) + 2n−1 = 2n − 1.
K@ L n = 1 . n > 1$ n 9 =
= = )9 / $ 9 n − 1 9 =
= 9 & 8 K k&)) 9 8 L 9 9 kn−1 · k = kn K5 L n = 1 . n / 8 $ 9 8 K n 8 9 8 9 8L$ K / # & (n − 1)!&)) 8 9 8 L 9 9 n · (n − 1)! = n!
n = 1 T n > 1 . n $ & $ & ! & Kn − 1L$ n − 1 & K / # & (n − 1)(n − 2)/2L & (n − 1) + (n − 1)(n − 2)/2 = n(n − 1)/2
3 8 n = 1
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
" # / $ 9 / # ) /) n = 1, 2 8
n = 3 J 9 J 9 & ' (
KL n 9 9 $ 5 9 KL 2n /n2 > n3 /n2 = = (n − 1)(n − 2)/(6n)$ / # & 9
( 8 / # n = 4 ! 4! = 24 > 16 = 24 . n $ (n+1)! = (n+1)n! > (n+1)2n > 2·2n = = 2n+1 )
"
18 + 23 + 21 + 17 − 9 − 7 − 6 − 12 − 9 − 12 + 4 + 3 + 5 + 7 − 3 = 40
* + ,
# . K / L / & +, 3X Y 89 $ :,, ,,, / & 20·500 000 = 10 000 000 3X Y 99 8 $ 9 -## # .
$ " 3 (
"
(x + y)n+1 = (x + y)n (x + y) = n n−1 n n n x xy n + y (x + y) = y + ... + = xn + 1 n−1 n n n−1 x y(x + y) + . . . = xn (x + y) + 1 n n n y (x + y) = xy n−1 (x + y) + ... + n n−1 n n x y + xn−1 y 2 + . . . = xn+1 + xn y + 1 n n n xy + y n+1 = x2 y n−1 + xy n + ... + n n−1
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
n n n n xn−1 y 2 + . . . x y+ + =x + 1+ 2 1 1 n n xy n + y n+1 = + ... + n n−1 n+1 n n + 1 n−1 2 n+1 n+1 x y+ x xy n + y n+1 . + y + ... + =x 1 2 n n+1
n " KL (1 − 1)n = 0T KL nk = n−k ""
! n ) "
( & $ ( & A = 9 /$ 9 / # ) ) = 9 ! 9 9 7$ 8 9 7 9 ) 9 $ 9 $ 7 ?9 @ ) 9
"
n n1
n − n1 n − n1 − . . . − nk−1 · ··· = n2 nk (n − n1 − . . . − nk−1 )! n! (n − n1 )! ··· = = n1 !(n − n1 )! n2 !(n − n1 − n2 )! nk−1 !(n − n1 − . . . − nk )! n! , n − n1 − . . . − nk−1 − nk = 0 = n1 !n2 ! · · · nk !
"
KL n! K 9 / 1) · · · (n − k + 1) K? @ /
9 L KL n(n − k$ n − k K L 8 O# #
? @ 9 K L nn K / 9 L " " KL Un = 8V 8!$ KL 8! · 84$ K L (8!)2 1
"" "" """
13!/23
75 8 $ 75 # ?#@ ""# KL 356 KL 6 354 9 8 T 42 &)) 9 / ) T - ) # 9 / K 8 ) # )L$ + 6! 6! 2!2! 9 8 9 354 42 2!2! K ) # )9 /L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
K L - 77&)) 9 / & ) ! 6=6=5+1=4+2=4+1+1=3+3=3+2+1=3+1+1+1= = 2 + 2 + 2 = 2 + 2 + 1 + 1 = 2 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1.
K L & & =
/ /! 9 n 9 =
= # $ 8 E A / $ 9 n & 5: $ & ! n+34 34 *
"# "# "#"
n−k−1 k−1 n+k−1
+k−1 kp + k − 1 k−1
- .
n "- A / $ nk = n−k n n "- 0 = n = 1 K) / 8 9 # #
&8
) L
- .(
"
n n n n = + + ... + + 1+ n n−1 2 1
n−1 n−1 n−1 n−1 + + + + =1+ 2 1 1 0
n−1 n−1 +1= + ... + n−1 n−2
n−1 n−1 n−1 n−1 = + + ... + + =2 n−1 n−2 1 0 = 2 · 2n−1 = 2n .
" xn yn 8 9 #
2 n n n n−1 n n n x + x xy n−1 + y y + ... + 0 1 n−1 n
&!
n n n n n n n n . + + ... + + 0 n 1 n−1 n−1 1 n 0
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
" " (n + m) 9 k 9 $ 9 9 n 8 " # . j K & n + 1L$ 9 8 > j−1 n n+k+1 n+k n+1 n = + ... + + n+1 n n n
$ n+i n
)/
=
n+i i
&8
&9 ) K5 :L
" - . , (!
"/ n = 3k + 2 "/ 3 F / 9 k $
8 8 ) !
n n n n − − − ≤ 0. k+1 k k k−1
n k−1
k(k + 1)
(n − k + 1)(n − k) − 2(n − k + 1)(k + 1) + k(k + 1) ≤ 0.
$ ) 4k 2 − 4nk + n2 − n − 2 < 0.
)/ / # k )/$ 9 n 1√ n 1√ − n+2≤k ≤ + n + 2. 2 2 2 2
) k 9 $ & ) $ k=
n 1√ − n+2 . 2 2
# /
" + : 7 " ) # /T )/ )/$ 9 ln
m+t−k m−k
m+t−k −1 t ≥ m−k , = m+t−k m+t−k m−k
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
ln
m+t
+ ln
m
m+t−1 m−1
+ . . . + ln
m+1 m−t+1
≥
t t t + + ... + . m+t m+t−1 m+1
≥
. 9 /$ ! t t t2 t + + ... + ≥ . m+t m+t−1 m+1 m+t
/ ? 8 @ K5 4L &8
& )/ " KL 2 /$ 9 e−t /(m−t+1) ≤ e−t /m ≤ e−t /(m+t) A #$ 9 D 8$ 9 ex &8
KL & # 9 ! 2
2
e−t
/(m+t)
−t2 /(m−t+1)
e
2
= et
2
/(m−t+1)−t2 /(m+t)
2
,
t2 (2t − 1)t2 t2 − = . m−t+1 m+t (m − t + 1)(m + t)
A 8 1900/(41 · 60) ≈ 0, 772$ 9 9 e0,772 ≈ 2, 1468 "" K5 4L &8
) 2 2m 2m ≥ et /(m+t) . m−t m
. t ≥ 0$ t # &8
K m 9 / $ √= $ 9 t(1 − m+t ) /L$ # & 9 $ 9 t ≥ m ln C + ln C $ $ 9 √ √ ( m ln C + ln C)2 ln C(m + 2 m ln C + ln C) t2 √ √ ≥ = > ln C, m+t m + m ln C + ln C m + m ln C + ln C
2m 2m > C. m−t m
& 9 #
4#-""#3 * / ( )
# F 9
/
#
Fn+1
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
#" % Sn # 9 . n = 1$ S1 = 2 K 8 {1} 9 L . n = 2$ ∅$ {1}, {2}$ S2 a5 G ) ! n $ 9 9 n $ n − 1 $ )/= 9 & Sn−1 F /# ) / $ Sn = Fn+2 *
# /# ) ) # 9 ) / ) $ = ) # ( 9 / ! 9 n 9 # : $ Fn $ 9 n : 7 $ Fn $ 9 n : + $ Fn $ 9 n : 5 $ Fn $ 9 n : 6 $ Fn Kn / #L ) 9 # " 1 / # n = 1 n = 2 8 & 9 $ 9 n ≥ 3 KL F1 + F3 + F5 + . . . + F2n−1 = (F1 + F3 + . . . + F2n−3 ) + F2n−1 = = F2n−2 + F2n−1 = F2n KL F0 − F1 + F2 − F3 + . . . − F2n−1 + F2n = (F0 − F1 + F2 − . . . + F2n−2 )+ +(−F2n−1 + F2n ) = (F2n−3 − 1) + F2n−2 = F2n−1 − 1 2 K L F02 +F12 +F22 +. . .+Fn2 = (F02 +F12 +. . .+Fn−1 )+Fn2 = Fn−1 Fn +Fn2 = = Fn (Fn−1 + Fn ) = Fn · Fn+1 2 K L Fn−1 Fn+1 − Fn2 = Fn−1 (Fn−1 + Fn ) − Fn2 = Fn−1 + Fn (Fn−1 − Fn ) = 2 n−1 n = (−1) = Fn−1 − Fn Fn−2 = −(−1) # # K6 7L ) Fn−1 = Fn+1 − Fn & 9 /$ * Fn 9 / K?&@ 9 # /#L! . . . , −21, 13, −8, 5, −3, 2, −1, 1, 0.
$ 9 J /) 8 $ 9 () ! F−n = (−1)n+1 Fn ,
) n / # 9 # G / n = 0, 1 T 9 n − 1 n $ F−(n+1) = F−(n−1) − F−n = (−1)n Fn−1 − (−1)n+1 Fn = = (−1)n (Fn−1 + Fn ) = (−1)n Fn+1 = (−1)n+2 Fn+1 ,
/
# -
Fn+2 = Fn+1 + Fn = (Fn + Fn−1 ) + Fn = 2Fn + (Fn − Fn−2 ) = 3Fn − Fn−2 .
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
n 9 2n − 1 )/ ) * # /# ) A &9 9 / K6 +L &8
! 2 2 Fn+1 + Fn2 = (Fn + Fn−1 )2 + Fn2 = 2Fn2 + Fn−1 + 2Fn Fn−1 2 2 2 = 3Fn2 + 2Fn−1 − (Fn − Fn−1 )2 = 3Fn2 + 2Fn−1 − Fn−2 2 2 2 = 3(Fn2 + Fn−1 ) − (Fn−1 + Fn−2 ) = 3F2n−1 − F2n−3 = F2n+1 .
#
/!
n−k n−2 n−1 n = Fn+1 , + ... + + + k 2 1 0
9 k = n/2 1 / # /T n = 0 n = 1 " n ≥ 2 /$ n ) K ) 9 # 9 $ /) / # L n−k n−2 n−1 n = + ... + + + k 2 1 0 n−3 n−3 n−2 n−2 + ... + + + =1+ 2 1 1 0 n−k−1 n−k−1 = + + k k−1 n−k−1 n−3 n−2 n−1 + + ... + + + = k 2 1 0 n−k−1 n−3 n−2 = + ... + + + k−1 1 0 = Fn + Fn−1 = Fn+1 .
# / K6 +L a = b = n − 1 $ K6 5L ) a = n$ b = n − 1 )9 # # " n = kmT m / # / m = 1 #T 9 m > 1$ K6 :L &8
9 / a = k(m − 1)$ b = k − 1 ! Fka = F(k−1)a Fa−1 + F(k−1)a+1 Fa / # & 9 # Fa # 3 ? #@ # 9 = $ 8 ) 8 =$ 9 Fn+1 Fn−1 − Fn2 = (−1)n $ Fn2 * / ( -
#" n / # &
= 0, 1
" n
≥ 2$
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
Fn = Fn−1 + Fn−2 = ⎛ ⎞ √ n−1 √ n−1 1 1+ 5 1− 5 ⎠+ =√ ⎝ − 2 2 5 ⎛ ⎞ √ n−2 √ n−2 1 1+ 5 1− 5 ⎠= +√ ⎝ − 2 2 5 ⎛ ⎞ √ n−2 √ n−2 √ √ 1 1− 5 1+ 5 1+ 5 1− 5 +1 + +1 ⎠= =√ ⎝ 2 2 2 2 5 √ n √ n 1 1+ 5 1− 5 . − =√ 2 2 5
#" n = 1 n = 2 J & $ 9 Ln = J )/$ 9 L1 = 1 = a + b,
A a b ! a=
√ 1+ 5 , 2
Ln =
√ √ 1− 5 1+ 5 +b . L2 = 3 = a 2 2
b=
√ 1− 5 , 2
√ n √ n 1+ 5 1− 5 + , 2 2
n / # & 9 9 # 9 # #"" KL /! %# ) & 7 $ & 9 6 ( & # 6& )9 #$ 9 & . &)) 9 %# n E √ √ 1 In = √ (2 + 2 5
5)n − (2 −
5)n .
#"# ) n = 1, 2, . . . , 10 $ n = 11 #! / 47 9 n 8 1 Fn ∼ √ 5
√ n 1+ 5 = (0, 447 . . . ) · (1, 618 . . . )n . 2
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
) & 9 /!
en/2−1 ∼ en/2−1 = (0, 367 . . . ) · (1, 648 . . . )n ,
& 9 (0, 367 . . . ) · (1, 648 . . . )n en/2−1 = (0, 822 . . . ) · (1, 018 . . . )n . ≈ Fn 0, 447 . . .
F 9 ) $ 7$ ? 9 =@ $ n
7-# #! / $ 6 0 + , ! '1
- A B /# ? A B @ $ ) $ 9 A B 8 - 9 # $ 7 # )) )9 / -" P(E) = 12 $ P(T ) = 13 -# F / P(s) # / -- F P(s) # $ s ∈ A ∩ B $ )$ P(s) # $ s ∈ A∪B $ s ∈/ A ∩ B $ 2' )
- (E, T ), (O, T ), (L, T ) ) &8
$ (E, O) ) (E, L) (O, L) ) &8
- P(∅ ∩ A) = P(∅) = 0 = P(∅) · P(A) A /
S 9 ! P(S ∩ A) = P(A) = P(S) · P(A) - " P(A) = |S||S| = |S|1 $ P(B) = |S||S| = |S|1 $ P(A ∩ B) = |S||S| = 1 = |S| = P(A) · P(B) - # # $ 9 / 8 )$ $ 361 K& 8$ 9 ) & #
$ ) 8L
88 ; $ 88 7 · 109 /365 K +, #L $ 8 ) / 8 ) $ 9 8 )/ $ ) 9 / 8 ) $ &8
$ # 9 $ 9 8 ) ! 1/3653 = 1/48 627 125 .
/ + 9 $ 88 2 000 000 000/48 627 125 ≈ 41 8) ? @ 8 ) n−1
n−1
n−2
n
n
n
2
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
5 =
$ 3
!
a = a · 1 = (−a) · (−1) KL
T KL ) T K L a = 0 " KL . b = am c = bn$ c = amn KL . b = am
c = an$ b + c = a(m + n) b − c = a(m − n) K L . b = am a, b > 0$ m > 0$ & m ≥ 1$ b ≥ a K L 3 #$ 9 a = 0 . a = 0$ b = am a = bn$ = a = amn$ mn = 1 ' 9 m = n = 1$ m = n = −1
# / /$ 9 a = cn b = cm$ r = b − aq = c(m − nq) - / /$ 9 b = am$ c = aq + r c = bt + s A& s =
= c − bt = (aq + r) − (am)t = (q − mt)a + r F 0 ≤ r < a$ s ÷ a r KL a2 − 1 = (a − 1)(a + 1) KL an − 1 = (a − 1)(an−1 + . . . + a + 1)
' + 4 ) (
" (#$ K9 )
8 9 L $ & 8 9 " '! 2 "" KL F p ) ab ) & $ ) a$ b ) & KL p | a(b/a)$ p a$ KL ) p | (b/a) "# " n = p1 p2 · · · pk T i pi ≥ 2$ n ≥ 2k "- . ri = rj $ ia−ja 9 # p$ ia−ja = (i−j)a a$ i−j 9 # p A 9 ri 8 F 8 0$ / ) p − 1$ 8 1, 2, . . . , p − 1 & / " . p ) $ / = $ + . n $ $ p ) $ n ) & ) ) p 9 "/ 2 9 #$ 9 9 √n 2 ! p ) $ J / t J ) n ) & $ k t . √n = a/b KL$ nbk = ak $ # & 9 p )$ 9 # k$ 9 A k
k
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
* '
# F k
= 200 $ = / 10k−1 10k ) #
) ) 8 9
10k−1 (9k − 10)10k−1 10k − = . k ln 10 (k − 1) ln 10 k(k − 1) ln 10
F 99$
1 9k − 10 =9− k−1 k−1 k $ k
) #
9 · 10k−1 . k ln 10
/ /$ 9 k # 10k − 10k−1 = 9 · 10k−1 $ 1 1 9 · 10k−1 ≈ . = k−1 k ln 10 · 9 · 10 (ln 10)k 2, 3k
5 6 / -
- 4 42 = 6T 4 24 − 2 = 14 - KL 2 /$ 9 9 p &
8 8 &$ 9 & $ a ) A & a A a | p$
a = 1 a = p . Kp =L & / $ k = 0 k = p$ / A 9 a = 1$ / KL 8 = K L . / p $ k 9 8$ 9 9 # p -" F p 8$ 9 8 $ & = , / / a # p )9 / A $ 9 a / $ 8 K E J 9 & 9 /$ 9 p ) L R ap − a )/$ p = 9 9 # A 9 p | ap − a -# 8 &$ 9 p a 8 a(2a)(3a) · · · ((p − 1)a) = = (p − 1)!ap−1 " ri ia p # ) & p / $ r1 r2 · · · rp−1 A )) (p − 1)!$ p 9 # (p − 1)!ap−1 − (p − 1)! = (p − 1)!(ap−1 − 1) F p ) $ # (p − 1)!$ & # 9 ap−1 − 1
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
lnko(a, b) ≤ a$ a #$ )/$ 9 lnko(a, b) = a KL " d = lnko(a, b) A d | a d | b$ d | b − a A 9 d # a b − a$ d ≤ ≤ lnko(a, b) & = / 9 # KL
KL " KL lnko(a/2, b) | (a/2)$ lnko(a/2, b) | aT lnko(a/2, b) 9 # a b$ lnko(a/2, b) ≤ lnko(a, b) & = 9 # 9 #$ &9 $ 9 lnko(a, b) ) $ lnko(a, b) | (a/2) KL lnko(a/2, b/2) | (a/2)$ 2lnko(a/2, b/2) | a . # )/$ 9 2 lnko(a/2, b/2) | b$ 2lnko(a/2, b/2) ≤ lnko(a, b) F & $ lnko(a, b) | a$ 12 lnko(a, b) | a/2 . #! 12 lnko(a, b) | b/2$ 12 lnko(a, b) ≤ lnko(a/2, b/2) # ' / ) $ ) & )$ 8 ) $ / ) 9 - . a b $ a ) & ) 8$ 8 a ) $ / b $ / /$ 8$ 9 ) b & ) A 8 ) a b & ) 8 % / / a ) $ 8 / ) ) 9 lnko lkkt ) ) / ) / KL 3 # KL " z = lnko(a, b, c)$ A = a/z$ B = b/z $ C = c/z A$ B C ) $ ) 9 A B 8 ) $ 9 / ) $ C $ 9 ) 8 &$ 9 B ) A ) 9 $ ) 6 7 $ 9 A B ) $ C 2 = A2 + B 2 66 + $ 9 R 9 C ) $ 9 . A ) $ A0 A = 2A0 R/ A20 =
C +B C −B . 2 2
T p ) $ # A0 A p (C + B)/2$ (C − B)/2 )) # F + C−B = C 9 $ / C+B 2 2 C+B C−B 2 − 2 = B 8 $ & 8$ A$ B C )
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
p ) A0 ) & J / k J & /9 A A20 & p )) 2k ) p (C + B)/2 (C − B)/2 ) & 8 2k )$
)9 F ) #$ 9 (C + B)/2 K (C − B)/2L ) & ) ) ) A ) $ 9 (C +B)/2 (C −B)/2 ! (C + B)/2 = x2 (C − B)/2 = y 2 & x y F &8 A $ B C x$ y ! B=
C −B C +B − = x2 − y 2 , 2 2 A = 2A0 = 2
C=
C −B C +B + = x2 + y 2 , 2 2
C +B C −B = 2xy. 2 2
a$ b c 8 )/$ 9 A $ B C z $ & 9 /
/
lnko(a, a + 1) = lnko(a, 1) = lnko(0, 1) = 1 3 Fn+1 Fn # ) Fn−1 R
lnko(Fn+1 , Fn ) = lnko(Fn , Fn−1 ) = . . . = lnko(F3 , F2 ) = 1 # 9 n − 1 ) 2 k / #T k = 1
8 &$ 9 k > 1T b = aq+r$ 1 ≤ r < a / / lnko(a, r) k − 1 ) $ /# & a ≥ Fk r ≥ Fk−1 A b = aq + r ≥ a + r ≥ Fk + Fk−1 = = Fk+1 #$ 9 lnko(a, b) = lnko(a−b, b) KL 7, ) KL ( K L lnko 10100 − 1, 10100 − 2 10100 − 1 ) KL < ) KL 8 ) K L - - + - - 5 & ) K L ) &
" 2
/ m = 54321 − 12345 = 41976 / 0 KL 9 /" a ≡ b (mod 0) $ 9 ! k
$ 9 a − b = 0 · k A $ 9 a − b = 0$ $ 9 a = b 9 / ) 9 /# KL " a = 2 b = 5 KL . ac ≡ bc (mod mc)$ mc | ac − bc$ 9 k $ ac − bc = kmc F c = 0$ $ 9 a − b = km$ a ≡ b (mod m)
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
/- #$ 9 x ≡ y (mod p) K ) L $ 9 xv ≡ yv (mod p)$ 9 $ 9 xu ≡ xv (mod p). K7- 7L . x ≡ 0 (mod p)$ K7- 7L 9 # p$ )/ 8 &$ 9 x ≡ 0 (mod p)$ $ 9 J / J u < v / /$ 9 p − 1 | v − u$ ) k v − u = k(p − 1) ?@ xp−1 ≡ 1 (mod p)$ / # xk(p−1) ≡ 1 (mod p)$ = ! xv = xu · xk(p−1) ≡ ≡ xu (mod p)$ K7- 7L # 2 ..
$ $ $ A = 1 ⊕ AT A B = A ⊕ B ⊕ A · B T AB = A · B " 2 · 0 ≡ 2 · 3 (mod 6)$ 0 ≡ 3 (mod 6) G $ 9
m = ab Ka, b > 1L 0 ≡ b (mod m)
// $ a · 0 ≡ a · b
(mod m)$
# / / 8! lnko(53, 234527) = lnko(53, 2) = lnko(1, 2) = 1.
A 2 2 = 234527 − 4425 · 53 )/ $ 7 ) ! 1 = 53 − 26 · 2 = 53 − 26(234527 − 4425 · 53) = 115051 · 53 − 26 · 234527.
F 1 ≡ 115051 · 53
(mod 234527)$ 1/53 = 115051 x ≡ 5, y ≡ 8 (mod 11) KL 11 | x2 − 2x = x(x − 2)$ 11 | x$ 11 | x − 2$ x ≡ 0 (mod 11) x ≡ 2 (mod 11) KL . #! #$ 9 23 | x2 − 4 = (x − 2)(x + 2)$ )/$ 9 x ≡ 2 (mod 23)$ x ≡ −2 (mod 23)
-
7 8 (
3
n K / ) L ! k k + 1T ) ) 3 # pi ) n pi K7 n L $ 8 9 9 pi $ pj ) $ pi $ pj pk 9 $ F / / ) $ pi n/pi $ pi pj n/(pi pj )$ pi $ pj pk n/(pi pj pk ) ' 8 )/$ 9 φ(n) = n −
n n n n n n − ... − + + + ... + − − .... p1 pr p1 p2 p1 p3 pr−1 pr p1 p2 p2
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
A K- ;L & '#$ = )/ $ 9 1 − p1 7 − p1 / A )/ 9 i
(−1)k
i
1 , pi1 · · · pik
) / ? @ 3" 3 9 $ 9 n 9 8 n1 , n2 , . . . , nn $ 8 $ 9 A a d )/$ 9 d # n$ 1 ≤ a ≤ d lnko(a, d) = 1 '
$ 9 )/ )) φ(d) ( / n 8 $ 3# n = 1, 2 7 8 &$ 9 n > 2 . k $ n − k T 9 ) & / $ ) n K n/2 8L ) φ(n)/2$ 9 nφ(n)/2 3- (8 - : 6 & " s1 , . . . , sk 1 b $ b9 ) T 9 k = φ(b) " ri si a p # ) 3 lnko(b, ri ) = 1$ 9 / p ) $ b ri #$ p si a $ 9 $ $ si a ) b9 F $ r1 , r2 , . . . , rk 8$ ri = rj / $ 9 b | si a − sj a = (si − sj )aT lnko(a, b) = = 1 ) $ 9 b | si − sj $ 9 r1 , r2 , . . . , rk 9 # s1 , s2 , . . . , sk $ 8 8 (s1 a)(s2 a) · · · (sk a) A (s1 a)(s2 a) · · · (sk a) = (s1 s2 · · · sk )ak ,
$ (s1 a)(s2 a) · · · (sk a) ≡ r1 r2 · · · rk = s1 s2 · · · sk (mod b).
& 9 / ! (s1 s2 · · · sk )ak ≡ s1 s2 · · · sk (mod b),
))!
b (s1 s2 · · · sk ) ak − 1 .
F s1 s2 . . . sk ) b9$ b | ak − 1$ ))
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
9 '
2 k / #T k = 1 " n = 2m + a$ 9 a ,$ 7 A m k − 1$ 2m & 2(k − 1) )9 # ' 8 2n = (2m )2 $ a = 0$ 2n = (2m )2 · 2$ a = 1 . 3 | a$ 3 | a561 − a . 3 a$ 3 | a2 − 1 ?@ $ 3 | (a2 )280 − 1 = a560 − 1 . #! 9 11 a$ 11 | a10 − 1$ 11 | (a10 )56 − 1 = a560 − 1 ' 8$ 9 17 a$ 17 | a16 − 1$ 17 | (a16 )35 − 1 = a560 − 1 % A*
" ) $
/ ( ) = & +$ 9 ) = < K / # 8 6 ? 8@L ) = & -6$ 77 ? 8@ / KL 3 $ ) & = ) ) KL 3 $ : & = ) $ 9 , & = ) K L 7+ K ? @L K L 9 · 7· ·5 · 3 · 1 = 945 K ? @L /" K L & n2 $ ) n /# KL & 7; $ & ! 9, 5, 3, 3, 2, 3, 1, 3, 2, 3 KL & 57 $ ) & 9, 5, 7, 5, 8, 3, 9, 5, 7, 4 /- 102 = 45 / 2( ) = 2190 // ' $ ' & ( F & , n − 1 $ 9 ) & 8$ & K L 0, 1, 2, 3, . . . n − 1 n − 1 & ) # ) 9 $ , & =9 $ 9 20 2
" : ; ..; . ) 4
/ 6 = $ - 7 & / n ) = 8 & 2n &
9 & 7 !
n(n−3) 2
% + .
n = 1 T n > 1 . / J / # & J (n − 1)n/2 + 1 / # 8 n $
n(n + 1) (n − 1)n +1+n= + 1. 2 2
2,? .
" " 7- 7
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
7- 7
5! 3*! 0+
( +!
' n ) $ & n − 1$ n4 $
& 6 K 77 7 & L 12 A/& /
n · (n − 1) +
n 4
·4
n n n n n −n+2 + +2= − n+ + 2 2 4 4 2 4
$ K ?8 @L / " f 9 8 & $ 9 8 9 A
& 2n 5 & = ) K ) ) L n2 6 & = ) K ) L 1 2
n n + 3n. ·4 =2 (2n) · 3 + 2 2
K # f + 1$ A/& / #
8 L )/$ 9 f + 1 + 2n + n2 = 2 n2 + 3n + 2$ f = n2 + n + 1 8'( ! )
1 $ 7- + 3 T 9 # 99 $ /
$ 9 K5 9 # 9 / - ) # 4 # ) & . 9 #$ 9 + 2 − 6 = = 5 F 6 9 $ 12 · 5 · 4 = 10 9 J
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
7- +
+ * % + ' '
" 1 / #T & n = 1 $ n > 1 8 &$ 9 n − 1 9 . / n $ 8 $ ) $ 8 " KL 1 / #T 7 T = / $ ) / KL A 9 ! ?&&@ " P ) $ ?&&@ 9 # 1 / & P && / $ 9 9 & 8 8 ) ) @) ' '
" & 9 ) 9 =
= . C $ ) ) /# ) ) = ) )$ C & )8 $ @) ' .(( '
"" 8 &$ 9 & ?#@ 5 1 // &8$ ) ?7@ $ ) ?+@ ?5@ $ # ) ) ?7@ A 9 $ & &8
8 &$ 9 & ?#@ 5 )) # //$ ?7@ A
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
$+@$ ?5@ 8 8 ?7@ ) ? 8@ A ) : 9 =
= + # ?#@ $ ? @ / K$ )) L A ) 9 "" & & 9 8$ 9 ) y K ?
@ 9 8L 8 & ) # & 9 ) 9 8 )) 8 ) $ & ) 9 $ 9 / $ / # # 8 """ 9 8$ 9 ) $ ) $ & d A ) 9 / $ 8 & d + 1 $ 8 / # ) J 9 8$ d ) d ""# . / d & = ) $ 8 & d + 1 A & KL 9 9 # 9 8
#= $= # . #! * 2 .. ,
# F )/ # " abc a ) 8
b$ ) c$ 9 a #" . H 9) /$ 6 ) - 9 9 H ) F & ! 9 L $ 6 8 ) # # 9 9 9 $ / L ) $ ) 9 9) / ## KL . L ) $ J L ) J $ 9 9 = # KL 9 8$ 9 6 ) $ / a$ b$ c d 8 &$ 9 $ ) a $ b$ c d 8 ) 9 ) 9 F 9) / $ K76 7 5 & L
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
#- KL ( ) T a = b ) 9 / ) 9/ $ 9 b 9 /$ = ) ) = KL 9 # 9 #$ K L #$ K L ) J / J KL#$ KL K L # 1 ! 9 K + ) 9 L ) / K ) L 9 # #/ " 7- 5 K L 1
2
4
6
3
2 5
4 5
7
6
1
3
7
7- 5
# 3 N 8 A ) F A 5 A . ) $ 9 ) * 8$ * A ', '
# N 8 a ) a ) n + 1 $ ) /$ J KL J & F n a # 8 ) $ a # 8 ) (n + 1)n 9 Ka 8 L n(n + 1)+ +1 = n2 + n + 1 ) # N 8 ) 9 $ + 9 K7- 6 L ( K L $ 9 ) K9 L ? 9 @ x + y + z = 1 ) / 001, 010, 100, 111 K
8L ) # " A 7, ) 102 +10+1 = 111 ) / 111 J 77 ) # J A 11 &)) 9 / $ 777 ? @ ) 111 11
111
=
473239787751081 11
> 101448
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
111
011 101
001
010 110 000
100
7- 6 9 8 A 9 )
# ) / J // & # Q " $ 9 X / # * B
#" 667$ 66 #" 2 J / C D J ) )
λ / $ . D /$ (v − 1)λ / )/$ C F / k − 1 /$ / 9 $ C $ (v − 1)λ/k A C ) / #"" KL . v = 6$ r = 3 k = 3$ K76 7L ) b = 6$ K76 +L# λ = 6/5 KL b = 8$ v = 16$ r = 3$ k = 6$ λ = 1 K ) 9 L #"# " b = v /$ C ) ) / / $ C A b = v$ k = v − 1$ r = v − 1 λ = v − 2 ** 8 -
## " A$ B C 5 $ / ' /$ A B $ / 9 D . #! ) E $ ACE $ ) F $ BCF / D$ E $ F ) 8 $ 9 / J / J D = E $ A D / K B $ C L " 9 G A / $ C D 8 $ / 9 ) G 9 K 9 9 /L . # 9 #$ 9 AF G BEG / ' 8 /$ D E $ 9 F 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
/ / = J J 9 / ## K76 +L r = (v − 1)/2$ K76 7L D b = v(v − 1)/6 F v − 1 ≥ 6$ )/$ 9 b ≥ v ##" 38 S 9 S " . # b = v(v − 1)/6$ S 9 # )
b =
v−1 2
v−1 2
6
−1
=
(v − 1)(v − 3) , 24
$ S 9 9 b − b = (v+1)(v−1) F 8 S 9 & ) S $ ) $ S S 8 9 (v+1)(v−1) = $ ) (v+1)/2 8 2 S 9 9 $ S 9 ) S 8 A /$ 9 S 9 S ### 7- : /
7- :
##- F < $ ) + 8 $ 6 ) 8 * C +
#- :;- 8 4 × 4 A &)) 9 #$ 9 4!&)) 9 8 A 9 $ 9 / = 9 8 9 9 , 7 + 5 # ) / 3!&)) 9 $ 9 = $ & 9 8 9 $ 9 ) , 7 + 5 . , /$ 9 / $ K # 9 L 9 8 . , 9
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
8$ 9 R )/! , 7 + 5 , 7 + 5 , 7 + 5 , 7 + 5 7 , 5 + 7 , 5 + 7 + 5 , 7 5 , + + 5 , 7 + 5 7 , + 5 , 7 + , 5 7 5 + 7 , 5 + , 7 5 , 7 + 5 + 7 , 4 9 6&)) 9 $ 9 & 4! · 3! · 4 = 576 8 / $ ! 9 7 + $ + 5 $ + 5 ) & 8$ )/ . #! 9 7 6$ + 6 )$ + 6 & )/ 8 9 / # 9 8 )9 # M K ) / 76 : ; & #L ' ? @ 8 4 × 4 #- A T ) / & K )9 L! , 7 + n − 2 n − 1 7 + 5 n − 1 , + 5 6 , 7 n − 1 , 7 n − 3 n − 2
#-"
7 + 5 7 + 5 + 5 7 5 7 + 5 7 + + 5 7 #-# F 9 7 /$ $ ) 6 #-- B 8 8$ / ) ) $ # 8 ) ) / &! , 7 + 5 , 7 + 5 + 5 , 7 5 + 7 , 7 , 5 + 5 + 7 , 7 , 5 + + 5 , 7 A ? @ )/! , : 7, 7: 77 76 7 6 75 < ; + - 5 7+ 4
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
#- . $ 0, 1, 2, 3 ) / # ) $ K76 4L K76 7+L ) 9 K2 / QL 9 8 9 $ 9 , 7 + 5 O 9 E , K ) & L$ 7$ + 5 #! + ) K76 7+L $ (2, 2) ) 3 9 & K 9 #! n × n & n − 1 ) L #-/ . K76 75L $ 76 : - & & 9 8$ 9 , 7 + 5 (0, 0)$ (1, 1)$ (2, 2) (3, 3) ) # $ 8 ) ) ! 9 7$ , K & , L$ 9 +$ 5 8 &$ 9 + 9 7$ + K7 & $ + )L$ 5 9 $ 9 ,
9 +$ ,$ 5$ 7 9 ! 9 ! + , 5 7 K K76 75L 9 L A/ 9 / / # F 8 J $ J & $ &8 ) K76 75L / # & $ ! 7 5 , + K K76 75L L 9 5 + 7 ,$ &8 (3, 1) ) . # 9 8$ 9 5 * 2!
# 8 &$ 9 # d9 # 2 /$ 9 # # 2d + 1 8 # '#! 9 u # ## v 2d )9 $ 8 w $ u# = )/$ 9 # & # 2d d / w ))= 9 u$ v$ $ 9 # d9 # . 9 8 )/$ & 2d 9 $ 8 # # J 2d 9 & / / & 9 # 9 # # . 7$ # # . 7 $ 9 # = $ 9 8 # # )/ . 7 $ $ # & # )
$ 9 9 ) 9 # , /$ # # )/ . 9 7 $ ) # & ) $
© Lovász László, Pelikán József, Vesztergombi Katalin
© Typotex Kiadó
G
# # . 9 7 $ & ) $ ) $ / 9 9 $ ) & ) # # )/ . 9 $ 9 # $ 7 ) , $
1# # > # 2