Задача Кобона про трикутник — невирішена задача з комбінаторної геометрії, яку сформулював Кодзабуро Фудзмура (Кобон), японський математик (1903—1983). Задача полягає у з'ясуванні, яке максимальне число трикутників, що не перекриваються, сторони якого належать конфігурації n прямих, можна утворити. Варіант задачі розглядається в проєктивній площині, а не в евклідовій площині, в цьому випадку вимагається, щоб трикутники не перетиналися іншими прямими.
Ідеальна конфігурація — це розташування прямих, які попарно перетинаються і кожен відрізок є стороною, а дві відповідні прямі є частиною щонайбільше двох пар трикутників, що мають спільну сторону.
Кобон знайшов найбільшу кількість трикутників , які не перекриваються та їх можна побудувати за допомогою ліній, тому трикутник Кобона визначається як один із трикутників, побудованих таким чином. Кілька перших — це 1, 2, 5, 7, 11, 15, 21, …
Аналітичний вираз для знаходження кількості трикутників вивів
Теорема Сабуро Тамура. забезпечує верхню межу максимальної кількості трикутників. Тому для 2,3, … перші кілька верхніх меж — це 2, 5, 8, 11, 16, 21, 26, 33, … .
Лема 1. Якщо (n mod 3) ∈ {0, 2}, то всі конфігурації, які відповідають верхній межі , є ідеальними конфігураціями. В цих випадках mod 3, а .
Лема 2. У ідеальній конфігурації усі екстремальні точки мають степінь 2.
Лема 3. Ідеальна конфігурація існує лише для непарних .
Г. Клемен та Дж. Бадер. знайшли більш чітку межу кількості трикутників Кобона:
Теорема Г. Клемена та Д. Бадера. Максимальна кількість трикутників Кобона для заданої кількості прямих в площині обмежені верхніми межами:
, де — індикатор функції. Тобто верхня межа за С.Тамури не можа бути досягнута для всіх з mod 6 mod 6.
Доведення. Відповідно до Леми 1 верхню межу можна досягти за допомогою конфігурацій, якщо mod 3 або mod 3. Але ці ідеальні конфігурації можливі тільки для непарного згідно Леми 3. Отже, для та не може досягати верхньої межі. Ці дві умови можна узагальнити як . Тоді:
А. Вайнберг знайшов конфігурацію для - 25 трикутників.
В 1967 р. конфігурацію з - 25 трикутників знайшов Б.Грюнбаум, а іншу конфігурацію - С.Хонма. Верхня межа означає, що максимум повинно бути 25 або 26 (невідомо, який). С.Хонма ілюстрував конфігурацію для - 32 трикутники, де 33 трикутники - це теоретично можливий максимум.
У 1996 році С.Грабарчуком і В.Кабановичем були знайдені два інші окремі рішення. У 1999 році В.Кабанович знайшов для , 38-трикутну конфігурацію (верхня межа дорівнює 40) і конфігурацію з 47 трикутників (яка відповідає верхній межі 47 трикутників).
Т.Судзукі знайшов конфігурацію для , яка є максимальною, оскільки вона задовольняє верхній межі .
Подальше дослідження виявило конфігурації для - 53 трикутників (верхня межа дорівнює 56), - 72 трикутники (74), а також - 85 трикутників - нове рішення, яке відповідає верхній межі.
Останній рядок таблиці показує нову прив'язку. Зірочка у рядку вказує оптимальні конфігурації на додаток до вже відомих оптимальних рішень (жирним шрифтом).
n | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
(n mod 6) | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 |
К(n) | 1 | 2 | 5 | 7 | 11 | 15 | 21 | 25 | 32 | 38 | 47 | 53 | 65 | 72 | 85 | 93 | 104 | 115 |
Верхня межа С.Тамури | 1 | 2 | 5 | 8 | 11 | 16 | 21 | 26 | 33 | 40 | 47 | 56 | 65 | 74 | 85 | 96 | 107 | 120 |
Верхня межа Г.Клемена та Д.Бадера | 1 | 2 | 5 | 7 | 11 | 15 | 21 | 26 | 33 | 39 | 47 | 55 | 65 | 74 | 85 | 95 | 107 | 119 |
Приклади
- 3 прямі дають один трикутник
- 4 прямі
- 5 прямих
- 6 прямих
- 7 прямих
Література
- K. Fujimura, The Tokyo Puzzle Charles Scribner's Sons, New York, 1978.
- M. Gardner, Wheels, Life, and Other Mathematical Amusements. W. H. Freeman, New York, pp. 170—171 and 178, 1983. [4] E. Pegg, Math Games: Kobon Triangles
- Weisstein, Eric W. Трикутники Кобона(англ.) на сайті Wolfram MathWorld.
- https://sop.tik.ee.ethz.ch/publicationListFiles/cb2007a.pdf [ 24 червня 2019 у Wayback Machine.]
- https://oeis.org/A006066 [ 24 листопада 2021 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Zadacha Kobona pro trikutnik nevirishena zadacha z kombinatornoyi geometriyi yaku sformulyuvav Kodzaburo Fudzmura Kobon yaponskij matematik 1903 1983 Zadacha polyagaye u z yasuvanni yake maksimalne chislo K displaystyle K trikutnikiv sho ne perekrivayutsya storoni yakogo nalezhat konfiguraciyi n pryamih mozhna utvoriti Variant zadachi rozglyadayetsya v proyektivnij ploshini a ne v evklidovij ploshini v comu vipadku vimagayetsya shob trikutniki ne peretinalisya inshimi pryamimi Idealna konfiguraciya ce roztashuvannya n displaystyle n pryamih yaki poparno peretinayutsya i kozhen vidrizok ye storonoyu a dvi vidpovidni pryami ye chastinoyu shonajbilshe dvoh par trikutnikiv sho mayut spilnu storonu Kobon znajshov najbilshu kilkist trikutnikiv K n displaystyle K n yaki ne perekrivayutsya ta yih mozhna pobuduvati za dopomogoyu n displaystyle n linij tomu trikutnik Kobona viznachayetsya yak odin iz trikutnikiv pobudovanih takim chinom Kilka pershih ce 1 2 5 7 11 15 21 Analitichnij viraz dlya znahodzhennya kilkosti trikutnikiv viviv Teorema Saburo Tamura K n n n 2 3 displaystyle K n frac n n 2 3 zabezpechuye verhnyu mezhu maksimalnoyi kilkosti trikutnikiv Tomu dlya 2 3 pershi kilka verhnih mezh ce 2 5 8 11 16 21 26 33 Lema 1 Yaksho n mod 3 0 2 to vsi konfiguraciyi yaki vidpovidayut verhnij mezhi K n n n 2 3 displaystyle K n frac n n 2 3 ye idealnimi konfiguraciyami V cih vipadkah n n 2 0 displaystyle n n 2 equiv 0 mod 3 a K n n n 2 3 displaystyle K n n n 2 3 Lema 2 U idealnij konfiguraciyi usi ekstremalni tochki mayut stepin 2 Lema 3 Idealna konfiguraciya isnuye lishe dlya neparnih n displaystyle n G Klemen ta Dzh Bader znajshli bilsh chitku mezhu kilkosti trikutnikiv Kobona Teorema G Klemena ta D Badera Maksimalna kilkist K n displaystyle K n trikutnikiv Kobona dlya zadanoyi kilkosti n displaystyle n pryamih v ploshini obmezheni verhnimi mezhami K n n n 2 3 I n nmod6 0 2 n displaystyle K n leq lfloor frac n n 2 3 rfloor I n n bmod 6 in 0 2 n de IA X displaystyle I A X indikator funkciyi Tobto verhnya mezha za S Tamuri ne mozha buti dosyagnuta dlya vsih z n 0 displaystyle n equiv 0 mod 6 n 2 displaystyle n equiv 2 mod 6 Dovedennya Vidpovidno do Lemi 1 verhnyu mezhu mozhna dosyagti za dopomogoyu konfiguracij yaksho n 0 displaystyle n equiv 0 mod 3 abo n 2 displaystyle n equiv 2 mod 3 Ale ci idealni konfiguraciyi mozhlivi tilki dlya neparnogo n displaystyle n zgidno Lemi 3 Otzhe dlya nmod3 0 2 displaystyle n bmod 3 in 0 2 ta n 0mod2 displaystyle n equiv 0 bmod 2 ne mozhe dosyagati verhnoyi mezhi Ci dvi umovi mozhna uzagalniti yak nmod6 0 2 displaystyle n bmod 6 in 0 2 Todi Bn n n 2 3 nmod6 3 5 n n 2 3 1 nmod6 0 2 n 1 23 nmod6 1 4 displaystyle B n begin cases frac n n 2 3 n bmod 6 in 3 5 frac n n 2 3 1 n bmod 6 in 0 2 frac n 1 2 3 n bmod 6 in 1 4 end cases A Vajnberg znajshov konfiguraciyu dlya n 10 displaystyle n 10 25 trikutnikiv V 1967 r konfiguraciyu z n 10 displaystyle n 10 25 trikutnikiv znajshov B Gryunbaum a inshu konfiguraciyu S Honma Verhnya mezha oznachaye sho maksimum povinno buti 25 abo 26 nevidomo yakij S Honma ilyustruvav konfiguraciyu dlya n 11 displaystyle n 11 32 trikutniki de 33 trikutniki ce teoretichno mozhlivij maksimum U 1996 roci S Grabarchukom i V Kabanovichem buli znajdeni dva inshi okremi rishennya U 1999 roci V Kabanovich znajshov dlya n 12 displaystyle n 12 38 trikutnu konfiguraciyu verhnya mezha dorivnyuye 40 i n 13 displaystyle n 13 konfiguraciyu z 47 trikutnikiv yaka vidpovidaye verhnij mezhi 47 trikutnikiv T Sudzuki znajshov konfiguraciyu dlya n 15 displaystyle n 15 yaka ye maksimalnoyu oskilki vona zadovolnyaye verhnij mezhi N 15 65 displaystyle N 15 65 Podalshe doslidzhennya viyavilo konfiguraciyi dlya n 14 displaystyle n 14 53 trikutnikiv verhnya mezha dorivnyuye 56 n 16 displaystyle n 16 72 trikutniki 74 a takozh n 17 displaystyle n 17 85 trikutnikiv nove rishennya yake vidpovidaye verhnij mezhi Ostannij ryadok tablici pokazuye novu priv yazku Zirochka u ryadku vkazuye optimalni konfiguraciyi na dodatok do vzhe vidomih optimalnih rishen zhirnim shriftom n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 n mod 6 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2K n 1 2 5 7 displaystyle 11 15 21 25 32 38 47 53 65 72 85 93 104 115Verhnya mezha S Tamuri 1 2 5 8 11 16 21 26 33 40 47 56 65 74 85 96 107 120Verhnya mezha G Klemena ta D Badera 1 2 5 7 11 15 21 26 33 39 47 55 65 74 85 95 107 119Prikladi3 pryami dayut odin trikutnik 4 pryami 5 pryamih 6 pryamih 7 pryamihLiteraturaK Fujimura The Tokyo Puzzle Charles Scribner s Sons New York 1978 M Gardner Wheels Life and Other Mathematical Amusements W H Freeman New York pp 170 171 and 178 1983 4 E Pegg Math Games Kobon Triangles Weisstein Eric W Trikutniki Kobona angl na sajti Wolfram MathWorld https sop tik ee ethz ch publicationListFiles cb2007a pdf 24 chervnya 2019 u Wayback Machine https oeis org A006066 24 listopada 2021 u Wayback Machine