Luet Solmun keskustelupalstan arkistoa. Uusia viestejä ei voi enää kirjoittaa. Solmu
Sivu: 1
Lotto (Luettu 20 kertaa)
Juhister
YaBB Newbies
*
Poissa

I Love YaBB 2!

Viestejä: 3

Lotto
27.01.2013 - 10:48:22
 
Olkoon n=1,...,7.

Monellako rivillä saadaan vähintään n osumaa kuponkiin? Anna esimerkki riittävästä rivien joukosta.

Pelataan suomalaista lottoa 7 numeron riveillä ja välittämättä lisänumeroista.
Siirry sivun alkuun
 
 
  IP on kirjattu
Juhister
YaBB Newbies
*
Poissa

I Love YaBB 2!

Viestejä: 3

Re: Lotto
Vastaus #1 - 27.01.2013 - 10:48:57
 
Pidempi versio:

Kuten tiedämme, suomalaisen loton numerot ovat väliltä 1-39. Oikea rivi tulee koostumaan seitsemästä eri numerosta, jotka arvotaan. (Unohdetaan lisänumerot.) Jokainen loton pelaaja veikkaa lottorivejä, joissa on jokaisessa seitsemän erillistä numeroa. Jos pelaajan lottorivin numero esiintyy oikeassa rivissä, se lasketaan osumaksi. Mitä enemmän osumia pelaaja saa, sitä enemmän rahaa hän voittaa. (Unohdetaan voitonjako. Lisäksi unohdetaan pelaajat, jotka pelaavat yli seitsemän numeron lottorivejä.)

(*) Nyt pelaamalla seitsennumeroisia lottorivejä "fiksusti"

5 riviä, kupongissa on rivi, jossa on vähintään yksi osuma;
6 riviä, kupongissa on rivi, jossa on vähintään kaksi osumaa;
a riviä, kupongissa on rivi, jossa on vähintään kolme osumaa;
b riviä, kupongissa on rivi, jossa on vähintään neljä osumaa;
c riviä, kupongissa on rivi, jossa on vähintään viisi osumaa;
d riviä, kupongissa on rivi, jossa on vähintään kuusi osumaa;
15 380 937 riviä, kupongissa on rivi, jossa on vähintään seitsemän osumaa.

Luvut 5, 6 ja 15 380 937 ovat pienimmät mahdolliset lukuarvot, jotka toteuttavat niitä vastaavat ehdot. (Näyttää siltä, en todista asiaa.)

Kysymykset:

Mitkä ovat lukujen a, b, c ja d pienimmät mahdolliset lukuarvot, niin että niitä vastaavat ehdot toteutuvat? Mitkä ovat lukuja a-d vastaavat esimerkit "fiksuista" lottoriveistä?

Perustelu luvuille 5, 6 ja 15 380 937:

5)

Jos pelataan lottorivit

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

johonkin riviin tulee aina osuma, koska jäljelle jääviä numeroita 36, 37, 38, 39 on vain neljä. Arvottavat seitsemän numeroa sisältävät jonkun muun numeron, joka esiintyy pelatuissa lottoriveissä. Siis pelaamalla kuten yllä

5 riviä, kupongissa on rivi, jossa on vähintään yksi osuma,

joten väitteen (*) ensimmäinen rivi on järkevä.

6)

Jos pelataan lottorivit

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

niin pelattuja rivejä on kuusi ja niissä esiintyvät kaikki numerot 1-39. Jokainen arvottu numero on siis jossakin pelatuista riveistä. Koska arvotut seitsemän numeroa ovat kuudessa rivissä, jossakin rivissä on pakko olla kaksi arvottua numeroa. Siis pelaamalla kuten yllä

6 riviä, kupongissa on rivi, jossa on vähintään kaksi osumaa

joten väitteen (*) toinen rivi on järkevä.

15 380 937)

