| dbo:abstract
|
- Halesova-Jewettova věta je důležité tvrzení Ramseyovské teorie, které tvrdí, že Pro každá přirozená čísla n a c existuje dostatečně velké D, od kterého lze v každém obarvení nadkrychle strany n a dimenze D c barvami najít stejně vybarvený řádek, sloupec, diagonálu, tělesovou úhlopříčku, či nějakou nadtělesovou úhlopříčku. Tvrdí tedy, že úplný chaos při barvení není od dostatečně velkých objektů možný, přičemž oním „dostatečně velkým“ se zde myslí „při dostatečně velké dimenzi“. (cs)
- Der Satz von Hales-Jewett ist ein mathematischer Satz aus der Ramseytheorie. Im Kern behandelt der Satz die Frage, ob hoch-dimensionale Objekte zwingend eine kombinatorische Struktur besitzen. Er ist nach den amerikanischen Mathematikern Alfred W. Hales und Robert I. Jewett benannt. (de)
- In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to be "completely random". An informal geometric statement of the theorem is that for any positive integers n and c there is a number H such that if the cells of a H-dimensional n×n×n×...×n cube are colored with c colors, there must be one row, column, or certain diagonal (more details below) of length n all of whose cells are the same color. In other words, the higher-dimensional, multi-player, n-in-a-row generalization of a game of tic-tac-toe cannot end in a draw, no matter how large n is, no matter how many people c are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high dimension H. By a standard strategy stealing argument, one can thus conclude that if two players alternate, then the first player has a winning strategy when H is sufficiently large, though no practical algorithm for obtaining this strategy is known. (en)
- En matemáticas, el teorema de Hales-Jewett es un resultado combinatorio fundamental de la teoría de Ramsey que lleva el nombre de Alfred W. Hales y Robert I. Jewett, en relación con el grado en que los objetos de alta dimensión deben exhibir necesariamente alguna estructura combinatoria; es imposible que tales objetos sean "completamente aleatorios". Un enunciado geométrico informal del teorema es que para cualquier entero positivo n y c hay un número H tal que si las celdas de un cubo H -dimensional n × n × n ×... × n están coloreadas con c colores, existe una fila, columna o cierta diagonal (más detalles a continuación) de longitud n cuyas celdas son del mismo color. En otras palabras, la generalización de n -en-fila, multijugador y de dimensiones superiores de un juego de tic-tac-toe no puede terminar en empate, no importa cuán grande sea n, no importa cuántas personas c están jugando, y no importa qué jugador juegue cada turno, siempre que se juegue en un tablero de dimensión H suficientemente alta. Mediante un argumento de robo de estrategia estándar, se puede concluir que si dos jugadores se alternan, entonces el primer jugador tiene una estrategia ganadora cuando H es suficientemente grande, aunque no se conoce ningún algoritmo práctico para obtener esta estrategia. Más formalmente, sea WnH el conjunto de palabras de longitud H sobre un alfabeto con n letras; es decir, el conjunto de sucesiones de {1, 2,..., n } de longitud H. Este conjunto forma el hipercubo que es el tema del teorema. Una palabra variable w (x) en WnH todavía tiene longitud H pero incluye un elemento especial x en lugar de al menos una de las letras que lo componen. Las palabras w (1), w (2),..., w ( n) obtenidas al reemplazar todas las instancias del elemento especial x con 1, 2,..., n, forman una línea combinatoria en el espacio WnH; las líneas combinatorias corresponden a filas, columnas y (algunas de las) diagonales del hipercubo. El teorema de Hales-Jewett establece que para enteros positivos n y c dados, existe un entero positivo H, que depende de n y c, tal que para cualquier partición de WnH en c partes, hay al menos una parte que contiene toda una línea combinatoria. Por ejemplo, tome n = 3, H = 2 y c = 2. El hipercubo WnH en este caso es solo el tablero estándar de tic-tac-toe, con nueve posiciones: Una línea combinatoria típica sería la palabra 2x, que corresponde a la línea 21, 22, 23; otra línea combinatoria es 'xx, que es la línea 11, 22, 33. (Tenga en cuenta que la línea 13, 22, 31, aunque es una línea válida para el tic-tac-toe, no se considera una línea combinatoria). En este caso particular, el teorema de Hales-Jewett no se aplica; es posible dividir el tablero de tic-tac-toe en dos conjuntos, por ejemplo, {11, 22, 23, 31} y {12, 13, 21, 32, 33}, ninguno de los cuales contiene una línea combinatoria (y correspondería empate en el juego de tic-tac-toe). Por otro lado, si aumentamos H a, digamos, 8 (de modo que el tablero ahora sea de ocho dimensiones, con 38 = 6561 posiciones), y dividir este tablero en dos conjuntos (los "ceros" y "cruces"), entonces uno de los dos conjuntos debe contener una línea combinatoria (es decir, no es posible empatar en esta variante de tic-tac-toe). Para una prueba, vea a continuación. (es)
- En mathématiques, le théorème de Hales-Jewett est un résultat combinatoire fondamental de la théorie de Ramsey, nommé d'après Alfred W. Hales et Robert I. Jewett. Il concerne la dimension dans laquelle des objets de cette dimension doivent nécessairement présenter une certaine régularité dans leur structure combinatoire : il est impossible que de tels objets soient « complètement aléatoires ». (fr)
- 헤일스-주에트 정리(Hales–Jewett theorem)는 하이퍼큐브 색칠에 관련된 램지 이론의 정리다. 충분히 큰 N이 존재해 한변이 n인 하이퍼큐브를 k개의 색으로 칠할때, N차원 이상에서는 가로세로대각선으로 한 열에 같은 색으로 칠해진 n개의 칸이 반드시 존재한다는 정리다. (ko)
|
| rdfs:comment
|
- Halesova-Jewettova věta je důležité tvrzení Ramseyovské teorie, které tvrdí, že Pro každá přirozená čísla n a c existuje dostatečně velké D, od kterého lze v každém obarvení nadkrychle strany n a dimenze D c barvami najít stejně vybarvený řádek, sloupec, diagonálu, tělesovou úhlopříčku, či nějakou nadtělesovou úhlopříčku. Tvrdí tedy, že úplný chaos při barvení není od dostatečně velkých objektů možný, přičemž oním „dostatečně velkým“ se zde myslí „při dostatečně velké dimenzi“. (cs)
- Der Satz von Hales-Jewett ist ein mathematischer Satz aus der Ramseytheorie. Im Kern behandelt der Satz die Frage, ob hoch-dimensionale Objekte zwingend eine kombinatorische Struktur besitzen. Er ist nach den amerikanischen Mathematikern Alfred W. Hales und Robert I. Jewett benannt. (de)
- En mathématiques, le théorème de Hales-Jewett est un résultat combinatoire fondamental de la théorie de Ramsey, nommé d'après Alfred W. Hales et Robert I. Jewett. Il concerne la dimension dans laquelle des objets de cette dimension doivent nécessairement présenter une certaine régularité dans leur structure combinatoire : il est impossible que de tels objets soient « complètement aléatoires ». (fr)
- 헤일스-주에트 정리(Hales–Jewett theorem)는 하이퍼큐브 색칠에 관련된 램지 이론의 정리다. 충분히 큰 N이 존재해 한변이 n인 하이퍼큐브를 k개의 색으로 칠할때, N차원 이상에서는 가로세로대각선으로 한 열에 같은 색으로 칠해진 n개의 칸이 반드시 존재한다는 정리다. (ko)
- In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to be "completely random". (en)
- En matemáticas, el teorema de Hales-Jewett es un resultado combinatorio fundamental de la teoría de Ramsey que lleva el nombre de Alfred W. Hales y Robert I. Jewett, en relación con el grado en que los objetos de alta dimensión deben exhibir necesariamente alguna estructura combinatoria; es imposible que tales objetos sean "completamente aleatorios". Por ejemplo, tome n = 3, H = 2 y c = 2. El hipercubo WnH en este caso es solo el tablero estándar de tic-tac-toe, con nueve posiciones: (es)
|
