Nolla oikein lotossa

5 kuponkia on noin 60 ruudukkoa, kyllä nollatulos on 100%:sti saavutettavissa
pienemmälläkin ruudukkomäärällä.

Tarkkaa vastausta en tiedä, ehkä sitä ei tiedä kukaan. On minulla kyllä täsmällinen
systeemi, mutten tiedä onko se pienin mahdollinen.

Sen voin sanoa, ettei se ainakaan alle 8 ruudukon onnistu, koska seitsemän
arvottua numeroa yltää osumaan 7 ruudukkoon.

Tässähän ei ole kyseessä todennäköisyysongelma, vaan puhtaasti kombinatorinen tehtävä.

Yleistetäänpä kysymys: Eli luvusta 39 tulee n ja luvusta 7 tulee r. Oletamme, että r n/2, nolla-oikein rivi olisi mahdoton.)

Kirjoitamme [n] = {1,2,3,...,n} ja [n]C(r) merkitsee kaikkien r-osajoukkojen kokoelmaa. Luonnollisella notaatiolla: |[n]C(r)| = nCr.

Tehtävä: Olkoon X= [n]C(n-r) ja Y= [n]C(r). Löydä funktio f:X--->Y, jolle pätee "Jokaiselle x in X, f(x) on joukon x osajoukko" ja |f(X)| on minimaalinen. Kirjoitetaan M = M(n,r) = min|f(X)|.

Huom: Tiedämme että r 1

Näyttäisi, että selviää 17 rivillä, vaan voihan siinä olla joku "reikä" (tai "tukko"), kun ei jaksa tarkistaa. Periaatteena jakaa rivi osiin, joissa "neljäsosissa" ei sitten voikaan olla kuin kaksi tai yksi rastia, muutoin joku "neljäsosa" jää rastitta. Sitten pitää vain varmistaa kustakin "neljäsosasta", ettei yksi rasti osu kaikkiin siinä oleviin riveihin.

Rivit vaikkapa seuraavasti:
20,21,22,23,24,25,26
13,14,15,16,17,18,19
("puolikkaat" varmistettu, rasteja pitää olla molemissa osissa)
1,2,3,4,5,6,7
33,34,35,36,37,38,39
(nyt pitää oikeassa rivissä olla joku rasti jokaisessa "neljänneksessä", muuten joku riveistä on 0 oikein.)

Sitten vaan varmistetaan, että yksi rasti kussakin "neljäsosassa" ei voi osua kaikkiin siinä esiintyviin riveihin, eli jätetään varma "reikä".
1,2,5,6,7,8,9
1,2,3,4,7,8,9
2,3,4,5,6,8,9
1,3,4,5,6,7,8
10,11,12,13,14,18,19
10,11,12,15,16,17,18
12,13,14,15,16,17,19
20,21,25,26,27,28,29
22,23,24,26,27,28,29
22,23,24,25,27,28,29
30,31,32,33,34,35,36
30,31,35,36,37,38,39
31,32,33,34,37,38,39

No, jos ei täytä vaatimuksia, ehkä tuosta ideasta joku taas pääsee eteenpäin?

old_profile_3668 kirjoitti:

Näyttäisi, että selviää 17 rivillä, vaan voihan siinä olla joku "reikä" (tai "tukko"), kun ei jaksa tarkistaa. Periaatteena jakaa rivi osiin, joissa "neljäsosissa" ei sitten voikaan olla kuin kaksi tai yksi rastia, muutoin joku "neljäsosa" jää rastitta. Sitten pitää vain varmistaa kustakin "neljäsosasta", ettei yksi rasti osu kaikkiin siinä oleviin riveihin.

Rivit vaikkapa seuraavasti:
20,21,22,23,24,25,26
13,14,15,16,17,18,19
("puolikkaat" varmistettu, rasteja pitää olla molemissa osissa)
1,2,3,4,5,6,7
33,34,35,36,37,38,39
(nyt pitää oikeassa rivissä olla joku rasti jokaisessa "neljänneksessä", muuten joku riveistä on 0 oikein.)