Erilaisia lottorivejä on
39!/(7!*(39-7)!)=15 380 937 kpl. Siis pelaamalla kaikki nämä rivit joku riveistä on sisältää kaikki seitsemän arvottua numeroa. Näin ollen väitteen (*) seitsemäs rivi on järkevä.
Siirry sivun alkuun
 
 
  IP on kirjattu
Juhister
YaBB Newbies
*
Poissa

I Love YaBB 2!

Viestejä: 3

Re: Lotto
Vastaus #2 - 27.01.2013 - 22:30:58
 
Tässä on sekavaa pohdintaa luvuista, sekä joitakin ylärajoja.

Lähettäjä: Juha-Matti Huusko
Lähetetty: 5. tammikuuta 2013 20:26
Vastaanottaja: Taneli Korhonen
Aihe: VS: Lottotehtävä

150 riittää - kolmen osuman tapaus
en parantanut 8245 - neljän osuman tapaus
1 846 880 riittää? - viiden numeron tapaus
3 262 623 riittää? - kuuden numeron tapaus

Kirjoitan tähän kommentin ja sitten tuloksien johdot.

Joo, tuossa oli taas hyvä ajatus. Muodostettujen rivien pareittaiset leikkaukset ovat (viimeistä riviä lukuunottamatta) kaksioita, joten rivit sisältävät erillisiä kolmikoita. Ehkä jatkossakin tehokasta kattamista saataisiin, jos rivien pareittaiset leikkaukset olisivat mahdollisimman pieniä. Ehkä tätä voisi käyttää jäsentävänä johtoajatuksena, jos työtä vielä jatkaisi käsin.

Asian pohtiminen käsin menee kyllä turhan hankalaksi. Jollakin yksinkertaisella kuviolla tai ajatuksella voisi ehkä saada keksittyä muutaman rivin lisää.

Ehkä jonkun pienemmän, mutta vastaavanlaisen tehtävän ratkaiseminen voisi valaista tätä tehtävää. Jos vaikka ajattelisi kolmen numeron lottorivejä numeroilla 1-11 tai viiden numeron lottorivejä numeroilla 1-7 yms., niin optimoinnin voisi viedä loppuun. Ehkä tällöin optimoinnin voisi viedä loppuun myös varsinaisessa tehtävässä.

Tällaisia tehtäviä voisi miettiä yleisemminkin ja pohtia numerojoukkojen {1,...,n} jakamista ryhmiin, kombinaatioiden kattamista, asioiden kirjoittamista tietokoneelle jne.

Luulen, että osaisin juuri ja juuri tehdä tästä Matlab-juttuja. Jos olisi keksitty ja kirjoitettu (tai tietokoneella tuotettu) kombinaatiot kattava rivien joukko, niin ylimääräisiä rivejä voitaisiin lähteä eliminoimaan. Tällöin pitäisi voida testata, onko suppeampi rivien joukko vielä kattava. Tuntuu myös, että eliminaationkin pitäisi ehkä tapahtua jollain tietyllä tavalla. Jos eliminaatio alkaa "tyhmästi", niin umpikuja voidaan kai saavuttaa ennenaikaisesti. Ehkä tietokoneella voisi tehdä kaikki mahdolliset eliminaatiopolut. Jos eliminoitavissa olevia rivejä on 100 ja ne voidaan eliminoida missä tahansa järjestyksessä, niin tietokoneen pitäisi tietysti tehdä 100! erilaista eliminaatiopolkua.

Tässä on tuloksien johdot.
>>>>>>>>>

Toisenlaisella aloituksella 150 riviä riittää kolmen osuman tapauksessa. Jaetaan numerot 1-39 yhtä suuriin luokkiin 1-13, 14-26, 27-39. Nyt, kun valitaan numeroista 1-39 seitsemän, yhdestä luokasta valitaan välttämättä kolme. Riittää siis kattaa näiden luokkien kaikki 3-kombinaatiot. Riittää keksiä rivit, jotka kattavat numeroiden 1-13 kaikki 3-kombinaatiot. Tämän jälkeen rivien numeroihin voidaan lisätä +13 ja +26 => numeroiden 14-26 ja 27-39 3-kombinaatiot saadaan katettua.

