ΠΠ΅ΡΠ΅Π²ΡΠ½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ.
ΠΠ°Π΄Π°ΡΠ° ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΠ΅ΡΠ° Π² ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠΈΠΊΠ΅ ΠΈ ΠΏΡΡΠΈ ΠΈΡ
ΡΠ΅ΡΠ΅Π½ΠΈΡ
ΠΡΡΡΡ ΠΈΠΌΠ΅Π΅ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ Π°Π»ΡΠ°Π²ΠΈΡ ΠΈ Π½Π°Π±ΠΎΡΡ ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² Π°Π»ΡΠ°Π²ΠΈΡΠ° (Π±ΡΠΊΠ²), Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΠ΅ ΡΠ»ΠΎΠ²Π°ΠΌΠΈ. ΠΡΠΊΠ²Ρ Π² Π°Π»ΡΠ°Π²ΠΈΡΠ΅ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Ρ: Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π² ΡΡΡΡΠΊΠΎΠΌ Π°Π»ΡΠ°Π²ΠΈΡΠ΅ ΠΏΠΎΡΡΠ΄ΠΎΠΊ Π±ΡΠΊΠ² Π°? Π±? Ρ (ΡΠΈΠΌΠ²ΠΎΠ»? ΡΠΈΡΠ°Π΅ΡΡΡ «ΠΏΡΠ΅Π΄ΡΠ΅ΡΡΠ²ΡΠ΅Ρ)». ΠΡΠ»ΠΈ Π·Π°Π΄Π°Π½ ΠΏΠΎΡΡΠ΄ΠΎΠΊ Π±ΡΠΊΠ², ΠΌΠΎΠΆΠ½ΠΎ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠΈΡΡ ΠΈ ΡΠ»ΠΎΠ²Π°. Π‘ΠΊΠ°ΠΆΠ΅ΠΌ, Π΄Π°Π½ΠΎ ΡΠ»ΠΎΠ²ΠΎ u=(u1,u2,., um) — ΡΠΎΡΡΠΎΡΡΠ΅Π΅ ΠΈΠ· Π±ΡΠΊΠ² u1, u2,., um — ΠΈ ΡΠ»ΠΎΠ²ΠΎ v =(v1,v2,., vb). Π’ΠΎΠ³Π΄Π° Π΅ΡΠ»ΠΈ u1? v1, ΡΠΎ ΠΈ u? v, Π΅ΡΠ»ΠΈ ΠΆΠ΅ u1=v1… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ΅ΡΠ΅Π²ΡΠ½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ. ΠΠ°Π΄Π°ΡΠ° ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΠ΅ΡΠ° Π² ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠΈΠΊΠ΅ ΠΈ ΠΏΡΡΠΈ ΠΈΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
Π’Π΅ΠΏΠ΅ΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠ±ΡΡΠ΄ΠΈΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΠ ΡΠ΅ΡΠ΅Π· ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π°. ΠΠ»Ρ ΠΊΡΠ°ΡΠΊΠΎΡΡΠΈ Π±ΡΠ΄Π΅Ρ Π½Π°Π·ΡΠ²Π°ΡΡ ΡΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π΄Π΅ΡΠ΅Π²ΡΠ½Π½ΡΠΌ.
ΠΠ½Π°ΡΠ°Π»Π΅ ΠΎΠ±ΡΡΠ΄ΠΈΠΌ ΡΠ²ΠΎΠΉΡΡΠ²ΠΎ ΡΠΏΡΡΠΌΠ»Π΅Π½ΠΈΡ. Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΊΠ°ΠΊΡΡ-Π½ΠΈΠ±ΡΠ΄Ρ ΡΠ΅ΠΏΡ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π½Π° ΡΠΈΡ. 5. ΠΡΠ»ΠΈ ΡΠΏΡΠ°Π²Π΅Π΄Π»ΠΈΠ²ΠΎ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ²ΠΎ ΡΡΠ΅ΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠ°, ΡΠΎ d[1,3]?d[1,2]+d[2,3] ΠΈ d[3,5]?d[3,4]+d[4,5]. Π‘Π»ΠΎΠΆΠΈΠ² ΡΡΠΈ Π΄Π²Π° Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ²Π°, ΠΏΠΎΠ»ΡΡΠΈΠΌ d[1,3]+d[3,5]?d[1,2]+d[2,3]+d[3,4]+d[4,5]. ΠΠΎ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ²Ρ ΡΡΠ΅ΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠ° ΠΏΠΎΠ»ΡΡΠΈΠΌ. d[1,5]?d[1,3]+d[3,5]. ΠΠΊΠΎΠ½ΡΠ°ΡΠ΅Π»ΡΠ½ΠΎ.
d[1,5] d[1,2]+d[2,3]+d[3,4]+d[4,5].
ΠΡΠ°ΠΊ, Π΅ΡΠ»ΠΈ ΡΠΏΡΠ°Π²Π΅Π΄Π»ΠΈΠ²ΠΎ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ²ΠΎ ΡΡΠ΅ΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠ°, ΡΠΎ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΠ΅ΠΏΠΈ Π²Π΅ΡΠ½ΠΎ, ΡΡΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΎΡ Π½Π°ΡΠ°Π»Π° Π΄ΠΎ ΠΊΠΎΠ½ΡΠ° ΡΠ΅ΠΏΠΈ ΠΌΠ΅Π½ΡΡΠ΅ (ΠΈΠ»ΠΈ ΡΠ°Π²Π½ΠΎ) ΡΡΠΌΠΌΠ°ΡΠ½ΠΎΠΉ Π΄Π»ΠΈΠ½Ρ Π²ΡΠ΅Ρ ΡΠ΅Π±Π΅Ρ ΡΠ΅ΠΏΠΈ. ΠΡΠΎ ΠΎΠ±ΠΎΠ±ΡΠ΅Π½ΠΈΠ΅ ΡΠ°ΡΡ ΠΎΠΆΠ΅Π³ΠΎ ΡΠ±Π΅ΠΆΠ΄Π΅Π½ΠΈΡ, ΡΡΠΎ ΠΏΡΡΠΌΠ°Ρ ΠΊΠΎΡΠΎΡΠ΅ ΠΊΡΠΈΠ²ΠΎΠΉ.
ΠΠ΅ΡΠ½Π΅ΠΌΡΡ ΠΊ ΠΠ ΠΈ ΠΎΠΏΠΈΡΠ΅ΠΌ ΡΠ΅ΡΠ°ΡΡΠΈΠΉ Π΅Π΅ Π΄Π΅ΡΠ΅Π²ΡΠ½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ.
ΠΠΎΡΡΡΠΎΠΈΠΌ Π½Π° Π²Ρ ΠΎΠ΄Π½ΠΎΠΉ ΡΠ΅ΡΠΈ ΠΠ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π΅ ΠΎΡΡΠΎΠ²Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ ΠΈ ΡΠ΄Π²ΠΎΠΈΠΌ Π²ΡΠ΅ Π΅Π³ΠΎ ΡΠ΅Π±ΡΠ°. ΠΠΎΠ»ΡΡΠΈΠΌ Π³ΡΠ°Ρ G — ΡΠ²ΡΠ·Π½ΡΠΉ ΠΈ Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ, ΠΈΠΌΠ΅ΡΡΠΈΠΌΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΡΠ΅ΡΠ½ΡΠ΅ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ.
ΠΠΎΡΡΡΠΎΠΈΠΌ ΡΠΉΠ»Π΅ΡΠΎΠ² ΡΠΈΠΊΠ» G, Π½Π°ΡΠΈΠ½Π°Ρ Ρ Π²Π΅ΡΡΠΈΠ½Ρ 1, ΡΠΈΠΊΠ» Π·Π°Π΄Π°Π΅ΡΡΡ ΠΏΠ΅ΡΠ΅ΡΠ½Π΅ΠΌ Π²Π΅ΡΡΠΈΠ½.
ΠΡΠΎΡΠΌΠΎΡΡΠΈΠΌ ΠΏΠ΅ΡΠ΅ΡΠ΅Π½Ρ Π²Π΅ΡΡΠΈΠ½, Π½Π°ΡΠΈΠ½Π°Ρ Ρ 1, ΠΈ Π±ΡΠ΄Π΅ΠΌ Π·Π°ΡΠ΅ΡΠΊΠΈΠ²Π°ΡΡ ΠΊΠ°ΠΆΠ΄ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΏΠΎΠ²ΡΠΎΡΡΠ΅Ρ ΡΠΆΠ΅ Π²ΡΡΡΠ΅ΡΠ΅Π½Π½ΡΡ Π² ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ. ΠΡΡΠ°Π½Π΅ΡΡΡ ΡΡΡ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΈ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠΎΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°.
ΠΡΠΈΠΌΠ΅Ρ 1. ΠΠ°Π½Π° ΠΏΠΎΠ»Π½Π°Ρ ΡΠ΅ΡΡ, ΠΏΠΎΠΊΠ°Π·Π°Π½Π½Π°Ρ Π½Π° ΡΠΈΡ. 5. ΠΠ°ΠΉΡΠΈ ΡΡΡ ΠΆΠ°Π΄Π½ΡΠΌ ΠΈ Π΄Π΅ΡΠ΅Π²ΡΠ½Π½ΡΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°ΠΌΠΈ.
Π ΠΈΡ 5.
ΠΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ.
Π’Π°Π±Π»ΠΈΡΠ°1
; | ||||||
; | ||||||
; | ||||||
; | ||||||
; | ||||||
; | ||||||
; | ||||||
Π ΠΈΡ.6
Π Π΅ΡΠ΅Π½ΠΈΠ΅. ΠΠ°Π΄Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ (ΠΈΠ΄ΠΈ Π² Π±Π»ΠΈΠΆΠ°ΠΉΡΠΈΠΉ Π³ΠΎΡΠΎΠ΄ ΠΈΠ· Π³ΠΎΡΠΎΠ΄Π° 1) Π΄Π°Π΅Ρ ΡΡΡ 1-(4)-3-(3)-5(5)-4-(11)-6-(10)-2-(6)-1, Π³Π΄Π΅ Π±Π΅Π· ΡΠΊΠΎΠ±ΠΎΠΊ ΠΏΠΎΠΊΠ°Π·Π°Π½Ρ Π½ΠΎΠΌΠ΅ΡΠ° Π²Π΅ΡΡΠΈΠ½, Π° Π² ΡΠΊΠΎΠ±ΠΊΠ°Ρ — Π΄Π»ΠΈΠ½Ρ ΡΠ΅Π±Π΅Ρ. ΠΠ»ΠΈΠ½Π° ΡΡΡΠ° ΡΠ°Π²Π½Π° 39, ΡΡΡ ΠΏΠΎΠΊΠ°Π·Π°Π½Π° Π½Π° ΡΠΈΡ. 5.
2. ΠΠ΅ΡΠ΅Π²ΡΠ½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π²Π½Π°ΡΠ°Π»Π΅ ΡΡΡΠΎΠΈΡ ΠΎΡΡΠΎΠ²Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ, ΠΏΠΎΠΊΠ°Π·Π°Π½Π½ΠΎΠ΅ Π½Π° ΡΠΈΡ. 6 ΡΡΡΠΈΡ ΠΎΠ²ΠΎΠΉ Π»ΠΈΠ½ΠΈΠ΅ΠΉ, Π·Π°ΡΠ΅ΠΌ ΡΠΉΠ»Π΅ΡΠΎΠ² ΡΠΈΠΊΠ» 1−2-1−3-4−3-5−6-5−3-1, Π·Π°ΡΠ΅ΠΌ ΡΡΡ 1−2-3−4-5−6-1 Π΄Π»ΠΈΠ½ΠΎΠΉ 43, ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠΎΠΊΠ°Π·Π°Π½ ΡΠΏΠ»ΠΎΡΠ½ΠΎΠΉ Π»ΠΈΠ½ΠΈΠ΅ΠΉ Π½Π° ΡΠΈΡ. 6.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΡ Π΄Π΅ΡΠ΅Π²ΡΠ½Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ°Π²Π½Π° 1.
ΠΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΡΡΡΠ²ΠΎ. ΠΠΎΠ·ΡΠΌΠ΅ΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΡΡ Π΄Π»ΠΈΠ½Ρ fB ΠΈ ΡΠ΄Π°Π»ΠΈΠΌ ΠΈΠ· Π½Π΅Π³ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ. ΠΠ»ΠΈΠ½Π° ΠΏΠΎΠ»ΡΡΠΈΠ²ΡΠ΅ΠΉΡΡ Π³Π°ΠΌΠΈΠ»ΡΡΠΎΠ½ΠΎΠ²ΠΎΠΉ ΡΠ΅ΠΏΠΈ LHC ΠΌΠ΅Π½ΡΡΠ΅ fB. ΠΠΎ ΡΡΡ ΠΆΠ΅ ΡΠ΅ΠΏΡ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ ΠΊΠ°ΠΊ ΠΎΡΡΠΎΠ²Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ, Ρ. ΠΊ. ΡΡΠ° ΡΠ΅ΠΏΡ Π΄ΠΎΡΡΠΈΠ³Π°Π΅Ρ Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈ Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ ΡΠΈΠΊΠ»ΠΎΠ². ΠΠ»ΠΈΠ½Π° ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° LMT ΠΌΠ΅Π½ΡΡΠ΅ ΠΈΠ»ΠΈ ΡΠ°Π²Π½Π° LHC. ΠΠΌΠ΅Π΅ΠΌ ΡΠ΅ΠΏΠΎΡΠΊΡ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ².
fB>LHC LMT (6).
ΠΠΎ ΡΠ΄Π²ΠΎΠ΅Π½Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ — ΠΎΠ½ΠΎ ΠΆΠ΅ ΡΠΉΠ»Π΅ΡΠΎΠ² Π³ΡΠ°Ρ — ΠΌΡ ΡΠ²Π΅Π»ΠΈ ΠΊ ΡΡΡΡ ΠΏΠΎΡΡΠ΅Π΄ΡΡΠ²ΠΎΠΌ ΡΠΏΡΡΠΌΠ»Π΅Π½ΠΈΠΉ, ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π΄Π»ΠΈΠ½Π° ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΠΎΠ³ΠΎ ΠΏΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΡΡΡΠ° ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΠ΅Ρ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ²Ρ.
2LMT>fA (7).
Π£ΠΌΠ½ΠΎΠΆΠ°Ρ (6) Π½Π° Π΄Π²Π° ΠΈ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡ Ρ (7), ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌ ΡΠ΅ΠΏΠΎΡΠΊΡ Π½Π΅ΡΠ°Π²Π΅Π½ΡΡΠ².
2fB>2LHC?2LMT?fA (8).
Π’.Π΅. 2fB>fA, Ρ. Π΅. fA/fB>1+?; ?=1.
Π’Π΅ΠΎΡΠ΅ΠΌΠ° Π΄ΠΎΠΊΠ°Π·Π°Π½Π°.
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΌΡ Π΄ΠΎΠΊΠ°Π·Π°Π»ΠΈ, ΡΡΠΎ Π΄Π΅ΡΠ΅Π²ΡΠ½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΎΡΠΈΠ±Π°Π΅ΡΡΡ ΠΌΠ΅Π½Π΅Π΅, ΡΠ΅ΠΌ Π² Π΄Π²Π° ΡΠ°Π·Π°. Π’Π°ΠΊΠΈΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΡΠΆΠ΅ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΏΡΠΈΠ±Π»ΠΈΠ·ΠΈΡΠ΅Π»ΡΠ½ΡΠΌΠΈ, Π° Π½Π΅ ΠΏΡΠΎΡΡΠΎ ΡΠ²ΡΠΈΡΡΠΈΡΠ΅ΡΠΊΠΈΠΌΠΈ.
ΠΠ·Π²Π΅ΡΡΠ½ΠΎ Π΅ΡΠ΅ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΏΡΠΎΡΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ², Π³Π°ΡΠ°Π½ΡΠΈΡΡΡΡΠΈΡ Π² Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ =1. ΠΠ»Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ Π½Π°ΠΉΡΠΈ ΡΡΠ΅Π΄ΠΈ Π½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΡΠΎΡΠ½Π΅Π΅, Π·Π°ΠΉΠ΄Π΅ΠΌ Ρ Π΄ΡΡΠ³ΠΎΠ³ΠΎ ΠΊΠΎΠ½ΡΠ° ΠΈ Π΄Π»Ρ Π½Π°ΡΠ°Π»Π° ΠΎΠΏΠΈΡΠ΅ΠΌ «brute-force enumeration» — «ΠΏΠ΅ΡΠ΅Π±ΠΎΡ ΠΆΠΈΠ²ΠΎΡΠ½ΠΎΠΉ ΡΠΈΠ»ΠΎΠΉ», ΠΊΠ°ΠΊ Π΅Π³ΠΎ Π½Π°Π·ΡΠ²Π°ΡΡ Π² Π°Π½Π³Π»ΠΎΡΠ·ΡΡΠ½ΠΎΠΉ Π»ΠΈΡΠ΅ΡΠ°ΡΡΡΠ΅. ΠΠΎΠ½ΡΡΠ½ΠΎ, ΡΡΠΎ ΠΏΠΎΠ»Π½ΡΠΉ ΠΏΠ΅ΡΠ΅Π±ΠΎΡ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ ΠΏΡΠΈΠΌΠ΅Π½ΠΈΠΌ ΡΠΎΠ»ΡΠΊΠΎ Π² Π·Π°Π΄Π°ΡΠ°Ρ ΠΌΠ°Π»ΠΎΠ³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ°. ΠΠ°ΠΏΠΎΠΌΠ½ΠΈΠΌ, ΡΡΠΎ ΠΠ Ρ n Π³ΠΎΡΠΎΠ΄Π°ΠΌΠΈ ΡΡΠ΅Π±ΡΠ΅Ρ ΠΏΡΠΈ ΠΏΠΎΠ»Π½ΠΎΠΌ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ΅ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½ΠΈΡ (n-1)!/2 ΡΡΡΠΎΠ² Π² ΡΠΈΠΌΠΌΠ΅ΡΡΠΈΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅ ΠΈ (n-1)! Π’ΡΡΠΎΠ² Π² Π½Π΅ΡΠΈΠΌΠΌΠ΅ΡΡΠΈΡΠ½ΠΎΠΉ, Π° ΡΠ°ΠΊΡΠΎΡΠΈΠ°Π», ΠΊΠ°ΠΊ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΉ ΡΠ°Π±Π»ΠΈΡΠ΅, ΡΠ°ΡΡΠ΅Ρ ΡΠ΄ΡΡΡΠ°ΡΡΠ΅ Π±ΡΡΡΡΠΎ:
5! | 10! | 15! | 20! | 25! | 30! | 35! | 40! | 45! | 50! |
~102. | ~106. | ~1012. | ~1018. | ~10 125. | ~1032. | ~1040. | ~1047. | ~1056. | ~1064. |
Π§ΡΠΎΠ±Ρ ΠΏΡΠΎΠ²ΠΎΠ΄ΠΈΡΡ ΠΏΠΎΠ»Π½ΡΠΉ ΠΏΠ΅ΡΠ΅Π±ΠΎΡ Π² ΠΠ, Π½ΡΠΆΠ½ΠΎ Π½Π°ΡΡΠΈΡΡΡΡ (ΡΠ°Π·ΡΠΌΠ΅Π΅ΡΡΡ, Π±Π΅Π· ΠΏΠΎΠ²ΡΠΎΡΠ΅Π½ΠΈΠΉ) Π³Π΅Π½Π΅ΡΠΈΡΠΎΠ²Π°ΡΡ Π²ΡΠ΅ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠΈΡΠ»Π° m ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΡΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΠΌΠΈ ΡΠΏΠΎΡΠΎΠ±Π°ΠΌΠΈ, Π½ΠΎ ΡΠ°ΠΌΡΠΉ ΡΠ°ΡΠΏΡΠΎΡΡΡΠ°Π½Π΅Π½Π½ΡΠΉ (Ρ.Π΅. ΠΏΡΠΈΠ»ΠΎΠΆΠΈΠΌΡΠΉ Π΄Π»Ρ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠ΅ΡΠ΅Π½ΠΈΡ Π΄ΡΡΠ³ΠΈΡ Π·Π°Π΄Π°Ρ) — ΡΡΠΎ ΠΏΠ΅ΡΠ΅Π±ΠΎΡ Π² Π»Π΅ΠΊΡΠΈΠΊΠΎΠ³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅.
ΠΡΡΡΡ ΠΈΠΌΠ΅Π΅ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ Π°Π»ΡΠ°Π²ΠΈΡ ΠΈ Π½Π°Π±ΠΎΡΡ ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² Π°Π»ΡΠ°Π²ΠΈΡΠ° (Π±ΡΠΊΠ²), Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΠ΅ ΡΠ»ΠΎΠ²Π°ΠΌΠΈ. ΠΡΠΊΠ²Ρ Π² Π°Π»ΡΠ°Π²ΠΈΡΠ΅ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Ρ: Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π² ΡΡΡΡΠΊΠΎΠΌ Π°Π»ΡΠ°Π²ΠΈΡΠ΅ ΠΏΠΎΡΡΠ΄ΠΎΠΊ Π±ΡΠΊΠ² Π°? Π±?Ρ (ΡΠΈΠΌΠ²ΠΎΠ»? ΡΠΈΡΠ°Π΅ΡΡΡ «ΠΏΡΠ΅Π΄ΡΠ΅ΡΡΠ²ΡΠ΅Ρ)». ΠΡΠ»ΠΈ Π·Π°Π΄Π°Π½ ΠΏΠΎΡΡΠ΄ΠΎΠΊ Π±ΡΠΊΠ², ΠΌΠΎΠΆΠ½ΠΎ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠΈΡΡ ΠΈ ΡΠ»ΠΎΠ²Π°. Π‘ΠΊΠ°ΠΆΠ΅ΠΌ, Π΄Π°Π½ΠΎ ΡΠ»ΠΎΠ²ΠΎ u=(u1,u2,., um) — ΡΠΎΡΡΠΎΡΡΠ΅Π΅ ΠΈΠ· Π±ΡΠΊΠ² u1, u2,., um — ΠΈ ΡΠ»ΠΎΠ²ΠΎ v =(v1,v2,., vb). Π’ΠΎΠ³Π΄Π° Π΅ΡΠ»ΠΈ u1? v1, ΡΠΎ ΠΈ u? v, Π΅ΡΠ»ΠΈ ΠΆΠ΅ u1=v1, ΡΠΎ ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡ Π²ΡΠΎΡΡΠ΅ Π±ΡΠΊΠ²Ρ ΠΈ Ρ. Π΄. ΠΡΠΎΡ ΠΏΠΎΡΡΠ΄ΠΎΠΊ ΡΠ»ΠΎΠ² ΠΈ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π»Π΅ΠΊΡΠΈΠΊΠΎΠ³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΌ. ΠΠΎΡΡΠΎΠΌΡ Π² ΡΡΡΡΠΊΠΈΡ ΡΠ»ΠΎΠ²Π°ΡΡΡ (Π»Π΅ΠΊΡΠΈΠΊΠΎΠ½Π°Ρ ) ΡΠ»ΠΎΠ²ΠΎ «Π°Π±Π°ΠΆΡΡ» ΡΡΠΎΠΈΡ ΡΠ°Π½ΡΡΠ΅ ΡΠ»ΠΎΠ²Π° «Π°Π±Π°ΠΊΠ°». Π‘Π»ΠΎΠ²ΠΎ «Π±ΡΡ» ΡΡΠΎΠΈΡ ΡΠ°Π½ΡΡΠ΅ ΡΠ»ΠΎΠ²Π° «Π±ΡΡΠ°», ΠΏΠΎΡΠΎΠΌΡ ΡΡΠΎ ΠΏΡΠΎΠ±Π΅Π» ΡΡΠΈΡΠ°Π΅ΡΡΡ ΠΏΡΠ΅Π΄ΡΠ΅ΡΡΠ²ΡΡΡΠΈΠΌ Π»ΡΠ±ΠΎΠΉ Π±ΡΠΊΠ²Π΅ Π°Π»ΡΠ°Π²ΠΈΡΠ°.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ, ΡΠΊΠ°ΠΆΠ΅ΠΌ, ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΠΈΠ· ΠΏΡΡΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½Π½ΡΡ ΡΠΈΡΡΠ°ΠΌΠΈ 1.5. ΠΠ΅ΠΊΡΠΈΠΊΠΎΠ³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈ ΠΏΠ΅ΡΠ²ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΎΠΉ ΡΠ²Π»ΡΠ΅ΡΡΡ 1−2-3−4-5, Π²ΡΠΎΡΠΎΠΉ — 1−2-3−5-4, …, ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΉ — 5−4-3−2-1. ΠΡΠΆΠ½ΠΎ ΠΎΡΠΎΠ·Π½Π°ΡΡ ΠΎΠ±ΡΠΈΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΡ Π»ΡΠ±ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ Π² Π½Π΅ΠΏΠΎΡΡΠ΅Π΄ΡΡΠ²Π΅Π½Π½ΠΎ ΡΠ»Π΅Π΄ΡΡΡΡΡ.
ΠΡΠ°Π²ΠΈΠ»ΠΎ ΡΠ°ΠΊΠΎΠ΅: ΡΠΊΠ°ΠΆΠ΅ΠΌ, Π΄Π°Π½Π° ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠ° 1−3-5−4-2. ΠΡΠΆΠ½ΠΎ Π΄Π²ΠΈΠ³Π°ΡΡΡΡ ΠΏΠΎ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅ ΡΠΏΡΠ°Π²Π° Π½Π°Π»Π΅Π²ΠΎ, ΠΏΠΎΠΊΠ° Π²ΠΏΠ΅ΡΠ²ΡΠ΅ Π½Π΅ ΡΠ²ΠΈΠ΄ΠΈΠΌ ΡΠΈΡΠ»ΠΎ, ΠΌΠ΅Π½ΡΡΠ΅Π΅, ΡΠ΅ΠΌ ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅Π΅ (Π² ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΡΡΠΎ 3 ΠΏΠΎΡΠ»Π΅ 5). ΠΡΠΎ ΡΠΈΡΠ»ΠΎ, Pi-1 Π½Π°Π΄ΠΎ ΡΠ²Π΅Π»ΠΈΡΠΈΡΡ, ΠΏΠΎΡΡΠ°Π²ΠΈΠ² Π²ΠΌΠ΅ΡΡΠΎ Π½Π΅Π³ΠΎ ΠΊΠ°ΠΊΠΎΠ΅-ΡΠΎ ΡΠΈΡΠ»ΠΎ ΠΈΠ· ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½ΡΡ ΠΏΡΠ°Π²Π΅Π΅, ΠΎΡ Pi Π΄ΠΎ Pn. Π§ΠΈΡΠ»ΠΎ Π±ΠΎΠ»ΡΡΠ΅Π΅, ΡΠ΅ΠΌ Pi-1, Π½Π΅ΡΠΎΠΌΠ½Π΅Π½Π½ΠΎ, Π½Π°ΠΉΠ΄Π΅ΡΡΡ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ Pi-1i-1. ΠΠ°ΡΠ΅ΠΌ ΡΠΈΡΠ»ΠΎ Pi-1 ΠΈ Π²ΡΠ΅ ΡΠΈΡΠ»Π° ΠΎΡ Pi Π΄ΠΎ Pn, Π½Π΅ ΡΡΠΈΡΠ°Ρ Pj Π½ΡΠΆΠ½ΠΎ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠΈΡΡ ΠΏΠΎ Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π½ΠΈΡ. Π ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΠΏΠΎΠ»ΡΡΠΈΡΡΡ Π½Π΅ΠΏΠΎΡΡΠ΅Π΄ΡΡΠ²Π΅Π½Π½ΠΎ ΡΠ»Π΅Π΄ΡΡΡΠ°Ρ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠ°, Π² ΠΏΡΠΈΠΌΠ΅ΡΠ΅ — 1−4-2−3-5. ΠΠΎΡΠΎΠΌ ΠΏΠΎΠ»ΡΡΠΈΡΡΡ 1−4-2−5-3 (ΡΠΎΡ ΠΆΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌ, Π½ΠΎ ΡΠΏΡΠΎΡΠ΅Π½Π½ΡΠΉ ΡΠ»ΡΡΠ°ΠΉ) ΠΈ Ρ. Π΄.
ΠΡΠΆΠ½ΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°ΡΡ, ΡΡΠΎ Π² ΠΠ Ρ n Π³ΠΎΡΠΎΠ΄Π°ΠΌΠΈ Π½Π΅ Π½ΡΠΆΠ½Ρ Π²ΡΠ΅ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΠΈΠ· n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΠΎΡΠΎΠΌΡ ΡΡΠΎ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ, ΡΠΊΠ°ΠΆΠ΅ΠΌ, 1−3-5−4-2 ΠΈ 3−5-4−2-1 (ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½ Ρ ΠΏΠ΅ΡΠ²ΡΠΌ) Π·Π°Π΄Π°ΡΡ ΠΎΠ΄ΠΈΠ½ ΠΈ ΡΠΎΡ ΠΆΠ΅ ΡΡΡ, ΡΡΠΈΡΠ°Π½Π½ΡΠΉ ΡΠΏΠ΅ΡΠ²Π° Ρ Π³ΠΎΡΠΎΠ΄Π° 1, Π° ΠΏΠΎΡΠΎΠΌ Ρ Π³ΠΎΡΠΎΠ΄Π° 3. ΠΠΎΡΡΠΎΠΌΡ Π½ΡΠΆΠ½ΠΎ Π·Π°ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°ΡΡ Π½Π°ΡΠ°Π»ΡΠ½ΡΠΉ Π³ΠΎΡΠΎΠ΄ 1 ΠΈ ΠΏΡΠΈΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡ ΠΊ Π½Π΅ΠΌΡ Π²ΡΠ΅ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΠΈΠ· ΠΎΡΡΠ°Π»ΡΠ½ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΡΠΎΡ ΠΏΠ΅ΡΠ΅Π±ΠΎΡ Π΄Π°ΡΡ (n-1)! ΡΠ°Π·Π½ΡΡ ΡΡΡΠΎΠ², Ρ. Π΅. ΠΏΠΎΠ»Π½ΡΠΉ ΠΏΠ΅ΡΠ΅Π±ΠΎΡ Π² Π½Π΅ΡΠΈΠΌΠΌΠ΅ΡΡΠΈΡΠ½ΠΎΠΉ ΠΠ (ΠΌΡ ΠΏΠΎ-ΠΏΡΠ΅ΠΆΠ½Π΅ΠΌΡ Π±ΡΠ΄Π΅ΠΌ ΡΠ°Π·Π»ΠΈΡΠ°ΡΡ ΡΡΡΡ 1−3-5−4-2 ΠΈ 1−2-4−5-3).
ΠΠ°Π½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΎΠΏΠΈΡΠ°Π½ Π½Π° ΡΠ·ΡΠΊΠ΅ ΠΠ°ΡΠΊΠ°Π»Ρ (ΡΠΌ. ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ).
ΠΡΠΈΠΌΠ΅Ρ 2. Π Π΅ΡΠΈΠΌ ΠΠ, ΠΏΠΎΡΡΠ°Π²Π»Π΅Π½Π½ΡΡ Π² ΠΡΠΈΠΌΠ΅ΡΠ΅ 1 Π»Π΅ΠΊΡΠΈΠΊΠΎΠ³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΌ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠΎΠΌ. ΠΡΠΈΠ²Π΅Π΄Π΅Π½Π½Π°Ρ Π²ΡΡΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° Π½Π°ΠΏΠ΅ΡΠ°ΡΠ°Π΅Ρ Π³ΠΎΡΠΎΠ΄Π°, ΡΠΎΡΡΠ°Π²Π»ΡΡΡΠΈΠ΅ Π»ΡΡΡΠΈΠΉ ΡΡΡ: 1−2-6−5-4−3 ΠΈ Π΅Π³ΠΎ Π΄Π»ΠΈΠ½Ρ 36.
ΠΠ΅Π»Π°ΡΠ΅Π»ΡΠ½ΠΎ ΡΡΠΎΠ²Π΅ΡΡΠ΅Π½ΡΡΠ²ΠΎΠ²Π°ΡΡ ΠΏΠ΅ΡΠ΅Π±ΠΎΡ, ΠΏΡΠΈΠΌΠ΅Π½ΠΈΠ² ΡΠ°Π·ΡΠΌ. Π ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ ΠΏΡΠ½ΠΊΡΠ΅ ΠΎΠΏΠΈΡΠ°Π½ Π°Π»Π³ΠΎΡΠΈΡΠΌ, ΠΊΠΎΡΠΎΡΡΠΉ ΡΠ΅Π°Π»ΠΈΠ·ΡΠ΅Ρ ΠΏΡΠΎΡΡΡΡ, Π½ΠΎ ΡΠΈΡΠΎΠΊΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΠΈΠΌΡΡ ΠΈ ΠΎΡΠ΅Π½Ρ ΠΏΠΎΠ»Π΅Π·Π½ΡΡ ΠΈΠ΄Π΅Ρ.