Кіріспе
Рамзи теориясының негізгі комбинаторлық нәтижесі
Математикада Хейлз-Джуетт теоремасы – Альфред В. Хейлз және Роберт И. Джуетт есімдерімен аталатын Рамзи теориясының негізгі комбинаторлық нәтижесі. Бұл теорема жоғары өлшемді объектілердің міндетті түрде белгілі бір комбинаторлық құрылымды көрсету керектігіне қатысты; мұндай объектілердің "толыққанды кездейсоқ" болуы мүмкін емес. Теореманың бейресми геометриялық тұжырымы: кез келген оң бүтін сандар n және c үшін, H саны бар, егер H өлшемді n×n×n×…×n кубының жасушалары c түспен боялған болса, онда ұзындығы n болатын бір қатар, баған немесе белгілі бір диагональдің (төменде егжей-тегжейі келтіріледі) барлық жасушалары бір түсті болуы керек. Басқаша айтқанда, n және c тұрақты деп есептесек, c ойыншы бар tic-tac-toe ойынының жоғары өлшемді, көп ойыншылы, n қатарлы жалпылама нұсқасы, n қаншалықты үлкен болса да, c қанша ойыншы ойнаса да және әрбір қадамды қай ойыншы жасаса да, егер ол жеткілікті жоғары өлшемді H тақтасында ойналса, тең аяқталуы мүмкін емес. Стандартты стратегия ұрлау аргументі бойынша, егер екі ойыншы кезекпен ойнаса, онда бірінші ойыншының H жеткілікті үлкен болғанда жеңіске жететін стратегиясы бар екенін қорытуға болады, бірақ осы стратегияны алуға арналған практикалық алгоритм әзірленбеген.
HalesJewett теоремасының дәлелі (ерекше жағдайда)
Біз қазір Hales–Jewett теоремасын жоғарыда қарастырылған n = 3, c = 2, H = 8 ерекше жағдайында дәлелдейміз. Бұл міндетті Hales–Jewett теоремасының қарапайым нұсқаларын дәлелдеуге келтіру (осы жағдайда n = 2, c = 2, H = 2 және n = 2, c = 6, H = 6) идеясы. Hales–Jewett теоремасының жалпы жағдайын ұқсас әдістермен, математикалық индукция қолдану арқылы дәлелдеуге болады. W гиперкубтың әрбір элементі 1-ден 3-ке дейінгі сегіз саннан тұратын тізбе болып табылады, мысалы, 13211321 гиперкубтың элементі. Бұл гиперкубты «нөлдермен» және «кресттермен» толы деп есептейміз. Қарама-қайшылық арқылы дәлелдейміз және нөлдердің немесе кресттердің жиынында комбинаторлық түзу жоқ деп санаймыз. Егер мұндай тізбектің алғашқы алты элементін бекітіп, соңғы екеуін өзгертетін болсақ, қарапайым крест-ноль ойынының тақтасын аламыз, мысалы, «132113??» осындай тақта береді. Әрбір мұндай тақта үшін «abcdef??», «abcdef11», «abcdef12» және «abcdef22» позицияларын қарастырамыз. Олардың әрқайсысы нөл немесе крестпен толтырылуы керек, сондықтан көгершін принципі бойынша екеуі бірдей символмен толтырылуы керек. Осы позициялардың кез келген екеуі комбинаторлық түзудің бөлігі болғандықтан, сол түзудің үшінші элементі қарама-қарсы символмен толтырылуы керек (комбинаторлық түзудің барлық үш элементі бірдей символмен толтырылмаған деп есептейміз). Яғни, «abcdef» әрбір таңдауы үшін (оны алты өлшемді гиперкубтың элементі ретінде қарастыруға болады) алты (біртіндеп келісетін) мүмкіндік бар: «abcdef11» және «abcdef12» – нөлдер, «abcdef13» – крест; «abcdef11» және «abcdef22» – нөлдер, «abcdef33» – крест; «abcdef12» және «abcdef22» – нөлдер, «abcdef32» – крест; «abcdef11» және «abcdef12» – кресттер, «abcdef13» – нөл; «abcdef11» және «abcdef22» – кресттер, «abcdef33» – нөл; «abcdef12» және «abcdef22» – кресттер, «abcdef32» – нөл. Осылайша, алты өлшемді гиперкубты жоғарыда аталған алты мүмкіндіктің әрқайсысына сәйкес келетін алты сыныпқа бөлуге болады. (Егер «abcdef» элементі бірнеше мүмкіндікке сәйкес келсе, біреуін кездейсоқ таңдауға болады, мысалы, тізімдегі ең жоғарысын таңдау арқылы). Енді W-дегі 111111, 111112, 111122, 111222, 112222, 122222, 222222 элементтерін қарастырайық. Көгершін принципі бойынша, осы элементтердің екеуі бір сыныпқа түсуі керек. Мысалы, 111112 және 112222 (5) сыныпқа түседі деп есептейік, сонда 11111211, 11111222, 11222211, 11222222 – кресттер, ал 11111233, 11222233 – нөлдер. Ал енді 11333233 позициясын қарастырайық, ол крестпен немесе нөлмен толтырылуы керек. Егер ол крестпен толтырылса, онда 11xxx2xx комбинаторлық түзу толығымен кресттермен толтырылады, бұл біздің гипотезамызға қайшы келеді. Егер оның орнына нөл толған болса, онда 11xxx233 комбинаторлық түзу толығымен нөлдермен толтырылады, бұл тағы да біздің гипотезамызға қайшы келеді. Сол сияқты, егер W-ның жоғарыда аталған жеті элементінің кез келген екеуі бір сыныпқа түседі. Барлық жағдайларда қарама-қайшылық болғандықтан, бастапқы гипотеза жалған болуы керек; демек, кем дегенде бір комбинаторлық түзу толығымен нөлдерден немесе толығымен кресттерден тұруы керек. Жоғарыдағы аргумент біршама тиімсіз болды; шын мәнінде, H = 4 үшін де сол теорема қолданылады. Егер жоғарыдағы аргументті n және c жалпы мәндеріне кеңейтсек, онда H өте тез өседі; тіпті c = 2 болғанда да (екі ойыншылық крест-ноль ойынына сәйкес келеді), жоғарыдағы аргументпен берілген H Акерман функциясы сияқты тез өседі. Бірінші примитивті рекурсивті шектеу Сахарон Шелахқа тиесілі және ол әлі күнге дейін Hales–Jewett саны H = H(n, c) үшін ең танымал шектеу болып табылады.
reduce this task to that of proving simpler versions of the Hales–Jewett theorem (in this particular case, to the cases n = 2, c = 2, H = 2 and n = 2, c = 6, H = 6). One can prove the general case of the Hales–Jewett theorem by similar methods, using mathematical induction. Each element of the hypercube W is a string of eight numbers from 1 to 3, e. g. 13211321 is an element of the hypercube. We are assuming that this hypercube is completely filled with "noughts" and "crosses". We shall use a proof by contradiction and assume that neither the set of noughts nor the set of crosses contains a combinatorial line. If we fix the first six elements of such a string and let the last two vary, we obtain an ordinary tic tac toe board, for instance "132113??" gives such a board. For each such board "abcdef?? ", we consider the positions
"abcdef11", "abcdef12", "abcdef22". Each of these must be filled with either a nought or a cross, so by the pigeonhole principle two of them must be filled with the same symbol. Since any two of these positions are part of
a combinatorial line, the third element of that line must be occupied by the opposite symbol (since we are assuming that no combinatorial line has all three elements filled with the same symbol). In other words, for each choice of "abcdef" (which can be thought of as an element of the six dimensional hypercube W), there are six (overlapping) possibilities:
abcdef11 and abcdef12 are noughts; abcdef13 is a cross. abcdef11 and abcdef22 are noughts; abcdef33 is a cross. abcdef12 and abcdef22 are noughts; abcdef32 is a cross. abcdef11 and abcdef12 are crosses; abcdef13 is a nought. abcdef11 and abcdef22 are crosses; abcdef33 is a nought. abcdef12 and abcdef22 are crosses; abcdef32 is a nought. Thus we can partition the six dimensional hypercube W into six classes, corresponding to each of the above six possibilities. (If an element abcdef obeys multiple possibilities, we can choose one arbitrarily, e. g. by choosing the highest one on the above list). Now consider the seven elements 111111, 111112, 111122, 111222, 112222, 122222, 222222 in W. By the pigeonhole principle, two of these elements must fall into the same class. Suppose for instance
111112 and 112222 fall into class (5), thus 11111211, 11111222, 11222211, 11222222 are crosses and 11111233, 11222233 are noughts. But now consider the position 11333233, which must be filled with either a cross or a nought. If it is filled with a cross, then the combinatorial line 11xxx2xx is filled entirely with crosses, contradicting our hypothesis. If instead it is filled with a nought, then the combinatorial line 11xxx233 is filled entirely with noughts, again contradicting our hypothesis. Similarly if any other two of the above seven elements of W fall into the same class. Since we have a contradiction in all cases, the original hypothesis must be false; thus there must exist at least one combinatorial line consisting entirely of noughts or entirely of crosses. The above argument was somewhat wasteful; in fact the same theorem holds for H = 4. If one extends the above argument to general values of n and c, then H will grow very fast; even when c = 2 (which corresponds to two player tic tac toe) the H given by the above argument grows as fast as the Ackermann function. The first primitive recursive bound is due to Saharon Shelah, and is still the best known bound in general for the Hales–Jewett number H = H(n, c).