Sitten vaan varmistetaan, että yksi rasti kussakin "neljäsosassa" ei voi osua kaikkiin siinä esiintyviin riveihin, eli jätetään varma "reikä".
1,2,5,6,7,8,9
1,2,3,4,7,8,9
2,3,4,5,6,8,9
1,3,4,5,6,7,8
10,11,12,13,14,18,19
10,11,12,15,16,17,18
12,13,14,15,16,17,19
20,21,25,26,27,28,29
22,23,24,26,27,28,29
22,23,24,25,27,28,29
30,31,32,33,34,35,36
30,31,35,36,37,38,39
31,32,33,34,37,38,39

No, jos ei täytä vaatimuksia, ehkä tuosta ideasta joku taas pääsee eteenpäin?

Periaate näyttää oikein päätellyltä.

Systeemin "oikeellisuutta" en ryhdy tarkastamaan,
koska vieläkin pienempi on olemassa.

Mutta kuitenkin, suoritus on suosionosoitusten
arvoinen! Tap! Tap!

Vaikuttaisi vähän, että tuota alinta riviä ei olisi veikattu vielä ollenkaan, joten pitäisi se vielä laittaa kierrätettynä taas kolmella numerolla, eli kahdeksan riviä lisää.
44

Ensiksikin, tuossa ratkaisussa alimmissa riveissä oli vain 4 numeroa.
Minulle ei oikein selvinnyt miten niitä täydennetään, että joka rivissä
olisi 7 ruksia.

Ratkaisun "oikeellisuutta" en viitsi tarkistaa,
koska 36 ruudukkoa ei olisi ennätys,
vaikka olisi oikeinkin.

niin kokeillaan.

ne 36 riviä kirjoitti:

niin kokeillaan.

Annetaan palstan lukijoiden miettiä. Siis heidän joita
tämän ongelman ajatteleminen kiinnostaa.

Eihän täällä mihinkään "pulmiin" ole pakko tarttua, en
minäkään jaksa esimerkiksi ryhtyä sormilla laskemaan
onko jossakin yhtälössä 53 miinus-merkkiä, tai 53 - yksi.

36 ruudukkoisen systeemin esittämisen voin hylätä myös
siksi, ettei se ole vielä lähelläkään minimiä.

ne 36 riviä kirjoitti:

niin kokeillaan.

Minä vähän karsin ja tästä lähdettiin:

1,2,3,4,37,38,39
5,6,7,8,x,x,x
9,10,11,12,x,x,x
13,14,15,16,x,x,x
17,18,19,20,x,x,x
21,22,23,24,x,x,x
25,26,27,28,x,x,x
29,30,31,32,x,x,x
33,34,35,36,x,x,x

ja tuosta tulee rivit:

1,2,3,4,37,38,39
5,6,7,8,9,10,11
5,6,7,8,13,14,15
5,6,7,8,17,18,19
5,6,7,8.21,22,23
5,6,7,8,25,26,27
5,6,7,8,29,30,31
5,6,7,8,33,34,35

9,10,11,12,13,14,15
9,10,11,12,17,18,19
9,10,11.12,21,22,23
9,10,11,12,25,26,27
9,10,11,12,29,30,31
9,10,11,12,33,34,35

13,14,15,16,17,18,19
13,14,15,16,21,22,23
13,14,15,16,25,26,27
13,14,15,16,29,30,31
13,14,15,16,33,34,35

17,18,19,20,21,22,23
17,18,19,20,25,26,27
17,18,19,20,29,30,31
17,18,19,20,33,34,35

21,22,23,24,25,26,27
21,22,23,24,29,30,31
21,22,23,24,33,34,35

25,26,27,28,29,30,31
25,26,27,28,33,34,35

29,30,31,32,33,34,35 yhteensä 28

????? kirjoitti:

Minä vähän karsin ja tästä lähdettiin:

1,2,3,4,37,38,39
5,6,7,8,x,x,x
9,10,11,12,x,x,x
13,14,15,16,x,x,x
17,18,19,20,x,x,x
21,22,23,24,x,x,x
25,26,27,28,x,x,x
29,30,31,32,x,x,x
33,34,35,36,x,x,x

ja tuosta tulee rivit:

1,2,3,4,37,38,39
5,6,7,8,9,10,11
5,6,7,8,13,14,15
5,6,7,8,17,18,19
5,6,7,8.21,22,23
5,6,7,8,25,26,27
5,6,7,8,29,30,31
5,6,7,8,33,34,35

9,10,11,12,13,14,15
9,10,11,12,17,18,19
9,10,11.12,21,22,23
9,10,11,12,25,26,27
9,10,11,12,29,30,31
9,10,11,12,33,34,35

