Tässä minulle joskus heitetty pikkupähkinä pureskeltavaksi diskreetin matematiikan ja kombinatoriikan harrastajille:
Tarkastellaan n-kirjaimisessa aakkostossa muodostettujen sanojen joukkoa.
Pyritään muodostamaan mahdollisimman pitkä sellainen sana, jonka missään osasanassa kaikkien kirjaimien määrä ei ole yhtäaikaa parillinen.
Esim. kolmikirjaimisen aakkoston {a,b,c} sana 'abacbca' ei käy sillä sen loppuosassa esiintyy osasana 'bacbca'. Tämä sisältää parillisen määrän kirjaimia a, b, ja c. Sen sijaan sana 'abcbabc' on kelvollinen sana.
Voidaanko muodostaa mielivaltaisen pitkiä tällaisia sanoja?
Jos ei, niin mikä on tällaisen sanan maksimipituus n-kirjaimisessa aakkostossa? Mikä on tässä tapauksessa maksimipituus vaikkapa 26-kirjaimisessa aakkostossa?
Miten todistat väitteesi lyhyesti?
Matti K. Sinisalo
Tarkastellaan n-kirjaimisessa aakkostossa muodostettujen sanojen joukkoa.
Pyritään muodostamaan mahdollisimman pitkä sellainen sana, jonka missään osasanassa kaikkien kirjaimien määrä ei ole yhtäaikaa parillinen.
Esim. kolmikirjaimisen aakkoston {a,b,c} sana 'abacbca' ei käy sillä sen loppuosassa esiintyy osasana 'bacbca'. Tämä sisältää parillisen määrän kirjaimia a, b, ja c. Sen sijaan sana 'abcbabc' on kelvollinen sana.
Voidaanko muodostaa mielivaltaisen pitkiä tällaisia sanoja?
Jos ei, niin mikä on tällaisen sanan maksimipituus n-kirjaimisessa aakkostossa? Mikä on tässä tapauksessa maksimipituus vaikkapa 26-kirjaimisessa aakkostossa?
Miten todistat väitteesi lyhyesti?
Matti K. Sinisalo
Vastaukset 10
Vanhimmat
... pitkiä sanoja ei voi muodostaa, ainakaan kaikille n.
Kun n=2, pisin sanamitta on 3.
Kun n=3, pisin sanamitta on 7
Todistus: Kasvata sanoja puussa, jonka alku on ab, WLOG. Saamme uusia haaroja lisäämällä merkkejä sanojen perään aina kun niin voi tehdä rikkomatta ehtoa. Prosessi päättyy ja saamme pisimmiksi ei-isomorfisiksi sanoiksi abacaba, abacbab ja abcbabc. Pidempi ehdon täyttävä sana ei ole mahdollinen, sillä muuten se voitaisiin kasvattaa puussa. QED
n=4: Ei mitään ideoita. Muodostetaan jonkinlainen katenaatioryhmä tms. ?
Tapaukset n=2 ja n=3 ovat ihan oikein ratkaistu.
Kuitenkin yleistä tulosta haetaan.
Muistaakseni juuri äskettäin tällä palstalla joku kuulutti olevansa kiinnostunut näistä yleisistä matemaattisista ratkaisuista, silloin kun n on liian suuri tietokoneelle...
Olen ehkä päässyt vähän eteenpäin.
Olkoon aakkoston koko n.
Väite: Maksimipituus ehdon täyttävälle sanalle on vähintään 2^n - 1.
Todistus. Olkoon aakkoset {a_1,...,a_n}. Laita S_1 = a_1 ja S_(i 1) = 'S_i a_(i 1) S_i'. Tällöin S_n on selvästikin ehdon täyttävä sana.
MOT
Konjektuuri: Maksimipituus ehdon täyttävälle sanalle on tasan 2^n - 1.
Todistusidea: Jos luemme maksimimittaista sanaa vasemmalta oikealle, esim. tapauksessa n=3, voimme tutkia kunkin merkin jälkeistä 'kiellettyjen aakkosten joukkoa'. Huomaamme, että maksimimittaisessa sanassa esiintyy kerran jokainen epätyhjä osajoukko.
Näin saadaan (konstruktiivisesti) perusteltua alaraja sanan maksimipituudelle.
Se, että tämä on myös yläraja, vaatisi vielä tarkempaa perustelua.
Annettakoon vihje: (Erään) ratkaisun avaimet löytyvät graafiteorian ja koodausteorian perusteista ja mm. suomenkielisestä Wikipediasta.
... keksin ratkaisun! Olin ajatellut pulmaa ihan liian monimutkaisesti tähän asti... ;) Tyhmä minä.
Väite: Jos aakkoston koko on n, ehdon täyttävän sanan maksimipituus on 2^n - 1.
Todistus: Otetaan aakkosto A={a_1,a_2,...,a_n}. Pituus 2^n - 1 on saavutettavissa (ks. edellisen viestin induktioesimerkki). Nyt todistamme, ettei pituutta voi ylittää.
Olkoon S = (S_1, S_2 , ..., S_s) jokin s-pituinen, ehdon täyttävä sana aakkostolla A. Jokaiselle 1
Havainnollistetaan asiaa.
Tarkastellaan sanaa 'abacabadabacaba' nelikirjaimisessa aakkostossa {a,b,c,d}.
Muodostetaan pariteettivektori siten, että viimeinen bitti kuvaa kirjaimen a lukumäärän pariteettia sanan alusta lukien ja ensimmäinen kirjaimen d pariteettia.
Tarkastellaan, miten pariteettivektori muuttuu, kun sanaan lisätään kirjain kerrallaan:
: 0000
a: 0001
b: 0011
a: 0010
c: 0110
a: 0111
b: 0101
a: 0100
d: 1100
a: 1101
b: 1111
a: 1110
c: 1010
a: 1011
b: 1001
a: 1000
Näyttääkö tutulta?
Kysymyksessä on yleisesti mittausteknologiassa käytetty Gray-koodi ks. jossa seuraavaan koodisanaan siirryttäessä aina tarkalleen yksi bitti (miksi?) vaihtaa tilaansa. Ks. http://fi.wikipedia.org/wiki/Gray-koodi
Gray-koodissa on kysymys ns. kauppamatkustajan ongelman ratkaisemisesta n-ulotteisessa hyperkuutiossa {0,1}^n, jossa em. vektorit kuvaavat kuution kulmia. Tehtävänä on kiertää kuutio särmiä pitkin.
PS. Gray-koodi liittyy myös virheitä havaitsevien koodien teoriaan siten, että poimimalla koodiin joka toisen sanan n-pituisesta Gray-koodilistasta saadaan muodostettua maksimaalinen n-pituinen yhden virheen havaitseva binäärikoodi.
Gray-koodilla voi olettaa olevan merkitystä myös eräiden matemaattisten probleemien tehokkaan algoritmisen ratkaisun kannalta.
Gray-koodin laskeminen on erittäin tehokasta (ks. Wikipedia).
Gray-koodi antaa siis täydellisen matemaattisen ratkaisun n-ulotteisessa hyperkuutiossa {0,1}^n.
Takaisin Köningsbergin silloille?
"Pyritään muodostamaan mahdollisimman pitkä sellainen sana, jonka missään osasanassa kaikkien kirjaimien määrä ei ole yhtäaikaa parillinen. "
Tyhmä varmistaa. Onhan tarkoitus, että "kaikki kirjaimet" viisaa alisanan kaikkiin kirjaimiin eikä aakkoston kaikkiin kirjaimiin? Eli jos aakkosto on {a,b,c}, niin "ababc" ei kelpaa, koska alisanassa "abab" on kaikkia siinä ilmeneviä kirjaimia parillinen määrä ja c:n puute ei haittaa?
Jos näin, niin haiskahtaa induktiolta aakkoston koon suhteen.
ei kelpaa, koska siinä esiintyy osasana 'abab', jossa kirjainten 'a' ja kirjainten 'b' esiintymisten lukumäärä on 2 ja siten parillinen. Niiden kirjainten, joita osasanassa ei esiinny, kuten 'c', esiintymisten lukumäärä osasanassa on nolla ja siten parillinen, joten ne eivät vaikuta asiaan.
Onko osasanan määritelmä se, että alusta ja lopusta otetaan osa merkeistä pois, esim. merkistössä {1,2,3,4,5} sanan 12345 osasana voi olla 234, vai voiko sanan keskeltä myös ottaa merkkejä pois, jolloin esim 245 olisi 12345:n osasana?
Sanan 12345 osasanat ovat 1,2,3,4,5,12,23,34,45,123,234,345,1234,2345 ja 12345.
Tyhjää sanaa ei tässä tehtävässä lueta osasanaksi. Siinähän kaikkien kirjainten lukumäärä olisi aina parillinen, joten tehtävä menettäisi merkityksensä.