Kobonův trojúhelníkový problém - Kobon triangle problem

Nevyřešený problém v matematice:

Kolik nepřekrývajících se trojúhelníků lze vytvořit v uspořádání

{displaystyle k}

linky?

(více nevyřešených úloh z matematiky)

Kobonovy trojúhelníky generované 3, 4 a 5 přímými segmenty.

The Kobonův trojúhelníkový problém je nevyřešený problém v kombinatorická geometrie nejprve uvedl Kobon Fujimura. Problém vyžaduje největší číslo N(k) nepřekrývajících se trojúhelníků, jejichž strany leží na uspořádání k řádky. Variace problému zohledňují projektivní rovina spíše než euklidovskou rovinu a požadovat, aby trojúhelníky nebyly překročeny žádnými jinými liniemi uspořádání.^[1]

Saburo Tamura dokázal, že největší celé číslo nepřesahuje k(k - 2) / 3 poskytuje horní mez maximálního počtu nepřekrývajících se trojúhelníků realizovatelných pomocí k řádky.^[2] V roce 2007 zjistili Johannes Bader a Gilles Clément přísnější horní hranici, což dokazuje, že horní hranice Tamury nemohla být dosažena k shodné s 0 nebo 2 (mod 6).^[3] Maximální počet trojúhelníků je proto v těchto případech maximálně o jeden menší než Tamurův. Dokonalá řešení (řešení Kobonových trojúhelníků poskytující maximální počet trojúhelníků) jsou známá k = 3, 4, 5, 6, 7, 8, 9, 13, 15 a 17.^[4] Pro k = 10, 11 a 12, nejlepší známá řešení dosahují počtu trojúhelníků o jeden menší než horní mez.

Jak dokazují G. Clément a J. Bader,^[3] řešení pro k > 2 jsou ohraničeny výše

{displaystyle k (k-2) / 3}

, když k== {3, 5} (mod 6);

{displaystyle (k + 1) (k-3) / 3}

, když k== {0, 2} (mod 6);

{displaystyle (k ^ {2} -2k-2) / 3}

, když k== {1, 4} (mod 6).

(Funkce floor je řešena upozorněním, že výraz k(k - 2) je násobkem 3 v prvním případě a 2 více než násobkem 3 ve třetím případě; Clément a Bader pouze vylepšili vazbu na střední případ.)

Vzhledem k dokonalému řešení s k₀> 3 řádky, další čísla řešení Kobonova trojúhelníku najdete pro všechny k_i-hodnoty kde

{displaystyle k_ {n + 1} = 2cdot k_ {n} -1,}

použitím postupu D. Forge a J. L. Ramireze Alfonsina.^[1]^[5] Například řešení pro k₀ = 5 vede k maximálnímu počtu nepřekrývajících se trojúhelníků pro k = 5,9,17,33,65,...

k	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	OEIS
Tamura je horní hranice N(k)	1	2	5	8	11	16	21	26	33	40	47	56	65	74	85	96	107	120	133	A032765
Clément a Baderova horní hranice	1	2	5	7	11	15	21	26	33	39	47	55	65	74	85	95	107	119	133	-
nejznámější řešení	1	2	5	7	11	15	21	25	32	38	47	53	65	72	85	93	104	115	130	A006066