Numeroiden 1-13 3-kombinaatioita on 13!/(3!*10!)=286 kpl
rivi 1-7 kattaa 35 kpl
rivi 1,8,9,10,11,12,13 35 kpl
jäljellä ovat 3-kombinaatiot, joissa on

a) 2 numeroista 1-7 ja 1 numeroista 8-13: 7!/(2!*5!)*6=126kpl
b) 1 numeroista 2-7 ja 2 numeroista 8-13: 6*6!/(2!*4!)=90kpl

a) voidaan kattaa riveillä
valitaan 6 numeroista 1-7 ja 1 numeroista 8-13: 7*6=42 kpl
b) voidaan kattaa riveillä
valitaan 1 numeroista 2-7 ja numerot 8-13: 6*1=6 kpl

Tarvittiin 2+42+6=50 riviä kattamaan numeroiden 1-13 3-kombinaatiot. Vastaavasti 14-26 ja 27-39 vaativat kumpikin 50 riviä. Siis 150 riviä riittää.

>>

Tässä on vähän suttuisia perusteluja, nämä pitäisi kirjoittaa paremmin ja ajatella vielä läpi. Tässä on kuitenkin se toimiva ajatus, että neljän osuman tapausta voisi käyttää hyväksi viiden osuman tapaukseen ja seitsemän osuman tapausta kuuden osuman tapaukseen, jotta saataisiin parempia ylärajoja kuin 15 380 937.

8245 riviin tulee neljä oikein. Halutaan saada viisi oikein. Tehdään rivit, joissa 1. numero on muutettu, yht. 32 tapaa. Tehdään rivit, joissa 2. numero on muutettu, 32 tapaa. jne. Pitää tehdä 8245*5*32= 1 846 880 uutta riviä.

15 380 937 riviin tulee seitsemän oikein. Halutaan saada kuusi oikein. Laitetaan rivit, joissa i=1. numeroa lukuunottamatta numerot ovat samoja luokkiin. Joka luokkaan tulee 33 riviä (ja luokkia on 39!/(6!*33!) kpl, mutta ei välitetä tästä). Otetaan joka luokasta yksi rivi ja tuhotaan muut. Annetaan i=1,...,7. Siis
15 380 937*7/33 riviä riittää.

t.Juha-Matti

Lähettäjä: Taneli Korhonen
Lähetetty: 5. tammikuuta 2013 13:28
Vastaanottaja: Juha-Matti Huusko
Aihe: VS: Lottotehtävä

Tosiaan, ilmeinen parannus, joka ei jostain syystä tullut heti mieleen. Kuten Juha-Matti arvelitkin, pienellä työllä sain jatkettua rivien vähentämistä kolmen osuman tapauksessa jo 696:een ja neljän osuman tapauksessa 8245:een. Alla muodostamani rivit, joilla tämä onnistui. Menetelmän loppuun asti vieminen ilmeisesti vaatisi kuitenkin joko melkoisen paljon aikaa, tai tietokoneella laskemista.

Jatkamalla kolmen osuman kohdassa valittuihin riveihin 1-7,8-14,20-26 ja 27-33 saadaan riveillä

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

kullakin viimeistä lukuun ottamatta katettua 35, ja viimeisellä rivillä 33 ({20,35,36} ja {29,35,37} ovat jo mukana), uutta kombinaatiota. Nyt on siis osioissa 1-19 ja 20-37 katettu 6*35=210 ja 5*35+33=208 kombinaatiota kuudella rivillä kummassakin. Tämän jälkeen yksittäisten uusien rivien "tehokkuus" ilmeisesti laskee (ainakaan jo tehdyille valinnoille en enää keksinyt lisärivejä, joilla saataisiin 35 uutta kombinaatiota katettua, välin 1-19 tapauksessa kylläkin löytyy kaiketi vielä 33-tehokkuuksisia rivejä).