13,14,15,16,17,18,19
13,14,15,16,21,22,23
13,14,15,16,25,26,27
13,14,15,16,29,30,31
13,14,15,16,33,34,35

17,18,19,20,21,22,23
17,18,19,20,25,26,27
17,18,19,20,29,30,31
17,18,19,20,33,34,35

21,22,23,24,25,26,27
21,22,23,24,29,30,31
21,22,23,24,33,34,35

25,26,27,28,29,30,31
25,26,27,28,33,34,35

29,30,31,32,33,34,35 yhteensä 28

Eikös tuossa ole 29 riviä.

Hätäisesti vilkaisten näyttää siltä, että systeemi antaisi
nollatuloksen 100% todennäköisyydellä.

Mutta lähelläkään minimiä se ei vielä ole.

Minun tietämäni rajat olen tässä ketjussa jo esittänyt,
vähintään 8 ja enintään 15.

Kohtalaisen helposti lienee pääteltävissä alarajaksi
9 tai ehkä 10, saattaa olla että nämä on joku jossain
todistanutkin.

Uskon toistaiseksi vakaasti, ettei tuo 15 ole pienin
mahdollinen.

Taidanpa pannakin koneen hakemaan pienempää.

hente13 kirjoitti:

Minun tietämäni rajat olen tässä ketjussa jo esittänyt,
vähintään 8 ja enintään 15.

Kohtalaisen helposti lienee pääteltävissä alarajaksi
9 tai ehkä 10, saattaa olla että nämä on joku jossain
todistanutkin.

Uskon toistaiseksi vakaasti, ettei tuo 15 ole pienin
mahdollinen.

Taidanpa pannakin koneen hakemaan pienempää.

Itse lähestyisin tätä ongelmaa sillä tavalla, että pyrkisin formalisoimaan sen koodausteoriaan.

Esim. tähän tyyliin:

Olkoon D niiden 39-pituisten binäärisanojen joukko, joiden painoarvo (ts. ykkösten lukumäärä koodisanassa) on 7.

Näiden sanojen joukosta olisi löydettävä pienin mahdollinen sellainen osajoukko C, että kaikilla joukkoon D kuuluvilla sanoilla olisi olemassa sellainen joukon C sana y, jolla sanojen y ja x välinen etäisyys (poikkeamien lukumäärä) olisi vähintään 14.

Tämä olisi kuitenkin vasta alkua. Ongelmana on se, että joukon D alkioiden lukumäärä on Comb(39,7) =39!/(7!*32!)=15380937.

Tämä ei kuitenkaan ole mikään ongelma.

Computer manin pitää vain oivaltaa, että alkioilla 1,2,3,...,39 ei ole mitään identiteettiä. Niitä voidaan permutoida ihan vapaasti. Tämä antaa mahdollisuuden siihen, että ongelma on nykyistä tietokoneteknologiaa käyttäen ihan tarkastikin ratkaistavissa. Toki siihen tarvitaan aikaa vievää pikkunäpertelyä.

Hauskaahan tämä tällainen on, mutta aikaa vaativaa. Ehkä joku haluaa jatkaa tästä näpertelyä?

old_profile_46003 kirjoitti:

Itse lähestyisin tätä ongelmaa sillä tavalla, että pyrkisin formalisoimaan sen koodausteoriaan.

Esim. tähän tyyliin:

Olkoon D niiden 39-pituisten binäärisanojen joukko, joiden painoarvo (ts. ykkösten lukumäärä koodisanassa) on 7.

Näiden sanojen joukosta olisi löydettävä pienin mahdollinen sellainen osajoukko C, että kaikilla joukkoon D kuuluvilla sanoilla olisi olemassa sellainen joukon C sana y, jolla sanojen y ja x välinen etäisyys (poikkeamien lukumäärä) olisi vähintään 14.

Tämä olisi kuitenkin vasta alkua. Ongelmana on se, että joukon D alkioiden lukumäärä on Comb(39,7) =39!/(7!*32!)=15380937.

Tämä ei kuitenkaan ole mikään ongelma.

Computer manin pitää vain oivaltaa, että alkioilla 1,2,3,...,39 ei ole mitään identiteettiä. Niitä voidaan permutoida ihan vapaasti. Tämä antaa mahdollisuuden siihen, että ongelma on nykyistä tietokoneteknologiaa käyttäen ihan tarkastikin ratkaistavissa. Toki siihen tarvitaan aikaa vievää pikkunäpertelyä.

