25 augusta 2008

Me3ce

Predstavme si, že vedľa seba kladieme farebné kamene. Monochromatická ekvidištantná trojica, skrátene me3ca, bude každá taká trojica kameňov rovnakej farby, pre ktorú platí: vzdialenosť prvého a druhého kameňa tejto trojice je rovnaká ako vzdialenosť druhého a tretieho kameňa tejto trojice. Na ilustračnom obrázku som znázornil sériu 10 kameňov dvoch farieb, ktorá obsahuje až 5 me3íc.

Ako sa môžete sami ľahko presvedčiť (napríklad otestovaním všetkých 512 možností na počítači), každá séria pozostávajúca z deväť kameňov dvoch farieb už nutne obsahuje nejakú me3cu. Osem kameňov dvoch farieb však me3cu obsahovať nemusí; všimnite si napríklad postupnosť 0X0XX0X0. Takže s dvomi farbami je otázka existencie bezme3cových sérií jednoduchá. Ukazuje sa však, že pre tri farby je to oveľa ťažšie:

Existuje také prirodzené číslo n, že každá séria n kameňov troch farieb obsahuje aspoň jednu me3cu?

Sám na túto zdanlivo jednoduchú otázku neviem odpovedať; môj polhodinový limit na jej vyriešenie nestačil. Preto sa opäť s dôverou obraciam na Vás. :-) Vzhľadom na to, že tento problém nie je triviálny, môžete do komentárov uvádzať nielen úplné riešenie, ale aj každý potenciálne užitočný postreh.

Poznámka 26.8.: Ako v komentári upozornil Nanyk, tento problém je zhodou okolností známy a veľmi ťažký a odpoveď je kladná pre ľubovoľný počet farieb a ľubovoľnú dĺžku ekvidištantnej série. Pre tri farby je maximálna bezme3cová séria dĺžky 26, napríklad

RRYYRRYBYBBRBRRYRYYBRBBYBY

a je dokázané, že každá séria dĺžky 27 už nejakú me3cu obsahuje.

A ak si chcete privyrobiť 1000 dolárov stačí, keď pre každé k ukážete, že pre niektoré n menšie než 2 na k2 platí, že každá séria kameňov dvoch farieb dĺžky n už obsahuje nejakú ekvidištantnú monochromatickú k-ticu. Túto odmenu Vám udelí jeden z najvýznamnejších žijúcich matematikov, Ronald Graham.

4 komentáre:

Nanyk povedal(a)...

upozornenie: nasledujuci text moze znicit radost z riesenia

me3ce su vlastne to comu sa hovori jednofarebna aritmeticka postupnost dlzky 3. nechcem nicit zabavu, ale moze vas zaujimat ze

plati veta

(van der Waerden) Pre k farieb a dané číslo l, existuje číslo N(k, l)také, že kedykolvek máme množinu {1, . . . , N(k, l)} ofarbenu k farbami, tak existuje nějaká jednofarebná aritmetická postupnost dlzky aspoň l

http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem

znovu ramsey theory

Radoslav Harman povedal(a)...

Ah, Nanyk, tak to som naozaj nevedel, ďakujem za upozornenie. Super! Ten problém ma napadol kvôli inému problému (ešte sa k nemu na QEDe dostanem) a po polhodine neúspešného zápasenia som ho bez veľkého váhania a prehľadávania literatúry napísal na blog...

Nanyk povedal(a)...

tak to tu v podstate nezavisle budujes ramsey teoriu:)

no ved je to pekny problem...aj zarobit sa na nom da...asi nejakych 1000$ za dobre spodne odhady:) (v zobecnenom pripade)

Radoslav Harman povedal(a)...

No, "buduješ" je silné slovo :) Skôr píšem bez dlhšieho skúmania o veciach, ktoré ma napadnú, celkom fajn sa pri tom bavím a ešte sa niečo nové aj naučím. A spolu so mňou možno aj niektorí návšetvníci tohto blogu...