Viikkotehtävä: puuttuvat aritmeettiset jonot (viikko 9/2019)

kombinatoriikka

#1

Viikkotehtävä

Vastausaikaa su 3.3.2018 klo 24 asti
Vastausaika on päättynyt. Voit keskustella tehtävästä ja sen ratkaisuideoista vapaasti tässä ketjussa.

Tehtävä

Onko mahdollista valita 2019 keskenään erisuurta positiivista kokonaislukua, jotka ovat pienempiä kuin 100\,000 ja joista mitkään kolme eivät muodosta aritmeettista jonoa?

(Kolme lukua muodostavat aritmeettisen jonon, jos ne ovat a, a+d ja a+2d joillakin a ja d.)

Vihje

Ratkaisuksi ei kelpaa “tarkistin tietokoneohjelmalla, että oheiset luvut eivät sisällä kolmen alkion aritmeettista jonoa” tai “tarkistin tietokoneohjelmalla, että vaadittua joukkoa ei ole”, mutta tarkoitukseen sopivan tietokoneohjelman luonnostelu saattaa auttaa ratkaisussa alkuun.


sulki #2

avasi #3

#4

Tämäpä osoittautui hankalaksi. Kyse on vuoden 1983 IMO-tehtävästä, mutta niihin aikoihin olympiatehtävät olivat yleensä vähän helpompia kuin nykyään. Taannoisessa valmennuskirjeessäkin osoittautui olleen vastaava tehtävä eri tavalla ilmaistuna.

Aletaan konstruoida lukujoukkoa “ahneesti” lisäämällä siihen aina pienin luku, joka ei täydennä mitään aritmeettista jonoa. Valitaan aluksi 1,2, sitten joudutaan jättämään 3 välistä mutta jatketaan 4,5. Tämän jälkeen ei kelpaa 6 (joka kuuluu jonoon 4,5,6), 7 (1,4,7), 8 (2,5,8) eikä 9 (1,5,9) mutta 10=9+1 käy, ja samoin käyvät luvut 9+2,9+4,9+5, siis koko aiempi joukko lisättynä yhdeksällä. Tähän mennessä saatu joukko on

A = \{\, 1, 2, 4, 5, 10, 11, 13, 14 \,\}.

Vastaavalla päättelyllä nähdään, että jos kaikkiin joukon A lukuihin lisätään 27, saadaan joukon koko tuplattua joutumatta hankaluuksiin. Kaikki A:n erotukset ovat nimittäin enintään 13, joten lisätyt alkiot eivät voi täydentää A:n alkioiden kanssa aritmeettista jonoa. Muodostetaan hypoteesi, että lisäämällä joukon alkioihin aina seuraava kolmen potenssi saadaan joukon koko kaksinkertaistettua. Tällöin joukon koko ja suurin alkio ovat:

\begin{matrix} \textrm{koko} & \textrm{suurin alkio}\\ 4 & 5\\ 8 & 14\\ 16 & 41\\ 32 & 122\\ 64 & 365\\ 128 & 1094\\ 256 & 3281\\ 512 & 9842\\ 1024 & 29525\\ 2048 & 88574\end{matrix}

Näyttää hyvältä! Hypoteesi pitäisi vielä todistaa, minkä tekeminen aiempaa päättelyä yleistämällä on täysin mahdollista mutta kylläkin hieman työlästä. Tähän on oikotie, joka vaatii vähän inspiraatiota: edellisen taulukon vasen sarake sisälsi kahden potensseja, ja oikeassa sarakkeessa odottaisi olevan jotain kolmen potensseihin liittyvää. Jos vähennetään joukon kaikista alkioista 1, aritmeettisia jonoja koskeva ehto ei muutu ja oikeaan sarakkeeseen saadaan kolmen peräkkäisten potenssien summia. Kirjoitetaan konstruoidun joukon alkiot 3-järjestelmässä tämän muutoksen jälkeen:

A' = \{\, 0_3, 1_3, 10_3, 11_3, 100_3, 101_3, 110_3, 111_3 \,\}.

On helppo tarkistaa, että konstruktiossa joukkoon tullaan ottaneeksi luvut, joiden 3-järjestelmäesitys sisältää vain nollia ja ykkösiä. Jos tällaisessa joukossa on luvut a, b ja c, joille b-a=c-b eli a+c=2b, niin luvussa 2b on 3-järjestelmässä vain nollia ja kakkosia, mutta a+b voi olla tätä muotoa vain, jos a=c. Siten kiellettyjä aritmeettisia jonoja ei esiinny.


#5

Tässä toinen tapa ajatella tehtävää: https://math.stackexchange.com/a/97786/61567

Mieleen tulee myös Cantorin joukko.