Jos nyt loput kombinaatiot katettaisiin pareittain, niin tarvittavien rivien määrä olisi enää 12+(969-210+1)/2+(816-208)/2=696. Jatkamalla rivien tehokkaampaa kattavuustulkintaa ja järkeviä valintoja päästäisiin tietysi vielä pienempään tulokseen, mutta mielenkiintoni ei taida riittää ainakaan käsin enää etsiä seuraavia rivejä. On toki myös mahdollista, että tässä valitut rivit olisi voinut muodostaa jatkoa ajatellen paremminkin.


Neljän osuman tapauksessa saadaan rivien 1-7,8-14,21-27 ja 28-34 lisäksi ainakin valinnoilla

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

saadan kullakin katettua 35 kombinaatiota. Jos loput katettaisiin ajatellen vain rivi/kombinaatio, tarvittaisiin rivejä 14+4845+3876-14*35=8245. Jatkamalla edelleen rivien järkevää valintaa saadaan määrää tässäkin pienemmäksi, mutta ainakin minulle alkaa päässälaskien käydä hieman turhan hankalaksi.


Mitä viiden ja kuuden osuman tapauksiin tulee, niin niissähän lukujoukon jakaminen kahteen lähes yhtäsuureen osaan ei ainakaan tällä samalla idealla onnistu. Tässä haettu jokaisella rivillä katettujen kombinaatioiden määrän maksimointi kylläkin toimisi, jos tarkasteluun otetaan viiden osuman tapauksessa luvut 1-37 ja kuuden osuman tapauksessa 1-38. Luvut 38 ja 39 (5 osumaa), sekä 39 (6 osumaa) voidaan tietysti jättää tarkastelematta samalla perusteella, kuin luvut 38 ja 39 unohdettiin kolmen osuman tapauksessa.

t. Taneli

Lähettäjä: Juha-Matti Huusko
Lähetetty: 4. tammikuuta 2013 18:52
Vastaanottaja: Taneli Korhonen; Martti Pesonen; tsareq@gmail.com; Marko Lamminsalo
Aihe: VS: Lottotehtävä

Ylärajoja tarvittavien rivien lukumäärille:
Taneli: 893 (kolme osumaa) ja 8721 (neljä osumaa)
Juha-Matti: 827 ja 8655, koska ylläolevia lukuja voidaan pienentää 66:lla. [66=2*7!/(3!4!)-4]

Joo, Taneli, tämä tuntuu järkevältä. Hyvä, kun ratkaisu edistyy. Nuo 893 ja 8721 rivin strategiat antavat minustakin toimivat rivit. Keksin jo yhden parannusidean. 1) ja 2) ovat kommentteja ja 3):n lopussa on parannusidea.

1) "Jaetaan luvut osiin 1 - 19, 20 - 37, sekä 38 ja 39." Ainakin tämänmuotoisella jaolla ongelmaan pääsee käsiksi. En keksi parempaa. Nyt nuo 969 ja 816 kombinaatiota pitäisi tosiaan sisällyttää lottoriveihin.

2) "Yhteen seitsemän numeron riviin saadaan mukaan kaksi tällaista kombinaatiota, joten kaikki kombinaatiot saadaan mukaan 485 + 408 = 893 rivillä." Tässä tosiaan 2*485=970 ja 2*408=816. Siis ensimmäiseen 485 riviin voidaan 969 kombinaatiota sisällyttää pareittain ja sitten 408 riviin voidaan sisällyttää 816 kombinaatiota pareittain. (Esim. 1,2,3,4,5,6,7 sisältää kombinaatiot {1,2,3} ja {4,5,6}.) Rivimäärällä 485+408=893 voidaan siis kattaa kaikki kombinaatiot ja voidaan tehdä loppupäätelmä.