Hauskaahan tämä tällainen on, mutta aikaa vaativaa. Ehkä joku haluaa jatkaa tästä näpertelyä?

Huomaa, että tämä on yksittäistapaus Turanin ongelmasta hypergraafeille:

Etsi maksimaalinen 7-graafi, joka ei sisällä täydellistä 32 solmukohdan 7-graafia.

Kyseessä on tapaus r=7, t=25 seuraavasta:

Turanin ongelma: Mikä on maksimaalinen r-graafi, joka ei sisällä täydellistä (r t)-solmukohdan r-graafia.

Tapaus r=2, eli perinteisten graafien tapaus on tietenkin ratkaistu, mutta kun r>2, oikeastaan juuri mitään ei tiedetä! (Yksi ongelma seuraa todistuksesta, että perinteisten graafien Erdös-Stone-tyyppinen teoreema ei voi päteä hypergraafeille.)

Esim. tapaus r=3 ja t=1 on tuntematon! Aivan viime aikoina ollaan tosin selvitetty vastaavia ominaisuuksia 3-graafeille, jotka eivät sisällä jotain muuta pientä ja symmetristä 3-graafia:

http://www.emis.de/journals/EJC/Volume_10/PDF/v10i1r18.pdf
http://www.springerlink.com/content/g2u53kn62355vt12/fulltext.pdf

Ekassa paperissa (2003) kielletty hypergraafi on tietty viiden solmukohdan ja neljän kolmikon 3-graafi. Tokassa (2005) kielletty 3-graafi on seitsemän solmukohdan ja seitsemän kolmikon 'Fano plane':

http://en.wikipedia.org/wiki/Fano_plane

Jälkimmäisen paperin Peter Keevashin muuten tunnen: tyyppi teki väitöskirjan Cambridgessa ja on nyt Lontoon Queen Maryssa, jonne olen Cambridgen ohella hakenut väitöskirjapaikkaa.

Varmastikin alkuperäisen ongelman tapaus r=3, t=1 olisi selvitetty tietokoneella jos mahdollista... Yrityksiä on ollut vuosikymmeniä, mutta kyseessä on yksi kombinatoriikan suuria avoimia ongelmia. Ongelma näyttää ärsyttävän helpolta vaikeuteensa nähden.

Olen siis varsin skeptinen, että pystyisit ratkaisemaan ohjelmointikeinoin tapauksen r=7, t=25. Mutta on sitä tietysti ihmeellisimpiäkin asioita nähty.

nkorppi kirjoitti:

Huomaa, että tämä on yksittäistapaus Turanin ongelmasta hypergraafeille:

Etsi maksimaalinen 7-graafi, joka ei sisällä täydellistä 32 solmukohdan 7-graafia.

Kyseessä on tapaus r=7, t=25 seuraavasta:

Turanin ongelma: Mikä on maksimaalinen r-graafi, joka ei sisällä täydellistä (r t)-solmukohdan r-graafia.

Tapaus r=2, eli perinteisten graafien tapaus on tietenkin ratkaistu, mutta kun r>2, oikeastaan juuri mitään ei tiedetä! (Yksi ongelma seuraa todistuksesta, että perinteisten graafien Erdös-Stone-tyyppinen teoreema ei voi päteä hypergraafeille.)

Esim. tapaus r=3 ja t=1 on tuntematon! Aivan viime aikoina ollaan tosin selvitetty vastaavia ominaisuuksia 3-graafeille, jotka eivät sisällä jotain muuta pientä ja symmetristä 3-graafia:

http://www.emis.de/journals/EJC/Volume_10/PDF/v10i1r18.pdf
http://www.springerlink.com/content/g2u53kn62355vt12/fulltext.pdf

Ekassa paperissa (2003) kielletty hypergraafi on tietty viiden solmukohdan ja neljän kolmikon 3-graafi. Tokassa (2005) kielletty 3-graafi on seitsemän solmukohdan ja seitsemän kolmikon 'Fano plane':

http://en.wikipedia.org/wiki/Fano_plane

Jälkimmäisen paperin Peter Keevashin muuten tunnen: tyyppi teki väitöskirjan Cambridgessa ja on nyt Lontoon Queen Maryssa, jonne olen Cambridgen ohella hakenut väitöskirjapaikkaa.

