Kobon triangle problem

Last updated October 11, 2023

Kobon triangles generated with 3, 4 and 5 straight line segments. Kobon triangles.gif — Kobon triangles generated with 3, 4 and 5 straight line segments.

Unsolved problem in mathematics:

How many non-overlapping triangles can be formed in an arrangement of $k$ lines?

The Kobon triangle problem is an unsolved problem in combinatorial geometry first stated by Kobon Fujimura (1903-1983). The problem asks for the largest number N(k) of nonoverlapping triangles whose sides lie on an arrangement of k lines. Variations of the problem consider the projective plane rather than the Euclidean plane, and require that the triangles not be crossed by any other lines of the arrangement.^[1]

Known upper bounds

Saburo Tamura proved that the number of nonoverlapping triangles realizable by $k$ lines is at most $\lfloor k(k-2)/3\rfloor$ . G. Clément and J. Bader proved more strongly that this bound cannot be achieved when $k$ is congruent to 0 or 2 (mod 6).^[2] The maximum number of triangles is therefore at most one less in these cases. The same bounds can be equivalently stated, without use of the floor function, as:

{\begin{cases}{\frac {1}{3}}k(k-2)&{\text{when }}k\equiv 3,5{\pmod {6}};\\{\frac {1}{3}}(k+1)(k-3)&{\text{when }}k\equiv 0,2{\pmod {6}};\\{\frac {1}{3}}(k^{2}-2k-2)&{\text{when }}k\equiv 1,4{\pmod {6}}.\end{cases}}

Solutions yielding this number of triangles are known when $k$ is 3, 4, 5, 6, 7, 8, 9, 13, 15 or 17.^[3] For k = 10, 11 and 12, the best solutions known reach a number of triangles one less than the upper bound.

Known constructions

Given an optimal solution with k₀> 3 lines, other Kobon triangle solution numbers can be found for all k_i-values where

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

by using the procedure by D. Forge and J. L. Ramirez Alfonsin.^[1] For example, the solution for k₀ = 5 leads to the maximal number of nonoverlapping triangles for k = 5, 9, 17, 33, 65, ....^{[ failed verification ]}

k	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	OEIS
Tamura's upper bound on N(k)	1	2	5	8	11	16	21	26	33	40	47	56	65	74	85	96	107	120	133	A032765
Clément and Bader's upper bound	1	2	5	7	11	15	21	26	33	39	47	55	65	74	85	95	107	119	133	-
best known solution	1	2	5	7	11	15	21	25	32	38	47	53	65	72	85	93	104	115	130	A006066

Examples

3 lines, 1 triangle
4 lines, 2 triangles
5 lines, 5 triangles
6 lines, 7 triangles
7 lines, 11 triangles

Related Research Articles

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor". Trapdoor functions are a special case of one-way functions and are widely used in public-key cryptography.

In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.

In mathematics a polydivisible number is a number in a given number base with digits abcde... that has the following properties:

Its first digit a is not 0.
The number formed by its first two digits ab is a multiple of 2.
The number formed by its first three digits abc is a multiple of 3.
The number formed by its first four digits abcd is a multiple of 4.
etc.

In number theory, the Kronecker symbol, written as $or, is a generalization of the Jacobi symbol to all integers . It was introduced by Leopold Kronecker.$

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi probable prime test.

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.

A Giuga number is a composite number n such that for each of its distinct prime factors p_i we have $, or equivalently such that for each of its distinct prime factors p i we have .$

The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r² ≡ n, where p is a prime: that is, to find a square root of n modulo p.

<span class="mw-page-title-main">Ordered Bell number</span> Number of weak orderings

In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of $elements. Weak orderings arrange their elements into a sequence allowing ties, such as might arise as the outcome of a horse race). Starting from, these numbers are$

In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as

Pocklington's algorithm is a technique for solving a congruence of the form

In the mathematical field of graph theory, the pancake graphP_n or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals.

In mathematics, specifically in number theory, Newman's conjecture is a conjecture about the behavior of the partition function modulo any integer. Specifically, it states that for any integers $m$ and $r$ such that $, the value of the partition function satisfies the congruence for infinitely many non-negative integers n . It was formulated by mathematician Morris Newman in 1960. It is unsolved as of 2020.$

References

1 2 Forge, D.; Ramírez Alfonsín, J. L. (1998), "Straight line arrangements in the real projective plane", Discrete and Computational Geometry , 20 (2): 155–161, doi: 10.1007/PL00009373 .
↑ "G. Clément and J. Bader. Tighter Upper Bound for the Number of Kobon Triangles. Draft Version, 2007" (PDF). Archived from the original (PDF) on 2017-11-11. Retrieved 2008-03-03.
↑ Ed Pegg Jr. on Math Games

External links

Johannes Bader, "Kobon Triangles"

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[forge-1] 1 2 Forge, D.; Ramírez Alfonsín, J. L. (1998), "Straight line arrangements in the real projective plane", Discrete and Computational Geometry , 20 (2): 155–161, doi: 10.1007/PL00009373 .

[bacl-2] "G. Clément and J. Bader. Tighter Upper Bound for the Number of Kobon Triangles. Draft Version, 2007" (PDF). Archived from the original (PDF) on 2017-11-11. Retrieved 2008-03-03.

[3] Ed Pegg Jr. on Math Games

[1]

[2]

[3]