Π‘ΡΠ΄ΠΎΠΊΡ ΠΈ Ρ ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Ρ
![Π Π΅ΡΠ΅ΡΠ°Ρ: Π‘ΡΠ΄ΠΎΠΊΡ ΠΈ Ρ
ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Ρ](https://gugn.ru/work/1320906/cover.png)
M-ΡΠ°ΡΠΊΡΠ°ΡΠΊΠ° Π³ΡΠ°ΡΠ° G — ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΠ΅ f ΠΌΠ΅ΠΆΠ΄Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ G ΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ {1, 2,…, Ρ}. Π’Π°ΠΊΠΎΠ΅ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΠ΅ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠΎΠΉ, Π΅ΡΠ»ΠΈ f (x) <>f (y) Π²ΡΡΠΊΠΈΠΉ ΡΠ°Π·, ΠΊΠΎΠ³Π΄Π° x ΠΈ y ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Π² G. ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ²Π΅ΡΠΎΠ² ΡΡΠ΅Π±ΠΎΠ²Π°Π²ΡΠΈΡ ΡΡ, ΡΡΠΎΠ±Ρ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎ ΠΎΠΊΡΠ°ΡΠΈΠ²Π°ΡΡ Π³ΡΠ°Π½ΠΈ Π³ΡΠ°ΡΠ° G Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Ρ ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠΈΡΠ»ΠΎ G ΠΈ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½Π½ΠΎΠ΅ x (G). ΠΠ΅ ΡΡΡΠ΄Π½ΠΎ Π²ΠΈΠ΄Π΅ΡΡ, ΡΡΠΎ ΡΡΠ΄ΠΎΠΊΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΡΠΎΠ±Π»Π΅ΠΌΠΎΠΉ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠΈ Π³ΡΠ°ΡΠ°… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
Π‘ΡΠ΄ΠΎΠΊΡ ΠΈ Ρ ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Ρ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠ’ΠΠΠ ΠΠΠ ΠΠΠΠΠΠΠΠ― ΠΠΠΠΠΠ¬Π‘ΠΠΠΠ ΠΠΠ ΠΠΠ‘ΠΠΠΠ ΠΠ‘ΠΠΠΠΠΠ’ΠΠΠ¬ΠΠΠΠ ΠΠΠΠΠ’ΠΠ’Π ΠΠΎΡΡΠ΄Π°ΡΡΡΠ²Π΅Π½Π½ΠΎΠ΅ ΡΡΡΠ΅ΠΆΠ΄Π΅Π½ΠΈΠ΅ ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΡ
" Π‘ΡΠ΅Π΄Π½ΡΡ ΠΎΠ±ΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½Π°Ρ ΡΠΊΠΎΠ»Π° № 22 Π³. ΠΠΎΠΌΠ΅Π»Ρ"
ΠΠΎΠ½ΠΊΡΡΡΠ½Π°Ρ ΡΠ°Π±ΠΎΡΠ°
" Π‘ΡΠ΄ΠΎΠΊΡ ΠΈ Ρ ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Ρ"
Π£ΡΠ΅Π½ΠΈΠΊΠ°
9Π ΠΊΠ»Π°ΡΡΠ° ΠΠ£Π Π‘ΠΠ¨№ 22 Π³. ΠΠΎΠΌΠ΅Π»Ρ ΠΡΠΎΠΌΡΠΊΠΎ ΠΠ»ΡΠΈ ΠΠ»Π΅ΠΊΡΠ΅Π΅Π²ΠΈΡΠ° ΠΠ°ΡΡΠ½ΡΠΉ ΡΡΠΊΠΎΠ²ΠΎΠ΄ΠΈΡΠ΅Π»Ρ ;
ΠΠΎΡΡΠΊΠΈΠΉ Π‘Π΅ΡΠ³Π΅ΠΉ ΠΠΈΡ Π°ΠΉΠ»ΠΎΠ²ΠΈΡ,
ΡΡΠΈΡΠ΅Π»Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ
ΠΠΎΡΡΠ΄Π°ΡΡΡΠ²Π΅Π½Π½ΠΎΠ³ΠΎ ΡΡΡΠ΅ΠΆΠ΄Π΅Π½ΠΈΡ ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΡ
Π‘ΠΠ¨ № 22 Π³. ΠΠΎΠΌΠ΅Π»Ρ ΠΠΎΠΌΠ΅Π»Ρ 2009
- ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅
- 1. Π₯ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Ρ
- 2. ΠΠΎΠ΄ΡΡΠ΅Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ ΡΡΠ΄ΠΎΠΊΡ
- ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
- Π‘ΠΏΠΈΡΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΡ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠΎΠ²
- ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅
ΠΠ΅ΡΠ²ΠΎΠ΅ ΡΠΏΠΎΠΌΠΈΠ½Π°Π½ΠΈΠ΅ ΠΎ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ°Ρ (Π² ΡΠ²ΡΠ·ΠΈ Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ ΠΊΠ°ΡΡΠΎΡΠ½ΡΡ Π·Π°Π΄Π°Ρ) ΠΎΡΠ½ΠΎΡΠΈΡΡΡ ΠΊ 1723 Π³. Π‘ΠΈΡΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΈΠ·ΡΡΠ΅Π½ΠΈΠ΅ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ² Π½Π°ΡΠ°Π»ΠΎΡΡ Ρ ΡΠ°Π±ΠΎΡ ΠΠΉΠ»Π΅ΡΠ°.
Π XVIII Π²Π΅ΠΊΠ΅, ΠΊΠΎΠ³Π΄Π° ΠΠΉΠ»Π΅Ρ Π²Π²Π΅Π» ΠΏΠΎΠ½ΡΡΠΈΠ΅ Π³ΡΠ΅ΠΊΠΎ-Π»Π°ΡΠΈΠ½ΡΠΊΠΈΡ (ΠΎΡΡΠΎΠ³ΠΎΠ½Π°Π»ΡΠ½ΡΡ ) ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ², ΠΎΠ½ΠΈ Π±ΡΠ»ΠΈ ΠΏΡΠΎΡΡΠΎ Π½ΠΎΠ²ΡΠΌΠΈ ΡΠΈΡΡΠΎ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΌΠΈ ΠΎΠ±ΡΠ΅ΠΊΡΠ°ΠΌΠΈ. Π Π΄Π°Π»ΡΠ½Π΅ΠΉΡΠ΅ΠΌ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΠ΅ ΠΈ ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎ ΠΎΡΡΠΎΠ³ΠΎΠ½Π°Π»ΡΠ½ΡΠ΅ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΡ Π½Π°ΡΠ»ΠΈ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΡ Π² ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ ΠΎΠ±Π»Π°ΡΡΡΡ .
Π ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠΈΠΊΠ΅ ΠΏΠΎΠ»Π½ΡΠ΅ ΡΠΈΡΡΠ΅ΠΌΡ ΠΎΡΡΠΎΠ³ΠΎΠ½Π°Π»ΡΠ½ΡΡ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ ΠΊΠΎΠ½Π΅ΡΠ½ΡΠΌ Π°ΡΡΠΈΠ½Π½ΡΠΌ ΠΈ ΠΏΡΠΎΠ΅ΠΊΡΠΈΠ²Π½ΡΠΌ ΠΏΠ»ΠΎΡΠΊΠΎΡΡΡΠΌ. ΠΠ°ΡΠΈΠ½ΡΠΊΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΠΏΡΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠΈ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ² Π ΡΠΌΠ° (ΡΡΡΠ½ΠΈΡΠΎΠ² ΠΈΠ³ΡΡ Π² Π±ΡΠΈΠ΄ΠΆ). Π ΠΊΠΎΠ½ΡΠ΅ XIX Π²Π΅ΠΊΠ° ΠΡΠ»ΠΈ ΠΏΠΎΠΊΠ°Π·Π°Π», ΡΡΠΎ ΡΠ°Π±Π»ΠΈΡΠ° ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠΉ Π³ΡΡΠΏΠΏΡ ΡΠ²Π»ΡΠ΅ΡΡΡ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΠΌ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠΌ. Π 30-Ρ Π³ΠΎΠ΄Π°Ρ XX Π²Π΅ΠΊΠ° Π²ΠΎΠ·Π½ΠΈΠΊΠ»ΠΎ ΠΏΠΎΠ½ΡΡΠΈΠ΅ ΠΊΠ²Π°Π·ΠΈΠ³ΡΡΠΏΠΏΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΠ΅ΠΉ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π»ΡΠ±ΠΎΠΉ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΠΉ ΠΊΠ²Π°Π΄ΡΠ°Ρ.
Π‘ΠΈΡΡΠ΅ΠΌΡ ΠΏΠΎΠΏΠ°ΡΠ½ΠΎ ΠΎΡΡΠΎΠ³ΠΎΠ½Π°Π»ΡΠ½ΡΡ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ² ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΠΏΡΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠΈ ΡΠ΅ΡΠΎΡΠ½ΡΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΈΠ½ΡΠ΅Π³ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π² Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ΅.
Π 30-Ρ Π³ΠΎΠ΄Π°Ρ XX Π²Π΅ΠΊΠ° Π . Π€ΠΈΡΠ΅Ρ ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠΈΠ» ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΠ΅ (ΠΈ ΠΎΡΡΠΎΠ³ΠΎΠ½Π°Π»ΡΠ½ΡΠ΅ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΠ΅) ΠΊΠ²Π°Π΄ΡΠ°ΡΡ Π΄Π»Ρ ΠΏΠ»Π°Π½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΡΠ΅Π»ΡΡΠΊΠΎΡ ΠΎΠ·ΡΠΉΡΡΠ²Π΅Π½Π½ΡΡ ΡΠΊΡΠΏΠ΅ΡΠΈΠΌΠ΅Π½ΡΠΎΠ².
ΠΡΠ΅ ΠΎΠ΄Π½Π° ΠΎΠ±Π»Π°ΡΡΡ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΡ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ² — ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΊΠΎΠ΄ΠΎΠ², ΠΈΡΠΏΡΠ°Π²Π»ΡΡΡΠΈΡ ΠΎΡΠΈΠ±ΠΊΠΈ.
ΠΡΡΠ΄ Π»ΠΈ ΠΠΉΠ»Π΅Ρ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π», ΡΡΠΎ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΡ Π±ΡΠ΄ΡΡ ΡΡΠΎΠ»Ρ ΡΠΈΡΠΎΠΊΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡΡΡ, ΠΎΠ΄Π½Π°ΠΊΠΎ Π΅Π³ΠΎ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΠΈΠ½ΡΡΠΈΡΠΈΡ ΠΏΠΎΠΌΠΎΠ³Π»Π° ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎ ΠΎΡΠ΅Π½ΠΈΡΡ Π΅ΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎΡΡΡ ΠΊΠΎΠ½ΡΡΡΡΠΊΡΠΈΠΈ ΠΈ Π½Π΅ΡΡΠΈΠ²ΠΈΠ°Π»ΡΠ½ΠΎΡΡΡ ΡΠ²ΠΎΠΉΡΡΠ² Π»Π°ΡΠΈΠ½ΡΠΊΠΈΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ².
ΠΠ΅ΠΆΠ΄Ρ Π³ΠΎΠ»ΠΎΠ²ΠΎΠ»ΠΎΠΌΠΊΠΎΠΉ ΡΡΠ΄ΠΎΠΊΡ ΠΈ Π»Π°ΡΠΈΠ½ΡΠΊΠΈΠΌΠΈ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ°ΠΌΠΈ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΏΡΡΠΌΠ°Ρ Π²Π·Π°ΠΈΠΌΠΎΡΠ²ΡΠ·Ρ: Π·Π°Π²Π΅ΡΡΠ΅Π½Π½Π°Ρ ΡΠ΅ΡΠΊΠ° ΡΡΠ΄ΠΎΠΊΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΡΠΌ ΡΠΈΠΏΠΎΠΌ Π»Π°ΡΠΈΠ½ΡΠΊΠΎΠ³ΠΎ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ° Ρ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡΡΡ — Π½ΠΈΠΊΠ°ΠΊΠΈΡ ΠΏΠΎΠ²ΡΠΎΡΡΡΡΠΈΡ ΡΡ ΡΠΈΡΠ΅Π» Π² Π»ΡΠ±ΠΎΠΌ Π±Π»ΠΎΠΊΠ΅ 3×3.
ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ, ΠΊΡΠΎ ΠΏΡΡΠ°Π»ΡΡ, ΡΠ΅ΡΠΈΡΡ Π·Π°Π΄Π°ΡΡ ΡΡΠ΄ΠΎΠΊΡ, Π΅ΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ Π²ΠΎΠΏΡΠΎΡΠΎΠ². ΠΠ»Ρ Π΄Π°Π½Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ, ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ? ΠΡΠ»ΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ, ΠΎΠ½ΠΎ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ΅? ΠΡΠ»ΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π½Π΅ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ΅, ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ Π΅ΡΡΡ? ΠΡΠΎΠΌΠ΅ ΡΠΎΠ³ΠΎ, Π΅ΡΡΡ ΡΠΈΡΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΡΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ Π²ΡΠ΅Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ? ΠΠ°ΠΊΠΎΠ²ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄Π°Π½Π½ΡΡ , Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΠΊΠΎΡΠΎΡΡΡ ΠΌΠΎΠΆΠ½ΠΎ Π³Π°ΡΠ°Π½ΡΠΈΡΠΎΠ²Π°ΡΡ ΡΠ½ΠΈΠΊΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅? Π Π±ΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²Π΅ Π·Π°Π΄Π°Ρ — ΠΌΠΈΠ½ΠΈΠΌΡΠΌ 17. ΠΠ΅ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎ Π² Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ, Π΅ΡΠ»ΠΈ Π·Π°Π΄Π°ΡΠ° Ρ 16 Π΄Π°Π½Π½ΡΠΌΠΈ, Π΄Π°ΡΡΠ΅Π΅ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. Gordon Royle ΡΠΎΠ±ΡΠ°Π» 36 628 Π·Π°Π΄Π°Ρ ΡΡΠ΄ΠΎΠΊΡ Ρ 17 ΡΠΈΡΠ»Π°ΠΌΠΈ, ΠΈΠΌΠ΅ΡΡΠΈΠ΅ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅.
ΠΡ ΠΏΠ΅ΡΠ΅ΡΠΎΡΠΌΡΠ»ΠΈΡΡΠ΅ΠΌ ΡΡΠΈ Π²ΠΎΠΏΡΠΎΡΡ Π² ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΊΠΎΠ½ΡΠ΅ΠΊΡΡΠ΅ ΠΈ ΠΏΠΎΠΏΡΡΠ°Π΅ΠΌΡΡ ΠΎΡΠ²Π΅ΡΠΈΡΡ Π½Π° Π½ΠΈΡ . ΠΠΎΠ»Π΅Π΅ ΡΠΎΡΠ½ΠΎ, ΠΌΡ ΠΈΠ½ΡΠ΅ΡΠΏΡΠ΅ΡΠΈΡΡΠ΅ΠΌ ΡΡΠ΄ΠΎΠΊΡ ΠΊΠ°ΠΊ Π·Π°Π΄Π°ΡΡ ΠΎΠΊΡΠ°ΡΠΈΠ²Π°Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½ Π² ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ². ΠΡΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ Π½Π°ΠΌ, ΠΎΠ±ΠΎΠ±ΡΠΈΡΡ Π²ΠΎΠΏΡΠΎΡΡ ΠΈ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡ ΠΈΡ Π² Π±ΠΎΠ»Π΅Π΅ ΡΠΈΡΠΎΠΊΠΎΠΌ ΡΠΌΡΡΠ»Π΅.
1. Π₯ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Ρ
m-ΡΠ°ΡΠΊΡΠ°ΡΠΊΠ° Π³ΡΠ°ΡΠ° G — ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΠ΅ f ΠΌΠ΅ΠΆΠ΄Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ G ΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ {1, 2,…, Ρ}. Π’Π°ΠΊΠΎΠ΅ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΠ΅ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠΎΠΉ, Π΅ΡΠ»ΠΈ f (x) <>f (y) Π²ΡΡΠΊΠΈΠΉ ΡΠ°Π·, ΠΊΠΎΠ³Π΄Π° x ΠΈ y ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Π² G. ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ²Π΅ΡΠΎΠ² ΡΡΠ΅Π±ΠΎΠ²Π°Π²ΡΠΈΡ ΡΡ, ΡΡΠΎΠ±Ρ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎ ΠΎΠΊΡΠ°ΡΠΈΠ²Π°ΡΡ Π³ΡΠ°Π½ΠΈ Π³ΡΠ°ΡΠ° G Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Ρ ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠΈΡΠ»ΠΎ G ΠΈ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½Π½ΠΎΠ΅ x (G). ΠΠ΅ ΡΡΡΠ΄Π½ΠΎ Π²ΠΈΠ΄Π΅ΡΡ, ΡΡΠΎ ΡΡΠ΄ΠΎΠΊΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΡΠΎΠ±Π»Π΅ΠΌΠΎΠΉ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠΈ Π³ΡΠ°ΡΠ°. ΠΠ° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅, ΠΌΡ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΠ΅ΠΌ Π³ΡΠ°Ρ Ρ ΡΠ΅ΡΠΊΠΎΠΉ 9×9 ΡΡΠ΄ΠΎΠΊΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ. ΠΡΠ°Ρ Π±ΡΠ΄Π΅Ρ ΠΈΠΌΠ΅ΡΡ 81 Π³ΡΠ°Π½ΠΈ Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ ΡΡΠ΅ΠΉΠΊΠ΅ Π² ΡΠ΅ΡΠΊΠ΅. ΠΠ²Π΅ ΡΠ΅ΡΠΊΠΈΡ Π³ΡΠ°Π½ΠΈ Π±ΡΠ΄ΡΡ ΡΠΌΠ΅ΠΆΠ½ΡΠΌΠΈ ΡΠΎΠ³Π΄Π° ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π° ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ ΡΡΠ΅ΠΉΠΊΠΈ Π² ΡΠ΅ΡΠΊΠ΅, ΡΠ°ΠΊΠΆΠ΅ Π² ΡΠΎΠΉ ΠΆΠ΅ ΡΡΡΠΎΡΠΊΠ΅, ΠΈΠ»ΠΈ ΡΠΎΠΉ ΠΆΠ΅ ΠΊΠΎΠ»ΠΎΠ½Π½Π΅, ΠΈΠ»ΠΈ ΡΠΎΠΉ ΠΆΠ΅ ΠΏΠΎΠ΄ΡΠ΅ΡΠΊΠ΅.
ΠΡ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ ΡΡΠΎΡ Π³ΡΠ°ΡΠ° Xn ΠΈ Π½Π°Π·ΡΠ²Π°Π΅ΠΌ ΡΡΠΎ Π³ΡΠ°Ρ ΡΡΠ΄ΠΎΠΊΡ ΡΠ°Π½Π³Π° n. ΠΠ²Π°Π΄ΡΠ°Ρ ΡΡΠ΄ΠΎΠΊΡ ΡΠ°Π½Π³Π° n Π±ΡΠ΄Π΅Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠΎΠΉ ΡΡΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°, ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π²ΡΠ΅Π³ΠΎ n2 ΡΠ²Π΅ΡΠ°. ΠΠ°Π΄Π°ΡΠ° ΡΡΠ΄ΠΎΠΊΡ ΠΈΠ½ΡΠ΅ΡΠΏΡΠ΅ΡΠΈΡΡΠ΅ΡΡΡ Π² ΡΠ°ΡΡΠΈΡΠ½ΡΡ ΡΠ°ΡΠΊΡΠ°ΡΠΊΡ, ΠΈ Π²ΠΎΠΏΡΠΎΡ ΡΠ²Π»ΡΠ΅ΡΡΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎ Π»ΠΈ ΠΎΡ ΡΡΠΎΠΉ ΡΠ°ΡΡΠΈΡΠ½ΠΎΠΉ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠΈ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠ° ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π·Π°Π²Π΅ΡΡΠ΅Π½Π°.
ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠΉ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠΈ Π³ΡΠ°ΡΠ° G Ρ m ΡΠ²Π΅ΡΠ°ΠΌΠΈ ΠΊΠ°ΠΊ Ρ ΠΎΡΠΎΡΠΎ ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎ Π±ΡΠ΄Π΅Ρ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠΌ Π² ΡΠΎ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ m ΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½ΡΡΡΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ Π³ΡΠ°Π½Π΅ΠΉ G.
Π’Π΅ΠΎΡΠ΅ΠΌΠ° 1. ΠΡΡΡΡ G Π±ΡΠ΄Π΅Ρ ΠΊΠΎΠ½Π΅ΡΠ½ΡΠΉ Π³ΡΠ°Ρ Ρ v Π³ΡΠ°Π½ΡΠΌΠΈ. ΠΡΡΡΡ, C Π±ΡΠ΄Π΅Ρ ΡΠ°ΡΡΠΈΡΠ½Π°Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ°Ρ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠ° t Π³ΡΠ°Π½Π΅ΠΉ G, ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π²ΡΠΈΡ d0 ΡΠ²Π΅ΡΠ°. ΠΡΡΡΡ pGC (m) Π±ΡΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠΉ, Π·Π°Π²Π΅ΡΡΠ°ΡΡΠΈΠΌ ΡΡΡ ΡΠ°ΡΠΊΡΠ°ΡΠΊΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ m ΡΠ²Π΅ΡΠ°ΠΌΠΈ, ΡΡΠΎΠ±Ρ ΠΏΠΎΠ»ΡΡΠ°ΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΡΡ ΡΠ°ΡΠΊΡΠ°ΡΠΊΡ G. Π’ΠΎΠ³Π΄Π°, pGC (m), ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ Ρ ΡΠ΅Π»ΡΠΌΠΈ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΠ°ΠΌΠΈ ΠΈ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ v-t Π΄Π»Ρ m>d0.
ΠΠ°Π½Π½Π°Ρ Π·Π°Π΄Π°ΡΠ° Sudoku (X3, C), ΠΈΠΌΠ΅Π΅Ρ ΡΠ½ΠΈΠΊΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΠΎΠ³Π΄Π° ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π° ΡΡΠΎ ΡΠΈΡΠ»ΠΎ pX3 C (9) = 1. ΠΡΠΎ Π±ΡΠ΄Π΅Ρ ΡΡΠ΅Π·Π²ΡΡΠ°ΠΉΠ½ΠΎ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΠ½ΡΠΌ, ΡΡΠΎΠ±Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΡΡ ΠΏΠΎΠ΄ ΠΊΠΎΡΠΎΡΡΠΌ ΡΡΠ»ΠΎΠ²ΠΈΡ ΡΠ°ΡΡΠΈΡΠ½Π°Ρ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠ° ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΡΠ°ΡΠΏΡΠΎΡΡΡΠ°Π½Π΅Π½Π° Π½Π° ΡΠ½ΠΈΠΊΠ°Π»ΡΠ½ΡΡ ΡΠ°ΡΠΊΡΠ°ΡΠΊΡ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ° 2. ΠΡΡΡΡ, G Π±ΡΠ΄Π΅Ρ Π³ΡΠ°Ρ Ρ Ρ ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΌ ΡΠΈΡΠ»ΠΎΠΌ x (G) ΠΈ C Π±ΡΠ΄Π΅Ρ ΡΠ°ΡΡΠΈΡΠ½Π°Ρ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠ° G, ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π²ΡΠ°Ρ ΡΠΎΠ»ΡΠΊΠΎ x (G) — 2 ΡΠ²Π΅ΡΠ°. ΠΡΠ»ΠΈ ΡΠ°ΡΡΠΈΡΠ½Π°Ρ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠ° ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π·Π°Π²Π΅ΡΡΠ΅Π½Π° Π² ΠΎΠ±ΡΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΡΡ ΡΠ°ΡΠΊΡΠ°ΡΠΊΡ G, ΡΠΎΠ³Π΄Π° Π΅ΡΡΡ ΠΏΠΎ ΠΊΡΠ°ΠΉΠ½Π΅ΠΉ ΠΌΠ΅ΡΠ΅ Π΄Π²Π° ΠΏΡΡΠΈ ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΡ ΡΠ°ΡΠΊΡΠ°ΡΠΊΠΈ.
2. ΠΠΎΠ΄ΡΡΠ΅Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ ΡΡΠ΄ΠΎΠΊΡ
ΠΡ ΠΊΡΠ°ΡΠΊΠΎ ΡΠ°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²ΠΎΠΏΡΠΎΡ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΡΡΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π΄Π»Ρ Π·Π°Π΄Π°ΡΠΈ Sudoku. Π Π½Π°ΡΠ°Π»Π΅ Π½Π΅ Π²ΡΠ΅Π³Π΄Π° ΡΡΠ½ΠΎ ΠΈΠΌΠ΅Π΅Ρ Π»ΠΈ Π΄Π°Π½Π½Π°Ρ Π·Π°Π΄Π°ΡΠ° ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. Π ΡΡΠΎΠΉ ΡΠ°ΡΡΠΈ, ΠΌΡ ΠΏΠΎΠ»ΡΡΠΈΠΌ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΡΠ΅ ΡΡΠ»ΠΎΠ²ΠΈΡ Π΄Π»Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ Π±ΡΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅.
ΠΠ° ΡΠΈΡΡΠ½ΠΊΠ΅ 1. ΠΏΡΠΈΠΌΠ΅Ρ Π·Π°Π΄Π°ΡΠΈ ΡΡΠ΄ΠΎΠΊΡ, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΈΠΌΠ΅Π΅Ρ ΡΠΎΡΠ½ΠΎ Π΄Π²Π° ΡΠ΅ΡΠ΅Π½ΠΈΡ.
ΠΡΠΎ Π½Π°Π±Π»ΡΠ΄Π΅Π½ΠΈΠ΅ Π»ΠΈΠ΄ΠΈΡΡΠ΅Ρ Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅Π΅ Π·Π°ΠΌΠ΅ΡΠ°Π½ΠΈΡ. ΠΡΠ»ΠΈ Π² ΡΠ΅ΡΠ΅Π½ΠΈΠΈ Π² Π·Π°Π΄Π°ΡΡ ΡΡΠ΄ΠΎΠΊΡ ΠΌΡ ΡΠΊΠ°Π·Π°Π»ΠΈ Π±Ρ, ΡΡΠΎ ΠΊΠΎΠ½ΡΠΈΠ³ΡΡΠ°ΡΠΈΡ Π½Π° ΡΠΈΡΡΠ½ΠΊΠ΅ 3 Π² ΡΠΎΠΌ ΠΆΠ΅ Π²Π΅ΡΡΠΈΠΊΠ°Π»ΡΠ½ΠΎΠΌ ΡΡΠ΅ΠΊΠ΅, ΡΠΎΠ³Π΄Π° ΠΏΠΎ ΠΊΡΠ°ΠΉΠ½Π΅ΠΉ ΠΌΠ΅ΡΠ΅ ΠΎΠ΄Π½ΠΎ ΠΈΠ· ΡΡΠΈΡ Π΄Π°Π½Π½ΡΡ Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ Π²ΠΊΠ»ΡΡΠ΅Π½Ρ ΠΊΠ°ΠΊ «Π΄Π°Π½Π½ΡΠΉ» Π² Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅, Π² ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅, Ρ Π½Π°Ρ Π±ΡΠ»ΠΎ Π±Ρ Π΄Π²Π° Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π² Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡΠΈΠ΅ ΠΏΡΠΎΡΡΠΎ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΎΠΉ a ΠΈ b Π² ΠΊΠΎΠ½ΡΠΈΠ³ΡΡΠ°ΡΠΈΠΈ.
ΠΠ°ΠΊ Π·Π°ΠΌΠ΅ΡΠ΅Π½ΠΎ ΡΠ°Π½Π΅Π΅, Π΅ΡΠ»ΠΈ ΡΠΎΡΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ «ΡΠ²Π΅ΡΠΎΠ²» ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΡ Π² Π΄Π°Π½Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅ ΡΡΠ΄ΠΎΠΊΡ — ΡΠ°ΠΌΠΎΠ΅ Π±ΠΎΠ»ΡΡΠ΅Π΅ ΡΠ΅ΠΌΡ, ΡΠΎΠ³Π΄Π° Π΅ΡΡΡ ΠΏΠΎ ΠΊΡΠ°ΠΉΠ½Π΅ΠΉ ΠΌΠ΅ΡΠ΅ Π΄Π²Π° ΡΠ΅ΡΠ΅Π½ΠΈΡ Π² Π·Π°Π΄Π°ΡΡ. ΠΡ ΠΎΡΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ ΡΡΠΎ Π±ΡΠ»ΠΎ ΡΠ°ΠΊΠΈΠΌ ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΌΡ ΠΌΠΎΠ³Π»ΠΈ Π²Π·Π°ΠΈΠΌΠΎΠΎΠ±ΠΌΠ΅Π½ Π΄Π²Π° Π½Π΅ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΡ ΡΠ²Π΅ΡΠ° ΠΈ Π²ΡΠ΅ Π΅ΡΠ΅ ΠΏΠΎΠ»ΡΡΠ°ΡΡ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅Π½Π½ΠΎΡΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ ΠΌΠΎΠΆΠ΅Ρ ΡΠ°ΠΊΠΆΠ΅ Π²ΠΈΠ΄Π½Π° ΠΈΠ· Ρ ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Π°. ΠΡΠ»ΠΈ d0 ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π²ΡΠΈΡ ΡΡ ΡΠ²Π΅ΡΠΎΠ², ΠΌΡ Π²ΠΈΠ΄Π΅Π»ΠΈ, ΡΡΠΎ pX3, C (m), ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ ΠΏΠΎ m, m> d0. Π’Π°ΠΊ ΠΊΠ°ΠΊ Ρ ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΡΠΈΡΠ»ΠΎ X3 = 9, ΠΌΡ Π΄ΠΎΠ»ΠΆΠ½Ρ ΠΈΠΌΠ΅ΡΡ pX 3 C (m) = 0 Π΄Π»Ρ m = d0, d0 + 1,…, 8. ΠΠ°ΠΊ pX 3C (m), ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ Ρ ΡΠ΅Π»ΡΠΌΠΈ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΠ°ΠΌΠΈ, ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ Π·Π°ΠΏΠΈΡΠ°ΡΡ pX3, C (m) = (m — d0) (m- (d0+ 1)) … (m-8) q (m), Π΄Π»Ρ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° q (Ρ) Ρ ΡΠ΅Π»ΡΠΌΠΈ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΠ°ΠΌΠΈ. ΠΡΠΈ m = 9 ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌ pX3, C (9) = (9-d0) Π=q (9) ΠΈ ΠΏΡΠ°Π²ΠΎ ΡΡΠΎΡΠΎΠ½Π½ΡΡ ΡΡΠΎΡΠΎΠ½Π° Π±ΠΎΠ»ΡΡΠ΅ ΠΈΠ»ΠΈ ΡΠ°Π²Π½Π° 2 Π΅ΡΠ»ΠΈ d0>= 7. ΠΡΠΎ Π΄Π°Π΅Ρ Π½Π°ΠΌ ΡΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½Π½ΠΎΠ΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎΠ΅ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ Π΄Π»Ρ ΡΠ°ΠΌ, ΡΡΠΎΠ±Ρ Π±ΡΠ»ΠΎ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, ΠΏΡΠΈ ΡΡΠ»ΠΎΠ²ΠΈΠΈ, ΡΡΠΎ Ρ Π·Π°Π΄Π°ΡΠΈ Π΅ΡΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅.
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
ΠΠ½ΡΠ΅ΡΠ΅ΡΠ½ΠΎ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ Π·Π°Π΄Π°ΡΠ° ΡΡΠ΄ΠΎΠΊΡ ΡΡΠ΅Π·Π²ΡΡΠ°ΠΉΠ½ΠΎ ΠΏΠΎΠΏΡΠ»ΡΡΠ½Π° ΠΏΠΎ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΠΌ ΠΏΡΠΈΡΠΈΠ½Π°ΠΌ. ΠΠ°ΡΠ»ΡΠΆΠΈΠ²Π°Π΅Ρ Π²Π½ΠΈΠΌΠ°Π½ΠΈΡ ΡΠΎ, ΡΡΠΎ ΡΡΠ° Π·Π°Π΄Π°ΡΠ° ΡΡΠ΄ΠΎΠΊΡ Π²ΡΠ·Π²Π°Π»Π° Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΏΡΠΎΠ±Π»Π΅ΠΌ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΠΏΡΠΈΡΠΎΠ΄Ρ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΏΠΎΠΊΠ° Π½Π΅ΡΠ΅ΡΠ΅Π½Ρ. ΠΡ ΡΠΆΠ΅ ΡΠΏΠΎΠΌΡΠ½ΡΠ»ΠΈ ΠΏΡΠΎΠ±Π»Π΅ΠΌΡ «ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΡΡΠ΄ΠΎΠΊΡ», Π³Π΄Π΅ ΠΌΡ ΡΠΏΡΠ°ΡΠΈΠ²Π°Π΅ΠΌ, Π΅ΡΠ»ΠΈ Π΅ΡΡΡ Π·Π°Π΄Π°ΡΠ° ΡΡΠ΄ΠΎΠΊΡ Ρ 16 ΠΈΠ»ΠΈ ΠΌΠ΅Π½ΡΡΠΈΠΌΠΈ Π΄Π°Π½Π½ΡΠΌΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ Π΄ΠΎΠΏΡΡΠΊΠ°ΡΡ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅.
ΠΡ ΡΠΆΠ΅ ΠΏΡΠΎΠΊΠΎΠΌΠΌΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π»ΠΈ ΡΡΠΎ, Π΅ΡΠ»ΠΈ ΡΠΎΠ»ΡΠΊΠΎ 7 ΠΈΠ»ΠΈ ΠΌΠ΅Π½ΡΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ²Π΅ΡΠΎΠ² ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Ρ, Π·Π°Π΄Π°ΡΠ° Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ.
ΠΡΠΈ Π²ΠΎΠΏΡΠΎΡΡ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»Π°Π³Π°ΡΡ Π±ΠΎΠ»Π΅Π΅ ΠΎΠ±ΡΠΈΠΉ Π²ΠΎΠΏΡΠΎΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ «ΠΌΠΈΠ½ΠΈΠΌΡΠΌΠ° ΡΡΠ΄ΠΎΠΊΡ» Π΄Π»Ρ ΠΎΠ±ΡΠ΅ΠΉ Π·Π°Π΄Π°ΡΠΈ ΡΠ°Π½Π³Π° n.
ΠΡ ΡΠΆΠ΅ ΠΎΡΠΌΠ΅ΡΠ°Π»ΠΈ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠ΅ ΡΠΈΠΌΠΌΠ΅ΡΡΠΈΠΈ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ² ΡΡΠ΄ΠΎΠΊΡ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΡΠΈΠΌΠ΅Π½ΡΡ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΡ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌ {1,2,…, n2}, ΠΌΡ ΠΏΠΎΠ»ΡΡΠΈΠΌ Π½ΠΎΠ²ΡΠΉ ΠΊΠ²Π°Π΄ΡΠ°Ρ ΡΡΠ΄ΠΎΠΊΡ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π½Π°ΡΠΈΠ½Π°Ρ Ρ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ°, ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ ΠΏΡΠΎΠΈΠ·Π²Π΅ΡΡΠΈ n2! Π½ΠΎΠ²ΡΡ ΡΡΠ΄ΠΎΠΊΡ. ΠΡΡΡ ΡΠ°ΠΊΠΆΠ΅ Π»Π΅Π½ΡΠΎΡΠ½ΡΠ΅ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΠΈΡ n!, Π° ΡΠ°ΠΊΠΆΠ΅ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΡΡΠΎΠ»Π±ΡΠΎΠ², ΠΊΠΎΡΠΎΡΡΡ ΡΠ°ΠΊΠΆΠ΅ n! ΠΡ ΠΌΠΎΠΆΠ΅ΠΌ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π²ΠΈΡΡ ΠΊΠΎΠ»ΠΎΠ½ΠΊΠΈ Π² ΠΏΡΠ΅Π΄Π΅Π»Π°Ρ ΠΏΠΎΠ»ΠΎΡΡ, Π° ΡΠ°ΠΊΠΆΠ΅ ΡΡΠΎΠ»Π±ΡΡ Π² ΠΏΡΠ΅Π΄Π΅Π»Π°Ρ ΡΡΠ΅ΠΊΠ° — n! n ΡΠΈΠΌΠΌΠ΅ΡΡΠΈΠΉ. Π ΠΈΡΠΎΠ³Π΅, ΡΡΠΎ Π³Π΅Π½Π΅ΡΠΈΡΡΠ΅Ρ Π³ΡΡΠΏΠΏΡ ΡΠΈΠΌΠΌΠ΅ΡΡΠΈΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½Ρ ΠΊΠ°ΠΊ ΠΏΠΎΠ΄Π³ΡΡΠΏΠΏΠ° Sn4. ΠΡΠ΄Π΅Ρ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΠ½ΡΠΌ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ ΡΠ°Π·ΠΌΠ΅Ρ ΠΈ ΡΡΡΡΠΊΡΡΡΡ ΡΡΠΎΠΉ ΠΏΠΎΠ΄Π³ΡΡΠΏΠΏΡ.
Π‘ΠΏΠΈΡΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΡ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠΎΠ²
S. Bammel and J. Rothstein, The number of 9 Π§ 9 Latin squares, Discrete Math.11 (1975), 93−95.
C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, J.comb. Theory Ser. B 48 (1990), no.1, 19−44.
B. Felgenhauer and A. F. Jarvis, Mathematics of Sudoku I, Mathematical Spectrum 39 (2006), 15−22.
E.russell and A. F. Jarvis, Mathematics of Sudoku II, Mathematical Spectrum 39 (2006), 54−58.
J. H. Van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.
ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅
Π ΠΈΡ. 1
Π ΠΈΡ. 2
Π ΠΈΡ. 3