Varmastikin alkuperäisen ongelman tapaus r=3, t=1 olisi selvitetty tietokoneella jos mahdollista... Yrityksiä on ollut vuosikymmeniä, mutta kyseessä on yksi kombinatoriikan suuria avoimia ongelmia. Ongelma näyttää ärsyttävän helpolta vaikeuteensa nähden.

Olen siis varsin skeptinen, että pystyisit ratkaisemaan ohjelmointikeinoin tapauksen r=7, t=25. Mutta on sitä tietysti ihmeellisimpiäkin asioita nähty.

Niin, tietysti meillä on lisäksi parametri n, eli fiksattu määrä solmukohtia. Tuon parametrin arvosta ei ole mainittavaa hyötyä kuin triviaaleissa tapauksissa.

... tarkoittavat tässä mitä?

Ei minua muuten ahdista tietokoneratkaisut, (kaksi viidesosaa kursseistani ovat algoritmipainotteisia), mutta mielelläni haluaisin ymmärtää muutkin tapaukset kuin pelkästään n=39 ja r=7. On jotenkin ilotonta laittaa tietokone hakemaan jotain alarajaa, ymmärtämättä miksi päädyttiin juuri siihen lukuun.

Kommentti "Tiedät varmaankin..."-viestiin:

Ajatus on tietenkin väärin, sillä sehän tarkoittaisi
sitä, että nolla oikein takaava systeemi takaisi myös
seitsemän oikein.

Arvaus "Pikkupähkinä"- ketjuun:

Alitajuntani sanoo, että sanan pituus voi olla:
n*(n-1) 1, esim. 26 * 25 1 = 651

hente13 kirjoitti:

Kommentti "Tiedät varmaankin..."-viestiin:

Ajatus on tietenkin väärin, sillä sehän tarkoittaisi
sitä, että nolla oikein takaava systeemi takaisi myös
seitsemän oikein.

Arvaus "Pikkupähkinä"- ketjuun:

Alitajuntani sanoo, että sanan pituus voi olla:
n*(n-1) 1, esim. 26 * 25 1 = 651

että tulos nolla oikein takaisi johonkin riviin seitsemän oikein. Totesin vain, että nollarivin takaaminen LISÄÄ MENESTYKSEN TODENNÄKÖISYYTTÄ muissa riveissä. Voiton odotusarvo koko systeemissä kun pysyy muuttumattomana.

hente13 kirjoitti:

Kommentti "Tiedät varmaankin..."-viestiin:

Ajatus on tietenkin väärin, sillä sehän tarkoittaisi
sitä, että nolla oikein takaava systeemi takaisi myös
seitsemän oikein.

Arvaus "Pikkupähkinä"- ketjuun:

Alitajuntani sanoo, että sanan pituus voi olla:
n*(n-1) 1, esim. 26 * 25 1 = 651

... taisi heittää sinua metsikköön 67108212 yksiköllä. Hups. :)

... yksi Furedin paperi näistä ongelmista, mm. siitä kuinka monta riviä tarvitaan jotta saataisiin vähintään r oikein:

http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_lotto.pdf

Sivulla 5 mainitaan, että oman tehtäväsi ongelma oli 1995 avoin kaikille kahta numeroa suuremmille lottoriveille, ja paras yleisesti tunnettu tulos antaa alarajaksi 5.06, mikä ei auta tähän tapaukseen, kun tiedämme jo alarajaksi 8. ;)

Saadaan suoraan
P(x0) = (7 yli 0)*(32 yli 7)/(39 yli 7)
= 3365856/15380937 = 0.218832961.

Tarkoitit varmaan että tarvittavien rivien määrän voisi lukea osoittajasta, mutta niitä on jo aika paljon jos miettii että noin joka viides kerta pitäisi tulla nolla oikein.

... siitä osoittajaksi siirtämisestä olisi hyötyä? Todennäköisyyden laskeminen on yhtäpitävä ja yhtäläisen vaikea ongelma kuin rivien määrän laskeminen. Jotta ratkaisuun päästäisiin, ei yleensä riitä että muuttaa tehtävän muotoilua -- pitää tehdä jotain konkreettista.

Vaikeusasteesta saa vihjettä, kun tajuaa, että kyseessä on yksittäistapaus Turanin hypergraafi-ongelmasta -- todella vaikea avoin ongelma.

