No-three-in-line problem (original) (raw)
El problema de sin tres en línea en geometría discreta plantea la cuestión de cuántos puntos se pueden colocar en una cuadrícula de para que no haya tres puntos en la misma línea recta. Este número está limitado a como máximo, porque puntos situados sobre los elementos de una cuadrícula incluirían necesariamente una fila con tres o más puntos, debido al conocido principio del palomar. El problema fue introducido por Henry Dudeney en 1900. Brass, Moser y Pach lo denominaron "una de las cuestiones geométricas más antiguas y más estudiadas de puntos colocados sobre una red".
| Property | Value |
|---|---|
| dbo:abstract | El problema de sin tres en línea en geometría discreta plantea la cuestión de cuántos puntos se pueden colocar en una cuadrícula de para que no haya tres puntos en la misma línea recta. Este número está limitado a como máximo, porque puntos situados sobre los elementos de una cuadrícula incluirían necesariamente una fila con tres o más puntos, debido al conocido principio del palomar. El problema fue introducido por Henry Dudeney en 1900. Brass, Moser y Pach lo denominaron "una de las cuestiones geométricas más antiguas y más estudiadas de puntos colocados sobre una red". Aunque el problema se ha podido resolver con puntos por cada hasta al menos , se conjetura que se pueden colocar menos de puntos en cuadrículas de gran tamaño. Los métodos conocidos pueden colocar linealmente muchos puntos en cuadrículas de tamaño arbitrario, pero el mejor de estos métodos coloca un poco menos de puntos, pero no . Aunque su origen procede de la matemática recreativa, el problema tiene aplicaciones en dibujo de grafos y en el . (es) The no-three-in-line problem in discrete geometry asks how many points can be placed in the grid so that no three points lie on the same line. This number is at most , because points in a grid would include a row of three or more points, by the pigeonhole principle. The problem was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points". Although the problem can be solved with points for every up to , it is conjectured that fewer than points can be placed in grids of large size. Known methods can place linearly many points in grids of arbitrary size, but the best of these methods place slightly fewer than points, not . Several related problems of finding points with no three in line, among other sets of points than grids, have also been studied. Although originating in recreational mathematics, the problem has applications in graph drawing and to the Heilbronn triangle problem. (en) Задача «никакие три точки не лежат на одной прямой» из комбинаторной геометрии. Её формулировка звучит следующим образом: сколько точек можно расположить на решётке так, чтобы никакие три точки не находились на одной прямой. Обнаружено, что их число не превосходит , поскольку при точек должна появиться строка с тремя или более точками согласно принципу Дирихле. Задачу описал в 1900 году. Брасс, Мозер и Пах назвали её «одним из самых старых и интенсивно изучаемых геометрических вопросов, касающихся точек решётки». Хотя проблему можно решить с точками для любого до , есть гипотеза, что на решётках большего размера можно разместить менее точек. Известные методы могут разместить линейное количество точек на решётке произвольного размера, но лучшие методы размещают меньше, чем точек, а совсем не . Изучались также проблемы поиска точек, среди которых никакие три не находятся на одной прямой, включая множества точек, отличные от решёток. Хотя первоначально проблема появилась как задача занимательной математики, она имеет приложение в визуализации графов и в . (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/No-three-in-line.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.mathpuzzle.com/MAA/36-Chessboard%20Tasks/mathgames_04_11_05.html https://www.quantamagazine.org/20160531-set-proof-stuns-mathematicians/ http://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html https://people.math.sc.edu/cooper/collinearpre.pdf https://archive.org/stream/amusementsinmath00dude%23page/222/mode/2up https://archive.org/stream/amusementsinmath00dude%23page/94/mode/2up https://books.google.com/books%3Fid=cT7TB20y3A8C&pg=PA417 https://eudml.org/doc/174999 https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz |
| dbo:wikiPageID | 2252579 (xsd:integer) |
| dbo:wikiPageLength | 30059 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120956451 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scientific_American dbr:Entropy_compression dbr:Prime_gap dbr:Algorithmica dbc:Mathematical_problems dbr:Approximation_algorithm dbr:Paul_Erdős dbr:Upper_bound dbr:Vector_space dbr:Degeneracy_(mathematics) dbr:International_Symposium_on_Graph_Drawing dbr:Line_segment dbc:Conjectures dbr:Complete_graph dbr:Mathematische_Zeitschrift dbr:Chessboard dbr:General_position dbr:Graph_coloring dbc:Lattice_points dbr:NP-hard dbr:SIAM_Journal_on_Computing dbr:Computational_Geometry_(journal) dbr:Computational_geometry dbr:Periodic_boundary_conditions dbr:Torus dbr:Algebraic_notation_(chess) dbr:American_Mathematical_Monthly dbc:Combinatorics dbr:Edge_(graph_theory) dbr:Finite_field dbr:Discrete_Mathematics_(journal) dbr:Discrete_geometry dbr:Graph_drawing dbr:Israel_Journal_of_Mathematics dbr:Journal_of_Combinatorial_Theory dbr:Heilbronn_triangle_problem dbr:Henry_Dudeney dbr:Hyperbola dbr:Fixed-parameter_tractable dbr:Prime_number dbr:Superset dbr:Recreational_mathematics dbr:Salem–Spencer_set dbr:Martin_Gardner dbr:Pick's_theorem dbr:Pigeonhole_principle dbr:Greedy_algorithm dbr:Approximation_ratio dbr:Canadian_Mathematical_Bulletin dbr:Cap_set dbr:Hypersphere dbr:Utility_graph dbr:Vertex_(graph_theory) dbr:Journal_of_the_London_Mathematical_Society dbr:Parameterized_complexity dbr:Polynomial-time dbr:APX-hard dbr:File:No-three-in-line.svg dbr:File:Erdős-no-3-in-line-12x12.svg |
| dbp:title | No-Three-in-a-Line-Problem (en) |
| dbp:urlname | No-Three-in-a-Line-Problem (en) |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Cite_magazine dbt:Cite_web dbt:Good_article dbt:Harvtxt dbt:Math dbt:Mathworld dbt:Mvar dbt:OEIS dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfn dbt:Sfnp dbt:Short_description dbt:Oeis dbt:Bi |
| dct:subject | dbc:Mathematical_problems dbc:Conjectures dbc:Lattice_points dbc:Combinatorics |
| gold:hypernym | dbr:Collinear |
| rdf:type | yago:WikicatConjectures yago:WikicatMathematicalProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Cognition100023271 yago:Concept105835747 yago:Condition113920835 yago:Content105809192 yago:Difficulty114408086 yago:Hypothesis105888929 yago:Idea105833840 yago:Problem114410605 yago:PsychologicalFeature100023100 yago:Speculation105891783 yago:State100024720 |
| rdfs:comment | El problema de sin tres en línea en geometría discreta plantea la cuestión de cuántos puntos se pueden colocar en una cuadrícula de para que no haya tres puntos en la misma línea recta. Este número está limitado a como máximo, porque puntos situados sobre los elementos de una cuadrícula incluirían necesariamente una fila con tres o más puntos, debido al conocido principio del palomar. El problema fue introducido por Henry Dudeney en 1900. Brass, Moser y Pach lo denominaron "una de las cuestiones geométricas más antiguas y más estudiadas de puntos colocados sobre una red". (es) The no-three-in-line problem in discrete geometry asks how many points can be placed in the grid so that no three points lie on the same line. This number is at most , because points in a grid would include a row of three or more points, by the pigeonhole principle. The problem was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points". Although originating in recreational mathematics, the problem has applications in graph drawing and to the Heilbronn triangle problem. (en) Задача «никакие три точки не лежат на одной прямой» из комбинаторной геометрии. Её формулировка звучит следующим образом: сколько точек можно расположить на решётке так, чтобы никакие три точки не находились на одной прямой. Обнаружено, что их число не превосходит , поскольку при точек должна появиться строка с тремя или более точками согласно принципу Дирихле. Задачу описал в 1900 году. Брасс, Мозер и Пах назвали её «одним из самых старых и интенсивно изучаемых геометрических вопросов, касающихся точек решётки». (ru) |
| rdfs:label | Problema de sin tres en línea (es) No-three-in-line problem (en) Задача «никакие три на прямой» (ru) |
| owl:sameAs | freebase:No-three-in-line problem yago-res:No-three-in-line problem wikidata:No-three-in-line problem dbpedia-es:No-three-in-line problem dbpedia-ru:No-three-in-line problem dbpedia-th:No-three-in-line problem https://global.dbpedia.org/id/4qU7p |
| prov:wasDerivedFrom | wikipedia-en:No-three-in-line_problem?oldid=1120956451&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/No-three-in-line.svg wiki-commons:Special:FilePath/Erdős-no-3-in-line-12x12.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:No-three-in-line_problem |
| is dbo:wikiPageRedirects of | dbr:No-3-in-a-line_problem dbr:No-three-in-a-line-problem |
| is dbo:wikiPageWikiLink of | dbr:Collinearity dbr:Mathematical_puzzle dbr:No-3-in-a-line_problem dbr:Heilbronn_triangle_problem dbr:Prime_number dbr:Eight_queens_puzzle dbr:Cap_set dbr:List_of_unsolved_problems_in_mathematics dbr:Moment_curve dbr:No-three-in-a-line-problem |
| is foaf:primaryTopic of | wikipedia-en:No-three-in-line_problem |
