Laura ja Risto pelaavat seuraavanlaista peliä: pöydällä on n lautasta (n>1) jotka ovat alussa tyhjiä. Joka kierroksen alussa Laura siirtää osan lautasista oikealle puolelle pöytää ja loput vasemmalle. Risto valitsee toisen puolen lautaset ja lisää kuhunkin yhden rusinan, lisäksi hän tyhjentää kaikki toisen puolen lautaset. Laura voi päättää pelin tähän ja laskea hyväkseen yhden lautasen rusinat, muutoin peli lähtee uudelle kierrokselle. Osoita, että jos Risto pelaa parhaalla mahdollisella tavalla, niin Laura voi voittaa itselleen korkeintaan n - 1 rusinaa.
(Lukion matematiikkakilpailun avoin sarja 2014)
Vaikea tehtävä
12+15
36
117
Vastaukset
- tarkennusta?
Tarkoittaako Riston paras mahdollinen tapa sitä, että Laura saa lopussa mahdollisimman vähän rusinoita vai miten strategian hyvyyttä mitataan?
- 15+12
Juuri näin, Laura haluaa pitää huolen siitä, että Risto saa mahdollisimman vähän rusinoita.
- 15+12
15+12 kirjoitti:
Juuri näin, Laura haluaa pitää huolen siitä, että Risto saa mahdollisimman vähän rusinoita.
Nyt meni nimet sekaisin, eli siis Risto haluaa minimoida Lauran saamien rusinoiden määrän.
- jaaps1
15+12 kirjoitti:
Nyt meni nimet sekaisin, eli siis Risto haluaa minimoida Lauran saamien rusinoiden määrän.
Hmm. Tällaiset ratkeavat yleensä jotenkin induktion avulla tai sitten ovat erikoistapauksia jostain yleisemmästä lauseesta. Enpäs tiedä sellaista lausetta tähän hätään.
- 1+3
Nyt rasahti rusinat... Ihan mielenkiintoinen tehtävän anto kyll.
- 17+3
Jos siinä Laurakin pelaa parhaalla mahdollisella tavalla, niin hän jakaa aina ne lautaset mahdollisimman tasan molemmille puolille, joissa on eniten rusinoita.
Risto tietysti pelaa parhaalla tavalla kun tyhjentää aina sen puolen , jossa sijaitsee kuppi, jossa on eniten rusinoita ja tasamäärätapauksissa sen puolen, jossa on eniten tasamääräisiä kuppeja.
Nämä taktiikat sitten yhdistetään, ja lähdetään sitten alusta liikkeelle, eli n=2.
Noiden taktiikkojen mukaan Lauran maksimivoitto on 1, eli lautasmäärällä n=2 tulee tuo voittojen yläraja , eli n-1.
Jos n=3, niin Lauran maksimivoitto on 1, joka on n-2
Jos n=4, niin Lauran maksimivoitto on 2, joka on n-2
Jos n=5, niin Lauran maksimivoitto on 2, joka on n-3
Jos n=6, niin Lauran maksimivoitto on 2, joka on n-4
Jos n=7, niin Lauran maksimivoitto on 2, joka on n-5
Jos n=8, niin Lauran maksimivoitto on 3, joka on n-5
Jos n=16, niin Lauran maksimivoitto on 4, joka on n-12
Lauran maksimivoitto karkaa koko ajan tuosta parhaasta mahdollisesta voitosta, eli lautasmäärä n=2, ja yhden rusinan voitto.- 17+3
Jatketaas vähän:
Jos n=2^m, niin maksimivoitto on m, joka on n-(2^m-m)=> n=2^m=>m=ln(n)/ln(2)
Piti osoittaa, että maksimivoitto m on pienempi tai yhtä suuri kuin n-1.
ln(n)/ln(2) ≤ (n-1) => ln(n) ≤ ln(2)^((n-1)) => n ≤ 2^(n-1), tämä toteutuu kaikilla n > 1
Tässä on nyt osoitettu, että maksimivoitto on pienempi kuin (n-1) , kun n > 1 - 17+3
17+3 kirjoitti:
Jatketaas vähän:
Jos n=2^m, niin maksimivoitto on m, joka on n-(2^m-m)=> n=2^m=>m=ln(n)/ln(2)
Piti osoittaa, että maksimivoitto m on pienempi tai yhtä suuri kuin n-1.
ln(n)/ln(2) ≤ (n-1) => ln(n) ≤ ln(2)^((n-1)) => n ≤ 2^(n-1), tämä toteutuu kaikilla n > 1
Tässä on nyt osoitettu, että maksimivoitto on pienempi kuin (n-1) , kun n > 1Korjataan tuo viimeinen lause: Tässä on nyt osoitettu, että maksimivoitto on korkeintaan (n-1) , kun n > 1
- supermate
Miten todistat tämän? Tuo ei minusta päde, sillä jos miettii esim. n=8 tapausta. Jos Laura pelaisi näin (ensin Lauran jako ja sitten Riston vuoron jälkeinen tilanne, Risto käyttää mainittua taktiikkaa) :
0000|0000 - 0000|1111
1100|1100 - 2211|0000
2100|2100 - 3211|0000
3000|2110 - 0000|3221
3000|2210 - 0000|3320
3000|3200 - 4000|0000
Nythän Laura saa jo 4 lautaselle. - supermate
supermate kirjoitti:
Miten todistat tämän? Tuo ei minusta päde, sillä jos miettii esim. n=8 tapausta. Jos Laura pelaisi näin (ensin Lauran jako ja sitten Riston vuoron jälkeinen tilanne, Risto käyttää mainittua taktiikkaa) :
0000|0000 - 0000|1111
1100|1100 - 2211|0000
2100|2100 - 3211|0000
3000|2110 - 0000|3221
3000|2210 - 0000|3320
3000|3200 - 4000|0000
Nythän Laura saa jo 4 lautaselle.Ai niin, ja Laurahan voisi tuossa neljännellä rivillä laittaa jopa 3|2110000, jolloin Risto poistaisi vasemman puolen ja tulisi vielä enemmän noita 1 rusinan lautasia, jotka sitten voisi taas jakaa eri puolille karttumaan.
En tarkoita, että tämä taktiikka ei toimisi, mutta tätä ei ole mielestäni vielä todistettu. - 17+3
supermate kirjoitti:
Ai niin, ja Laurahan voisi tuossa neljännellä rivillä laittaa jopa 3|2110000, jolloin Risto poistaisi vasemman puolen ja tulisi vielä enemmän noita 1 rusinan lautasia, jotka sitten voisi taas jakaa eri puolille karttumaan.
En tarkoita, että tämä taktiikka ei toimisi, mutta tätä ei ole mielestäni vielä todistettu.Olet ihan oikeassa Laura saa kahdeksalla lautasella maksimivoitoksi neljä noilla taktiikoilla, (tai oikeastaan paransit Lauran taktiikkaa)
Se yleinen maksimivoitto saattaakin olla simppeli n/2 alaspäin pyöristettynä, en jaksa enempää pähkäillä. Jos niin olisi, niin helposti n/2 ≤ n-1 => n ≥ 2 - supermate
17+3 kirjoitti:
Olet ihan oikeassa Laura saa kahdeksalla lautasella maksimivoitoksi neljä noilla taktiikoilla, (tai oikeastaan paransit Lauran taktiikkaa)
Se yleinen maksimivoitto saattaakin olla simppeli n/2 alaspäin pyöristettynä, en jaksa enempää pähkäillä. Jos niin olisi, niin helposti n/2 ≤ n-1 => n ≥ 20000|0000 - 1111|0000
1100|1100 - 2211|0000
2100|2100 - 3211|0000
3|2110000 - 0|3221111
3|2211110 - 0|3322221
3220|3221 - 4331|0000
4|3310000 - 0|4421111
4210|4111 - 0000|5222
Viisikin saadaan - 17+3
supermate kirjoitti:
0000|0000 - 1111|0000
1100|1100 - 2211|0000
2100|2100 - 3211|0000
3|2110000 - 0|3221111
3|2211110 - 0|3322221
3220|3221 - 4331|0000
4|3310000 - 0|4421111
4210|4111 - 0000|5222
Viisikin saadaanViidennellä rivillä Risto tietysti parhaiten pelaamalla poistaa tuon pitkän rimpsun ja Laura joutuu tyytymään siihen neljään. Ei tässä Ristolla mitään kiveen hakattua taktiikkaa ilmeisesti olekaan, vaan tilanteen mukaan....annetaan tämän nyt olla
- supermate
17+3 kirjoitti:
Viidennellä rivillä Risto tietysti parhaiten pelaamalla poistaa tuon pitkän rimpsun ja Laura joutuu tyytymään siihen neljään. Ei tässä Ristolla mitään kiveen hakattua taktiikkaa ilmeisesti olekaan, vaan tilanteen mukaan....annetaan tämän nyt olla
Joo, mutta ratkaisu tälle tehtävälle olisi kiva saada. Siinähän pitäisi konstruoida strategia Ristolle, joka takaisi, että Laura ei saa ikinä yli n-1 millekään lautaselle. (Optimaalinen strategiahan olisi silloin ainakin näin hyvä.) Itse yritin miettiä jotain "tunnuslukua", jota Risto pyrkisi kontrolloimaan ja josta voitaisiin sitten päätellä, että millään lautasella ei ole yli n-1 rusinaa. Yritin rusinakeskiarvoa, mutta en oikein saanut sitä toimimaan.
- supermate
Esitän hypoteesini: Oletetaan, että Risto käyttää strategiaa, jossa hän valitsee siten, että lautasilla on vuoron jälkeen yhteensä mahdollisimman vähän rusinoita, ja jos vuoron jälkeinen rusinoiden yhteismäärä on sama riippumatta kumman puolen Risto valitsee poistettavaksi, hän valitsee sen, jolla on suuremman rusinamäärän omaava lautanen (tai enemmän tällaisia, tai jos sama määrä, niin sitten hän päättää seuraavaksi enimmistä jne.).
Siis hypoteesini on, että tällöin lautasille ei tule ikinä yhteensäkään yli n-1 rusinaa. Eipä tule siis millekään yhdellekään lautaselle.
Testasin tätä tietokoneohjelmalla, jossa laitoin Lauran arpomaan jakonsa satunnaisesti. Testasin kuitenkin niin monta kierrosta, että jako olisi joskus Lauran kannaltakin hyvä ja tämä hypoteesi tulisi hyvin testatuksi. Aina siinä kävi niin nätisti, että suurimmaksi rusinamääräksi, joka lautasilla ikinä yhteensä oli tuli korkeintaan n-1. Ja usein kun laitoin oikein monta kierrosta, tuli juuri tuo n-1 maksimimääräksi. Olen siis tähän hypoteesiin melko luottavainen.
En vain keksi miten tämän voisi todistaa. - enolevarmatästä
Voiko tämän ratkaista jotenkin ahneella algoritmilla?
Onkoon S rusinoiden lukumäärä. Alussa S=0. Kullakin kierroksella toisella puolella on enintään n rusinaa. Nyt Laura voi laittaa ne miten haluaa. Oletetaan, että meillä on x rusinaa pöydän toisella puolella ja y toisella, jolloin x y - 8+4
Ristohan ei joudu koko pelin aikana laittamaan lautasille kuin korkeintaan tasan n/2 rusinaa.
Jos Laura alussa jakoi lautaset tasan kahtia, niin Risto kun sen toisen puolen täyttää, niin hänen ei pelin aikana enää tarvitse rasiasta kaivaa lisää. Laura ei voi voittaa muuta kuin just sen puolikkaan ja maksimivoitto tulee kahdella lautasella 1 rusina ja n-1.
Jakaa Laura lautaset miten vaan, niin näin se menee.- 8+4
Joo ei mene.
Risto joutuu maksimissaan laittamaan peliin tavaraa geometrisen sarjan summan:
n/2 n/4 n/8.... näitä on ln(n)/ln(2) kappaletta , ja suhdeluku q=½
summa on n(1-½^(ln(n)/ln(2))), jos tuohon nyt sijoittaa vaikka n=16, niin summaksi tulee 15. Siis korkeintaan 15 Lauralla on mahdollisuus 16:sta voittaa.
Tästä se osoitus varmaan irtoaa, nyt ei vaan ehdi - 8+4
8+4 kirjoitti:
Joo ei mene.
Risto joutuu maksimissaan laittamaan peliin tavaraa geometrisen sarjan summan:
n/2 n/4 n/8.... näitä on ln(n)/ln(2) kappaletta , ja suhdeluku q=½
summa on n(1-½^(ln(n)/ln(2))), jos tuohon nyt sijoittaa vaikka n=16, niin summaksi tulee 15. Siis korkeintaan 15 Lauralla on mahdollisuus 16:sta voittaa.
Tästä se osoitus varmaan irtoaa, nyt ei vaan ehdiMolemmat kun pelaa parhaalla mahdollisella tavalla, niin Laura jakaa kahtia sitä lautasmäärää ja Risto vaan poistaa ja kaivaa kuvetta.
Oletetaan nyt yksinkertaisuuden vuoksi, että lautasmäärä n on joku kakkosen iso potenssi, vaikka voi se olla mikä hyvänsä >1.
Risto joutuu Lauran kahtia jakamisten vuoksi laittamaan maksimissaan peliin geometrisen sarjan summan mukaisen määrän , ja sen verran Laura voi siis korkeintaan voittaa. Se geometrinen sarja on: n/2 n/4 n/8 ... n/n
Kun Risto on alkuvaiheissa peliin tuon verran sijoittanut, niin loppupelin hän parhaalla tavalla pelatessaan, tällä klaaraa.
Jäsenten lukumäärä m saadaan: 2^m=n=> m=ln(n)/ln(2). Sarjan q=½, ja a=n/2
Summa on : n/2*(1-(½)^(ln(n)/ln(2)))/(1-½), ja tämä on sievennyksen jälkeen
n(1-1/n)= (n-1). Laura voi siis maksimissaan voittaa (n-1) rusinaa.
- mallivastaaja
Täällä mallivastaus: http://solmu.math.helsinki.fi/olympia/MAOL/2014/alkukratk2014.pdf . Viimeinen sivu, tehtävä A4.
- 8+4
Kukahan tostakin mallia ottaa , mulla on ainakin sata kertaa parempi vastaus
- mallivastaaja
8+4 kirjoitti:
Kukahan tostakin mallia ottaa , mulla on ainakin sata kertaa parempi vastaus
Mutta jotta vastaus olisi täydellinen, pitäisi tarkastella tapaukset, missä Laura ei pelaa optimistrategialla ja n ei ole kakkosen potenssi.
- 8+4
mallivastaaja kirjoitti:
Mutta jotta vastaus olisi täydellinen, pitäisi tarkastella tapaukset, missä Laura ei pelaa optimistrategialla ja n ei ole kakkosen potenssi.
Hetkinen, tehtävässä pyydetään osoittamaan paljonko Laura korkeintaan voi voittaa.
Lauran maksimivoitto tulee nimenomaan silloin kun hän pelaa parhaalla mahdollisella taktiikalla, ja lautasia on kappalemäärä, joka on kakkosen potenssi. - 8+4
8+4 kirjoitti:
Hetkinen, tehtävässä pyydetään osoittamaan paljonko Laura korkeintaan voi voittaa.
Lauran maksimivoitto tulee nimenomaan silloin kun hän pelaa parhaalla mahdollisella taktiikalla, ja lautasia on kappalemäärä, joka on kakkosen potenssi.niin ja tuo kyllä pätee millä tahansa n arvolla, niin kuin tuossa sanoinkin
- mallivastaaja
8+4 kirjoitti:
Hetkinen, tehtävässä pyydetään osoittamaan paljonko Laura korkeintaan voi voittaa.
Lauran maksimivoitto tulee nimenomaan silloin kun hän pelaa parhaalla mahdollisella taktiikalla, ja lautasia on kappalemäärä, joka on kakkosen potenssi.Ensimmäiseksi pitää osata lukea kysymys. Siinä lukee selvästi, että pöydällä on n lautasta ja n on vähintään kaksi. Mitään oletusta siitä, että n on kakkosen potenssi ei ole.
- 8+4
mallivastaaja kirjoitti:
Ensimmäiseksi pitää osata lukea kysymys. Siinä lukee selvästi, että pöydällä on n lautasta ja n on vähintään kaksi. Mitään oletusta siitä, että n on kakkosen potenssi ei ole.
Tuostahan näkee välittömästi, että Lauran maksimivoitto täytyy esiintyä lautasmäärällä joka on kakkosen potenssi, koska aina kakkosen potenssi lautasmäärissä Risto joutuu laittamaan peliin yhden rusinan enemmän, kuin mitä olisi laittanut lautasmäärällä , joka on yksi vähemmän kuin se kakkosen potenssi.
Jos se Lauran maksimivoitto ei kakkosen potenssi lautasmäärälläkään ole suurempi kuin (n-1), niin ei se ole millään muullakaan lautasmäärällä. Riittää kun tutkii kakkosen potenssi lautasmäärät. - kyllästetty
8+4 kirjoitti:
Tuostahan näkee välittömästi, että Lauran maksimivoitto täytyy esiintyä lautasmäärällä joka on kakkosen potenssi, koska aina kakkosen potenssi lautasmäärissä Risto joutuu laittamaan peliin yhden rusinan enemmän, kuin mitä olisi laittanut lautasmäärällä , joka on yksi vähemmän kuin se kakkosen potenssi.
Jos se Lauran maksimivoitto ei kakkosen potenssi lautasmäärälläkään ole suurempi kuin (n-1), niin ei se ole millään muullakaan lautasmäärällä. Riittää kun tutkii kakkosen potenssi lautasmäärät.Lopeta nyt se höpöttäminen niistä kakkosen potensseista. Toi perustelukin on järjetön. Jos sarjan summajutska kerran pätee kaikilla n-määrillä, niin se on sitten siinä.
- mallivastaaja
8+4 kirjoitti:
Tuostahan näkee välittömästi, että Lauran maksimivoitto täytyy esiintyä lautasmäärällä joka on kakkosen potenssi, koska aina kakkosen potenssi lautasmäärissä Risto joutuu laittamaan peliin yhden rusinan enemmän, kuin mitä olisi laittanut lautasmäärällä , joka on yksi vähemmän kuin se kakkosen potenssi.
Jos se Lauran maksimivoitto ei kakkosen potenssi lautasmäärälläkään ole suurempi kuin (n-1), niin ei se ole millään muullakaan lautasmäärällä. Riittää kun tutkii kakkosen potenssi lautasmäärät.Olet ymmärtänyt tehtävän väärin. Kokeile aluksi ratkaista tehtävä kolmen lautasen tapauksessa.
- 8+4
mallivastaaja kirjoitti:
Olet ymmärtänyt tehtävän väärin. Kokeile aluksi ratkaista tehtävä kolmen lautasen tapauksessa.
Koetetaan, mutta koetetaan ensin pelata tätä peliä kahdella lautasella.
No niin. Kahdella lautasella Laura voittaa yhden rusinan, joka on 2-1, eli n-1.
Risto laittoi yhden, jonka Laura heti söi pois.
Teoreettinen maksimivoitto, eli kaikki Riston peliin laittamat rusinat toteutui heti.
Kolmella Laura voittaa yhden rusinan, joka on n-2
Neljällä voittaa 2 rusinaa, joka on n-2
Viidellä voittaa 2 rusinaa, joka on n-3
Kuudella voittaa 3 rusinaa, joka on n-3
Seitsemällä voittaa 3 rusinaa, joka on n-3
Kahdeksalla voittaa 4 rusinaa, joka on n-4
...
Teoreettinen maksimivoitto (n-1), ei tämän jälkeen enää ilmeisesti toteudu, vaan näyttäisi siltä, että käytännön pelissä Lauran teoreettinen maksimivoitto, eli kaikki Riston peliin laittamat rusinat toteutuu vain lautasmäärällä n=2, ja muilla lautasmäärillä käytännön maksimivoitto näyttäisi olevan n/2, mutta ei se ainakaan enempää ole kuin kahden lautasen voitto (n-1)
Käsittääkseni tässä ei kuitenkaan tarvitse pelata tuota käytännön peliä muuta kuin sen kahden lautasen tapaus, koska siinä se maksimivoitto n-1 heti tuli
- näinkai
Oletetaan, että Risto on juuri siirtänyt lautaset ja on Riston vuoro. Olkoon p rusinoiden yhteismäärä kaikilla n lautasella. Oletetaan, että p
- 8+4
Siinä on Ristot ja Laurat niin sekaisin ettei siitä saa mitään tolkkua.
- näinkai
8+4 kirjoitti:
Siinä on Ristot ja Laurat niin sekaisin ettei siitä saa mitään tolkkua.
Totta. Ensimmäinen Risto pitäisi olla Laura, eli Laura on juuri lopettanut vuoronsa. Onko muita virheitä? Mikä on se kohta, josta et saanut enää selvää?
- 8+4
näinkai kirjoitti:
Totta. Ensimmäinen Risto pitäisi olla Laura, eli Laura on juuri lopettanut vuoronsa. Onko muita virheitä? Mikä on se kohta, josta et saanut enää selvää?
Ihan niin kuin sulla Laura lisäisi rusinoita ja tyhjentelisi lautasia, minä olen käsittänyt, että se olisi Riston hommia, ja Laura vaan siirtelisi niitä.
Voi kyllä olla, että minä tosiaan olen ymmärtänyt tämän pelin totaalisesti väärin. - näinkai
8+4 kirjoitti:
Ihan niin kuin sulla Laura lisäisi rusinoita ja tyhjentelisi lautasia, minä olen käsittänyt, että se olisi Riston hommia, ja Laura vaan siirtelisi niitä.
Voi kyllä olla, että minä tosiaan olen ymmärtänyt tämän pelin totaalisesti väärin.Äh. Mä mokasin. Olet oikeassa.
- näinkai
Tässä korjattu vastaus, onko oikein?
Oletetaan, että Laura on juuri siirtänyt lautaset ja on Riston vuoro. Olkoon p rusinoiden yhteismäärä
kaikilla n lautasella. Oletetaan, että p - 8+4
näinkai kirjoitti:
Tässä korjattu vastaus, onko oikein?
Oletetaan, että Laura on juuri siirtänyt lautaset ja on Riston vuoro. Olkoon p rusinoiden yhteismäärä
kaikilla n lautasella. Oletetaan, että pEn osaa sanoa, rupee vaan "rusinaa" särkeen, tämä on mennyt minun osaltani jo tappiinsa tämä tehtävä
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
- 676679
Tappo Kokkolassa
Päivitetty tänään Iltalehti 17.04.2024 Klo: 15:23..Mikähän tämä tapaus nyt sitten taas on.? Henkirikos Kokkolassa on tap284320Miksi tytöt feikkavat saaneensa orgasmin, vaikka eivät ole saaneet?
Eräs ideologia itsepintaisesti väittää, että miehet haluavat työntää kikkelinsä vaikka oksanreikään, mutta tämä väite ei2712740Poliisit vaikenee ja paikallinen lehti
Poliisit vaikenee ja paikallinen lehti ei kerro taposta taaskaan mitään. Mitä hyötyä on koko paikallislehdestä kun ei262070MAKEN REMPAT
Tietääkö kukaan missä tämmöisen firman pyörittäjä majailee? Jäi pojalla hommat pahasti kesken ja rahat muisti ottaa enna311613- 971427
Kuntoutus osasto Ähtärin tk vuode osasto suljetaan
5 viikkoa ja mihin työntekijät, mihin potilaat. Mikon sairaalan lopetukset saivat nyt jatkoa. Alavudelle Liisalle tulee551131Itämaisesta filosofiasta kiinnostuneille
Itämaisesta filosofiasta kiinnostuneille. Nämä linkit voivat auttaa pääsemään niin sanotusti alkuun. https://keskustel3041117Välillä käy mielessä
olisiko sittenkin ollut parempi, että emme koskaan olisi edes tavanneet. Olisi säästynyt monilta kyyneleiltä.781104Mulla on kyllä
Järkyttävä ikävä sua. Enkä yhtään tykkää tästä olotilastani. Levoton olo. Ja vähän pelottaa..391061