nkorppi kirjoitti:

... siitä osoittajaksi siirtämisestä olisi hyötyä? Todennäköisyyden laskeminen on yhtäpitävä ja yhtäläisen vaikea ongelma kuin rivien määrän laskeminen. Jotta ratkaisuun päästäisiin, ei yleensä riitä että muuttaa tehtävän muotoilua -- pitää tehdä jotain konkreettista.

Vaikeusasteesta saa vihjettä, kun tajuaa, että kyseessä on yksittäistapaus Turanin hypergraafi-ongelmasta -- todella vaikea avoin ongelma.

osoittajasta voidaan ainoastaan lukea niiden rivien lukumäärä, joissa ei ole yhtään oikein. Auttaako se sitten missään, en tiedä.

jens kirjoitti:

osoittajasta voidaan ainoastaan lukea niiden rivien lukumäärä, joissa ei ole yhtään oikein. Auttaako se sitten missään, en tiedä.

Sorry, meni itseltä osoittaja ja nimittäjä sekaisin!
Kysyttiin, montako riviä pitää pelata, että saa _varmasti_ rivin, jossa ei ole yhtään oikein!

Eikös tuo juuri ole vastaus esitetyyn kysymykseen?!

Aivan analogisesti: montako riviä on pelattava, että saa _varmasti_ seitsemän oikein? Vastaus: [39 yli 7].

Mitä kysyttiin? kirjoitti:

Sorry, meni itseltä osoittaja ja nimittäjä sekaisin!
Kysyttiin, montako riviä pitää pelata, että saa _varmasti_ rivin, jossa ei ole yhtään oikein!

Eikös tuo juuri ole vastaus esitetyyn kysymykseen?!

Aivan analogisesti: montako riviä on pelattava, että saa _varmasti_ seitsemän oikein? Vastaus: [39 yli 7].

Tuohan oli tehtävä: varmasti nolla oikein? Oikeasssa olit kuitenkin alunperinkin. Rivien lkm pysyy nimittäjässä, jos koko laskelma hoidetaan 1/jotain periaatteella.
nKorppi:ei tuohon tehtävään kovin syvällistä matikkaa tartte. Seinäjoen ja Vaasan välillä voi junien liikkumisen laskea ilman suhteellisuusteoriaakin ;-).

nkorppi kirjoitti:

... siitä osoittajaksi siirtämisestä olisi hyötyä? Todennäköisyyden laskeminen on yhtäpitävä ja yhtäläisen vaikea ongelma kuin rivien määrän laskeminen. Jotta ratkaisuun päästäisiin, ei yleensä riitä että muuttaa tehtävän muotoilua -- pitää tehdä jotain konkreettista.

Vaikeusasteesta saa vihjettä, kun tajuaa, että kyseessä on yksittäistapaus Turanin hypergraafi-ongelmasta -- todella vaikea avoin ongelma.

Tuohan on tilastotieteen tai todennaköisyyslaskennan ekakurssin harjoitustehtävä. Soita Veikkauksen pääkonttoriin ja kysy joku matemaatikko puhelimeen. Varmaan ehtii vastaamaankin kesken vaativan tuotekehittelytyön.

Mitä kysyttiin? kirjoitti:

Sorry, meni itseltä osoittaja ja nimittäjä sekaisin!
Kysyttiin, montako riviä pitää pelata, että saa _varmasti_ rivin, jossa ei ole yhtään oikein!

Eikös tuo juuri ole vastaus esitetyyn kysymykseen?!

Aivan analogisesti: montako riviä on pelattava, että saa _varmasti_ seitsemän oikein? Vastaus: [39 yli 7].

rivejä on 15380937 kpl. Nolla oikein rivejä on 3365856 kpl. Sitten erotuksena saadaan ne rivit 12015081 kpl, joissa on jokaisessa ainakin yksi oikein. Jos veikkaat 12015081 1 riviä niin varmasti sattuu ainakin yksi nolla oikein rivi.

Turhaan valitat kirjoitti:

Tuohan oli tehtävä: varmasti nolla oikein? Oikeasssa olit kuitenkin alunperinkin. Rivien lkm pysyy nimittäjässä, jos koko laskelma hoidetaan 1/jotain periaatteella.
nKorppi:ei tuohon tehtävään kovin syvällistä matikkaa tartte. Seinäjoen ja Vaasan välillä voi junien liikkumisen laskea ilman suhteellisuusteoriaakin ;-).