3) Tuntuu, että tässä voisi keksiä tehokkaammankin ajatuksen kombinaatioiden kattamiseen pareittaisen kattamisen sijasta. Esim. lottorivi 1,2,3,4,5,6,7 kattaa jo 7!/(3!4!)=35 luvuista 1-19 koostuvaa kolmen numeron kombinaatiota. Rivit 1-7,8-14,20-26 ja 27-33 kattavat näin jokainen 35 eri kombinaatiota. Näillä neljällä rivillä saadaan katettua 2*35=70 lukujen 1-19 3-kombinaatiota ja 70 lukujen 2-37 3-kombinaatiota. Nyt kun kombinaatioita on sisällytetty tehokkaasti, voitaisiin loput käsitellä sisällyttämällä ne riveihin pareittain. Näyttää siltä, että 4+(969-70+1)/2+(816-70)/2=827 riviä riittää. Tämä on 66 riviä vähemmän kuin 893 riviä. Samalla periaatteella neljän osuman tapauksessa voidaan päästä ainakin 66 riviä vähemmällä eli 8655 rivillä.

Kun nämä 4*35 kombinaatiota tai ensimmäiset 35 kombinaatiota on saatu mukaan, miten voitaisiin jatkaa yhtä tehokkaasti?

Ehkä jollakin muullakin tavalla voisi saada pienemmät luvut eli jossakin muussakin kohtaa voisi säästää.

t.Juha-Matti

Lähettäjä: Taneli Korhonen
Lähetetty: 4. tammikuuta 2013 12:48
Vastaanottaja: Juha-Matti Huusko; Martti Pesonen; tsareq@gmail.com; Marko Lamminsalo
Aihe: VS: Lottotehtävä

Tällaisen melko raa'an ratkaisun keksin kolmen osuman tapaukseen 893 rivillä. En tosin osaa sanoa, onko tämä paras ratkaisu.

Perustelu:

Valitaan rivit seuraavasti:
Jaetaan luvut osiin 1 - 19, 20 - 37, sekä 38 ja 39. Muodostetaan rivit kahdesta ensimmäisestä lukujoukosta siten, että niihin saadaan mukaan kaikki kolmen numeron kombinaatiot ko. joukosta.

Luvuista 1 - 19 voidaan muodostaa 19!/(3!*16!) = 969 ja luvuista 20 - 37 (18 kpl) 18!/(3!*15!) = 816 eri kolmen numeron kombinaatiota. Yhteen seitsemän numeron riviin saadaan mukaan kaksi tällaista kombinaatiota, joten kaikki kombinaatiot saadaan mukaan 485 + 408 = 893 rivillä.

Jos nyt seitsemästä oikeasta numerosta kaksi sattuisivat olemaan riveistä puuttuvat 38 ja 39, niin jäljelle jäävistä viidestä oikeasta numerosta on aina vähintään kolme joko välillä 1 - 19 tai välillä 20 - 37. Rivien valinnasta johtuen kummassakin tapauksessa nuo kolme numeroa löytyvät jostakin yhdestä rivistä.


Vastaavalla idealla saadaan neljän osuman tapauksessa ratkaisu 8721 rivillä, kun jaetaan kaikki numerot 1 - 39 kahteen osaan 1 - 20 ja 21 - 39. Näistä saadaan 4845 ja 3876 neljän numeron yhdistelmää, joiden kattamiseen tarvitaan 4845 + 3876 = 8721. Tähänkin tietysti saattaisi löytyä parempikin ratkaisu.


t. Taneli
Siirry sivun alkuun
 
 
  IP on kirjattu
Hermanni
YaBB Newbies
*
Poissa

I Love YaBB 2!

Viestejä: 45

Re: Lotto
Vastaus #3 - 26.02.2013 - 21:34:55
 
Wikipedia toteaa tästä probleemasta:
Lainaus:
It is a hard, in most cases open, mathematical problem to calculate the minimum number of tickets one needs to purchase to guarantee that at least one of these tickets matches at least 2 numbers. In the 5-from-90 lotto, the minimum number that can guarantee a ticket with at least 2 matches is 100.
Siirry sivun alkuun
 
 
  IP on kirjattu
Sivu: 1