... siihen vaaditaan syvällistä matikkaa, tai ainakin aivan uudenlaisia ideoita. Ongelma on tietysti absoluuttisen MINIMIN selvittäminen.

Suosittelen tutustumaan Turanin hypergraafi-ongelmaa tutkiviin papereihin, esim.

http://www.combinatorics.org/Volume_12/PDF/v12i1n11.pdf

Kombinatoriikan perusluonne on se, että kysymykset ovat helpon kuuloisia, mutta ratkaisut vaikeita.

Tsiisus sentään kirjoitti:

Tuohan on tilastotieteen tai todennaköisyyslaskennan ekakurssin harjoitustehtävä. Soita Veikkauksen pääkonttoriin ja kysy joku matemaatikko puhelimeen. Varmaan ehtii vastaamaankin kesken vaativan tuotekehittelytyön.

Olenhan jo osoittanut, että kyseessä on erikoistapaus Turanin hyper-graafi-ongelmasta, jonka yleinen ratkaisu on täysin hämärän peitossa.

Myös ratkaisu tähän yksittäiseen tapaukseen saattaa olla ainakin lähes yhtä vaikea.

Esim. tässä on täysin avoin ongelma matematiikassa: "Mikä on maksimimäärä 3-pituisia lottorivejä n-numeroisessa lotossa, niin että emme ole luetelleet minkään nelikon jokaista kolmikkoa."

Kysymys voi kuulostaa yksinkertaiselta, mutta ratkaisu on täysin avoin.

jens kirjoitti:

rivejä on 15380937 kpl. Nolla oikein rivejä on 3365856 kpl. Sitten erotuksena saadaan ne rivit 12015081 kpl, joissa on jokaisessa ainakin yksi oikein. Jos veikkaat 12015081 1 riviä niin varmasti sattuu ainakin yksi nolla oikein rivi.

... myös 15 riviä riittää varmasti. Kysymys onkin: Mikä on absoluuttinen minimi?

Tiedämme, että se on välillä 8-15, mutta mikä niistä voi hyvinkin olla täysin avoin ongelma. Luultavasti onkin.

nkorppi kirjoitti:

Olenhan jo osoittanut, että kyseessä on erikoistapaus Turanin hyper-graafi-ongelmasta, jonka yleinen ratkaisu on täysin hämärän peitossa.

Myös ratkaisu tähän yksittäiseen tapaukseen saattaa olla ainakin lähes yhtä vaikea.

Esim. tässä on täysin avoin ongelma matematiikassa: "Mikä on maksimimäärä 3-pituisia lottorivejä n-numeroisessa lotossa, niin että emme ole luetelleet minkään nelikon jokaista kolmikkoa."

Kysymys voi kuulostaa yksinkertaiselta, mutta ratkaisu on täysin avoin.

Käsitin kyllä, että alkuperäinen kysymys kuului: "Montako riviä on lotottava, että täysin varmasti saa johonkin riviin 0 oikein?". Yllähän tuo jo laskettukin, siis _täysin varmoja_ voidaan olla vain, jos lototaan niin paljon, ettei ole 1,2, ... tai 7 oikein, eli vähennetään kaikkien mahdollisten rivien lkm:stä niiden rivien lkm, joissa on vähintään 1 oikein.
Empiria kyllä on osoittanut, että 0-oikein voi saada yhdelläkin rivillä, ja vielä varmemmin, kun ei lottoa ollenkaan :-).
Voihan Seinäjoki-Vaasa-junan nopeuden laskea myös suhteellisuusteorian avulla, mutta vähemmälläkin selviää. Tämä nyt ei tarkoita, etteikö yleisten ratkaisujen haku olisi kunnioitettavaa!

ghgfdrt kirjoitti:

Käsitin kyllä, että alkuperäinen kysymys kuului: "Montako riviä on lotottava, että täysin varmasti saa johonkin riviin 0 oikein?". Yllähän tuo jo laskettukin, siis _täysin varmoja_ voidaan olla vain, jos lototaan niin paljon, ettei ole 1,2, ... tai 7 oikein, eli vähennetään kaikkien mahdollisten rivien lkm:stä niiden rivien lkm, joissa on vähintään 1 oikein.
Empiria kyllä on osoittanut, että 0-oikein voi saada yhdelläkin rivillä, ja vielä varmemmin, kun ei lottoa ollenkaan :-).
Voihan Seinäjoki-Vaasa-junan nopeuden laskea myös suhteellisuusteorian avulla, mutta vähemmälläkin selviää. Tämä nyt ei tarkoita, etteikö yleisten ratkaisujen haku olisi kunnioitettavaa!

... on edelleen ihan sama, mutta logiikkasi sen ratkaisuun on päin mäntyä -- tehtävä on vaikeampi kuin luulet.

Sinun ei suinkaan tarvitse VÄLTTÄÄ kaikkia rivejä joissa on vähintään yksi oikein, saadaksesi varmasti nolla-oikein rivin.

Riittää, että sinulla on ainakin yksi rivi jokaisen mahdollisen tulosrivin ulkopuolella. Ongelma on siinä, ettei näiden tarvitse suinkaan olla eri rivejä! Yksi rivi kun on 3365856 rivin ulkopuolella. Tehtävän vaikeus perustuu siihen, ettei ole helppoa keinoa tietää 'päällekkäisyyden optimimäärää'.

Tässäkin ketjussa on jo esitetty 15 rivin taktiikka, joka sisältää aina varmasti yhden nolla-oikein rivin. Kysymys kuuluu: Kuinka pieni rivimäärä riittää tähän?

Voit naureskella ihan rauhassa siitä, miten 'helppo' ongelma on kyseessä, mutta tämä ongelma on ihan aito matematiikan tutkimuskohde -- avoin sellainen. Kysymys on vaikeampi kuin miltä näyttää.

ghgfdrt kirjoitti:

Käsitin kyllä, että alkuperäinen kysymys kuului: "Montako riviä on lotottava, että täysin varmasti saa johonkin riviin 0 oikein?". Yllähän tuo jo laskettukin, siis _täysin varmoja_ voidaan olla vain, jos lototaan niin paljon, ettei ole 1,2, ... tai 7 oikein, eli vähennetään kaikkien mahdollisten rivien lkm:stä niiden rivien lkm, joissa on vähintään 1 oikein.
Empiria kyllä on osoittanut, että 0-oikein voi saada yhdelläkin rivillä, ja vielä varmemmin, kun ei lottoa ollenkaan :-).
Voihan Seinäjoki-Vaasa-junan nopeuden laskea myös suhteellisuusteorian avulla, mutta vähemmälläkin selviää. Tämä nyt ei tarkoita, etteikö yleisten ratkaisujen haku olisi kunnioitettavaa!

... jotta varmasti vältetään kaikki 'vähintään yksi oikein'-rivit, piti lotota 12015082 riviä.

Mutta on jo esitetty tapa, jolla 15 riviä riittää siihen, että ollaan TÄYSIN VARMOJA nolla-oikein-rivistä.

Mielestäni 15 < 12015082.

Minimimäärä rivejä on 8 ja 15 välissä.

ghgfdrt kirjoitti:

Käsitin kyllä, että alkuperäinen kysymys kuului: "Montako riviä on lotottava, että täysin varmasti saa johonkin riviin 0 oikein?". Yllähän tuo jo laskettukin, siis _täysin varmoja_ voidaan olla vain, jos lototaan niin paljon, ettei ole 1,2, ... tai 7 oikein, eli vähennetään kaikkien mahdollisten rivien lkm:stä niiden rivien lkm, joissa on vähintään 1 oikein.
Empiria kyllä on osoittanut, että 0-oikein voi saada yhdelläkin rivillä, ja vielä varmemmin, kun ei lottoa ollenkaan :-).
Voihan Seinäjoki-Vaasa-junan nopeuden laskea myös suhteellisuusteorian avulla, mutta vähemmälläkin selviää. Tämä nyt ei tarkoita, etteikö yleisten ratkaisujen haku olisi kunnioitettavaa!

... olisi itse asiassa oikein, JOS lottorivit olisi valittava sattumanvaraisesti.

Kysymys ei kuitenkaan kieltänyt aivojen käyttöä: saamme valita rivit paljon nokkelammin. Ei kysytty minimimäärää rivejä, niin että 'mitkä tahansa niin monta riviä riittäisivät'.

Kysyttiin minimimäärää sillä oletuksella, että rivit voi valita nimenomaan siihen tarkoitukseen, että siellä olisi nolla-oikein rivi.