pikku harjoitustehtäviä näyttäisi löytyvän lukion matematiikkaan perehtyneille osoitteesta
http://bw09.no/problems/english.pdf
Osa näistä näyttäisi tarjoavan kammettavaa jopa minun kaltaiselleni vanhalle kalkkikselle/fossiilille. Aktiivisesti toimiville lukion opettajille tehtävät lienevät selvää pässinlihaa.
http://bw09.no/problems/english.pdf
Osa näistä näyttäisi tarjoavan kammettavaa jopa minun kaltaiselleni vanhalle kalkkikselle/fossiilille. Aktiivisesti toimiville lukion opettajille tehtävät lienevät selvää pässinlihaa.
Vastaukset 57
Vanhimmat
Ei nuo nyt kamalilta vaikuta. Aloitin aamuyöstä kaljapöhnässä loppupäästä, kuten lehden luvun sarjakuvista. Menisikö tuo Problem 20 simppelisti seuraavasti?
Sairaalapareja on a = (16C2) = 120. Päivystykset voidaan järjestää b =(16C4) = 1820 tavalla. b/a = 15.7 < 20, joten ei onnistu.
C on tuossa "yli".
Englantia en ymmärrä, joten olen voinut käsittää
asian väärin, mutta yritetään.
Neljästä "päivystäjästä" saadaan 6 paria, joten
20 * 6 = 120. Lasku siis näyttää menevän tasan.
Koska on olemassa 20-sanainen 4-painoinen koodi,
joka peittää täsmälleen yhteen kertaan kaikki
2-painoiset 16-mittaiset binäärisanat, pitäisi
päivystysten jakaminen "tasan" onnistua".
On 16 sairaalaa, joista 4 päivystää jokaisena yönä. Voidaanko päivystykset järjestää siten, että 20 yön jälkeen jokainen sairaalapari on päivystänyt täsmälleen kerran?
Minusta avainsana on tuo "sairaalapari".
Alla on binäärikoodilla yritetty kuvata miten
onnistuu 16 sairaalan 20 yön päivystys "tasan",
jos joka yö pitää valmiudessa olla 4 sairaalaa.
Kommenttina "Sven Tuuvalle":
Eihän tässä 1820 kombinaatiota tarvita.
Ajankuluksi kannattaa tarkistaa, että jokainen
"sairaalapari" löytyy täsmälleen yhden kerran.
Pari esimerkkiä "kaavan" ymmärtämiseksi:
1. yönä päivystävät sairaalat:
1, 2, 3 ja 4.
20. yönä päivystävät sairaalat:
4, 7, 9 ja 14.
Sairaalat:
0000000001111111
1234567890123456
1111000000000000 1. yö
0000111100000000 2. yö
0000000011110000 3. yö
0000000000001111 4. yö
1000100010001000 5. yö
0100010001000100 6. yö
0010001000100010 7. yö
0001000100010001 8. yö
1000000100100100 9. yö
0100001000011000 10. yö
0010010010000001 11. yö
0001100001000010 12. yö
1000001001000001 13. yö
0100000110000010 14. yö
0010100000010100 15. yö
0001010000101000 16. yö
1000010000010010 17. yö
0100100000100001 18. yö
0010000101001000 19. yö
0001001010000100 20. yö
Itsekin ajattelin, että tämä tehtävä ratkeaisi tietokoneella yksinkertaisella "kokeile ja palaa"-algoritmilla asettamalla nuo kaksi ensimmäistä kierrosta (8 yötä) esittämäsi ratkaisun mukaisesti.
Mutta voisikohan tämän tehtävän ratkaista jollakin tavalla näppärästi ilman tietokonetta?
Ovatko matikkakilpailun osallistujajoukkueilla olleet käytettävissään tietokoneet?
Samalta verkkosivulta lötyi myös säännöt (Regualtions). Niissä seisoo:
Only writing and drawing materials are allowed during the contest; in particular calculators and computers are not allowed.
Öitä siis 20, joka yö 4 sairaala eli 6 paria, yhteensä 120 paria.
Jokainen sairaala päivystää 5 kertaa, joka kerta kolmen eri sairaalan kanssa.
Tehdään sairaaloista 4x4 matriisi:
A1 A2 A3 A4
B1 B2 B3 B4
C1 C2 C3 C4
D1 D2 D3 D4
Käydään matriisi läpi 5 kertaa (jokainen sairaalahan päivysti 5 kertaa), siten, että jokainen sairaala päivystää kerran joka kierroksella. Valitaan nuo 5 läpikäyntiä siten, että kombinaatiot on aina erit.
Kierros 1, päivät 1-4, vaakarivit:
1. A1 A2 A3 A4
2. B1 B2 B3 B4
3. C1 C2 C3 C4
4. D1 D2 D3 D4
Kierros 2, päivät 5-8, pystyrivit:
5. A1 B1 C1 D1
6. A2 B2 C2 D2
7. A3 B3 C3 D3
8. A4 B4 C4 D4
Kierros 3, päivät 9-12, vinorivit oikealle:
9. A1 B2 C3 D4
10. A2 B3 C4 D1
11. A3 B4 C1 D2
12. A4 B1 C2 D3
Kierros 4, päivät 13-16, vinorivit vasemmalle:
13. A1 B4 C3 D2
14. A2 B1 C4 D3
15. A3 B2 C1 D4
16. A4 B3 C2 D1
Kierros 5, päivät 17-20, 'väliinjääneet', eli valitaan matriisin joka riviltä ne, jotka eivät aiemmissa kombinaatioissa olleet mukana:
17. A1 B3 C2 D3
18. A2 B4 C3 D4
19. A3 B1 C4 D1
20. A4 B2 C1 D2
No hemmetti, eihän se toimikaan noin, vinoriveistä tulee samoja kombinaaiotita. Siis uusi yritys korjatulla logiikalla:
Kierros 1, päivät 1-4, vaakarivit:
1. A1 A2 A3 A4
2. B1 B2 B3 B4
3. C1 C2 C3 C4
4. D1 D2 D3 D4
Kierros 2, päivät 5-8, pystyrivit:
5. A1 B1 C1 D1
6. A2 B2 C2 D2
7. A3 B3 C3 D3
8. A4 B4 C4 D4
Kierros 3, päivät 9-12, 'parit ristiin':
9. A1 B2 C3 D4
10. A2 B1 C4 D3
11. A3 B4 C1 D2
12. A4 B3 C2 D1
Kierros 4, päivät 13-16, 'parit lomittain':
13. A1 B3 C4 D2
14. A3 B1 C2 D4
15. A2 B4 C3 D1
16. A4 B2 C1 D3
Kierros 5, päivät 17-20, 'reunat ja keskimmäiset':
17. A1 B4 C2 D3
18. A4 B1 C3 D2
19. A2 B3 C1 D4
20. A3 B2 C4 D1
Kun sairaalat on 4x4 matriisissa ja vaaka- ja pystyrivit on käsitelty (8 ensimmäistä tapausta), ollaan tilanteessa, missä neljältä riviltä pitää valita aina yksi kultakin riviltä eri sarakkeista niin, että tuplia ei tule.
Kysymys siis supistuu kysymykseksi:
Kuinka monella tavalla luvut 1-4 voidaan järjestää siten, että samat kaksi lukua ei esiinny samoilla paikoilla kuin kerran?
On helppo kokeilla, että niitä on 12:
1,2,3,4
1,3,4,2
1,4,2,3
2,1,4,3
2,4,3,1
2,3,1,4
3,1,2,4
3,2,4,1
3,1,2,4
4,1,3,2
4,3,2,1
4,2,1,3
Noista saakin ne loput kombinaatiot, kun ensimmäinen luku vastaa riviä A, toinen B jne. Eli tuosta vaikkapa 2,4,3,1 tarkoittaa sairaaloita A2, B4, C3, D1. (Järjestys yllä on eri kuin äsköisessä vastauksessani, jonka päättelin vähän eri järjestyksessä).
Mutta osaako joku näppärästi osoittaa (muutenkin kuin kokeilemalla), että kombinaatioita on 12?
Tietokonetta en ollut nähnytkään kun jo tunsin
kyseisen koodin, lienee ikivanha Steinersysteemi.
Minusta tuntuu, ettei tähän tuon matemaattisempaa
ratkaisua löydy.
Eli miten voidaan todistaa jonkun konstruktion
"olemassaolo" muuten kuin laatimalla kyseinen
systeemi?
Kaikenkaikkiaan tehtävän ratkaiseiden on täytynyt
tuntea kyseinen koodi, tai ainakin pystyneen sen
konstruoimiseen kynällä ja paperilla.
((16*15/2))/((4*3/2)) on kaksikymmentä
Tämä jakolaskun tasan meneminen ei todista sitä,
että kyseinen koodi voidaan laatia.
Saattaa olla, että 2-painoisten peittämisen onnistuminen
"täsmälleen yhteen kertaan" 4-painoisilla on todistettukin
jossain, mutta pitäisi esittää kyseinen todistus, ellei halua
koodia esittää.
mitä kysyttiin, mutta tässä on koko lista:
2 kerrallaan 120 yötä
4 kerrallaan 20 yötä
6---------------8
8---------------4,2
10-------------2,6
12-------------1,8
14-------------1,3
16-------------1
ei kai tässä muuta todistelua , eikä varsinkaan koodia tarvita
Toistan, ettei tiettyjen jakolaskujen meneminen
tasan todista jonkun koodin olemassaoloa.
Alla esimerkki, jossa laskut menevät tasan,
mutta ei ole mahdollista laatia 4-painoista
11-sanaista koodia, joka peittää 2-painoiset
sanat täsmälleen yhteen kertaan.
((12*11/2))/((4*3/2)) = 11
Ps. Seuraavaksi ehdotan tarkastelun kohteeksi
kyseisen tehtäväluettelon numeroa 19.
Muut saattavat mennä yli minun kykyjeni.
Hauska taulukko, toivottavasti myös tarkoitettu hauskaksi.
Problem 20:
In the battlezone are 16 soldiers. Every night exactly four of them must be on duty
for guarding. Is it possible to arrange schedule in such away that after twenty nigths
every pair of soldiers have been common duty exactly once?
16 yksikköä, merkitään kukin kirjaimella a,b,c,.. jne.; saadaan 120 paria, joissa
kukin yksikkö esiintyy 15 kertaa.
Ja kysymys kuului; Onko mahdollista järjestää vuorolista siten, että kahdenkymmenen yön
jälkeen jokainen sotilaspari on ollut vartiossa vain kerran.
No tietenkin ON MAHDOLLISTA, mutta yksittäinen yksikkö saattaa urputtaa ylimääräisistä
vuoroista ja homppeleista palvelustovereista sekä vaatia kompensaatiota yhtymän
päivystysjärjestelyistä.
:DDDD
sain kompuutterini sylkemään seuraavat ratkaisut:
Ratkaisu no: 1
1111000000000000
0000111100000000
0000000011110000
0000000000001111
1000100010001000
0100010001000100
0010001000100010
0001000100010001
0001001001001000
0100000100101000
0010010000011000
0010000110000100
0001100000100100
1000001000010100
0001010010000010
1000000101000010
0100100000010010
0100001010000001
0010100001000001
1000010000100001
Ratkaisu no: 2
1111000000000000
0000111100000000
0000000011110000
0000000000001111
1000100010001000
0100010001000100
0010001000100010
0001000100010001
0010000101001000
0001010000101000
0100001000011000
0001001010000100
1000000100100100
0010100000010100
0100000110000010
0001100001000010
1000010000010010
0010010010000001
1000001001000001
0100100000100001
Näissä ratkaisuissa kahdeksan ensimmäistä riviä on asetettu etukäteen (hiukan päättelemällä). Loput 12 riviä ovat niden binäärilukuarvojen mukaisessa järjestyksessä (vähiten merkitsevä bitti vasemmalla).
Mutta kuten muualla ketjussa on todettu, tehtävä pitäisi ratkaista ilman tietokonetta.
Ilmeisesti homma onnistuu jollain näppärällä konstruktiolla?
Tällaisen idean kuulin:
Olkoon Q neljän alkion kunta. Liitetään kuhunkin 16 sairaalaan 16 pistettä (x,y), missä x ja y ovat Q:n alkioita. Nyt 4x4-ruudukko sisältää 20 suoraa muotoa ax by=c. Kulmakertoimella voi olla neljä eri vaihtoehtoa tai suora voi olla pystysuora. Kukin pistepari kuuluu täsmälleen yhteen suoraan.
mutta ratkaisu edellyttää perehtyneisyyttä äärellisten kuntien teoriaan.
Tätä ei tietääkseni ainakaan Suomessa toisen asteen oppilaitoksissa opeteta.
Toisaalta kilpailumatikkaa perehtyneet saattavat hyvinkin osata kuntateoriaa. Kunnan voi korvata ruudukolla, sillä ratkaisussa ei käytetä kuntin liittyvää teoriaa.
nimenomaan äärellisten kuntien teoriaa. Renkaan rakenne ei riitä.
Kokeilepas ratkaista tehtävä samalla tavalla vaikkapa renkaassa Z_4 ts. jäännösluokkarenkaassa modulo 4.
avulla tuota äärellisiin kuntiin perustuvaa ratkaisutapaa.
Tulokseksi sain seuraavat taulukot:
1. 0 1 2 3
2. 4 5 6 7
3. 8 9 10 11
4. 12 13 14 15
5. 0 4 8 12
6. 1 5 9 13
7. 2 6 10 14
8. 3 7 11 15
9. 0 5 10 15
10. 1 4 11 14
11. 2 7 8 13
12. 3 6 9 12
13. 0 6 11 13
14. 1 7 10 12
15. 2 4 9 15
16. 3 5 8 14
17. 0 7 9 14
18. 1 6 8 15
19. 2 5 11 12
20. 3 4 10 13
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
Ensimmäinen taulukko kertoo päivystysvuorot.
Toinen kertoo sen, että ratkaisu tosiaan toimii, ts. kukin sairaalapari päivystää yhdessä täsmälleen kerran.
osoitteesta
http://bw09.no/
(Valitse vasemmasta palkista Problems ja sitten kieli finnish)
Tehtävässä 20 on "every pair of hospitals" suomennettu "mitkä tahansa kaksi sairaalaa". Tällä käännöksellä voitaisiin valita yksi satunnainen sairaalapari, fiksata se päivystämään kerran, eikä lopuilla ole mitään väliä. Sven Tuuva käänsi ylempänä ketjussa aivan oikein: "jokainen sairaalapari". Vai mikä onkaan masterkieli tehtävissä, ja onko muissa käännöksissä mokia?
millaisia ratkaisuja olette löytäneet tehtävään 3.
Tämä tehtävä näyttää kilpailussa jääneen mm. Suomen joukkueelta ratkaisematta. Omasta mielestäni se ei kuitenkaan näytä mitenkään mahdottomalta. Siihen pitää vain hoksata oikea lähestymistapa. (Hox!)
Ehkä Suomen toisen asteen oppilaitoksissa ei aiheeseen liittyvää (periaatteessa varsin yksinkertaista)
teoriaa kuitenkaan mitenkään sivuta. Se lieneekin lähinnä oman harrastuksen varassa. Avainsana alkaa kirjaimella 'd' ja siinä on 19 kirjainta.
Itse löysin siihen pienellä tarkastelulla mielestäni varsin näppärän todistuksen, parannuksia ja yleistyksiäkin. (Aha!)
Eikö sitä voi vain käsitellä määrättynä integraalina, ja päädytään tuohon ?
0≤Ck(n³-1)/3≤4
se avainsana on 'differenssilaskenta'.
Jos on jotenkin hajulla differenssilaskennan ideoista, niin tässä tehtävässä pääsee helposti alkuun.
Eihän tässä varsinaisia diffrenssilaskennan merkintöjä tietenkään tarvitse osata, mutta lähtökohtana on samanlainen peräkkäisten lukujen erotusten laskeminen.
tai nimimerkki 'yksi/yski vain' voisi kertoa, miten tässä tehtävässä tulisi edetä?
Omasta lukiomatematiikasta on kolmattakymmenettä vuotta aikaa, eikä matematiikkaa ole juuri tullut sen jälkeen käytettyä muuta kuin harrastusmielessä. Huomaan, että monilla matematiikan alueilla olen aivan pihalla, mutta jonkin verran saan aina joskus pääteltyä. Kokeillaan siis:
Voimme valita kahdelle perättäiselle termille k-1 ja k eri etumerkit, jolloin summan itseisarvo niiden osalta on k^2-(k-1)^2 = 2k-1. Vastaavasti termien k ja k 1 summan itseisarvo, kun termeillä on eri etumerkit, on 2k 1.
Voimme siis kirjoittaa summan muotoon sum (j=1->n/2) {( /-1)(2(2j)-1)} kun termejä on parillinen määrä ja sum (j=0->(n-1)/2) {( /-1)(2(2j) 1)} kun termejä on pariton määrä.
Parilllisessa tapauksessa edellisen summan termien itseisarvot ovat {3,7,11,15...} ja parittomassa {1,5,9,13...}. Koska termien itseisarvot kasvavat aina neljällä, voidaan etumerkit aina valita siten, että summalle s pätee 0
No niin, nyt on mietitty loppuun:
{3,7,11,15...} ja {1,5,9,13...} 4 peräkkäisen termin summaksi saadaan aina 0, koska a-(a 4)-(a 8) (a 12)=0. Riittää siis, että tarkistetaan alle neljän termin mittaiset vaihtoehdot:
3, 7-3=4, 11-7-3=1 ja 1, 5-1=4, 9-5-1=3.
Nyt kun tämä tuli näin hankalalla tavalla mietittyä, esitän toisen ratkaisun, jota en olisi kyllä ikinä keksinyt suoraan. Ratkaisu seuraa suoraan tuosta ensimmäisestä ratkaisusta.
Alkuperäisessä summassa, minkä tahansa kahdeksan perättäisen termin summaksi saadaan sopivasti valituilla kertoimilla ( 1,-1,-1, 1,-1, 1, 1,-1, joko alhaalta ylös tai toisinpäin) nolla:
(k 7)^2-(k 6)^2-(k 5)^2 (k 4)^2-(k 3)^2 (k 2)^2 (k 1)^2-k^2 = (4-4)k^2 (14-12-10 8-6 4 2)k 49-36-25 16-9 4 1 = 0
Riittää siis, että löydetään ratkaisut 7 ensimmäiselle summalle, muut palautuvat niihin (tai nollaan):
49-36-25 16-9 4 1 = 0
36-25-16 9-4 1 = 1
25-16-9 4-1 = 3
16-9-4-1 = 2
9-4-1 = 4
4-1 = 3
1 = 1
tehtävään kolme meni seuraavasti.
Käsitellään konkreettisena esimerkkinä vaikkapa tapausta n=23.
Muodostetaan lopusta lukien aina kahden peräkkäisen neliön erotukset siten, että kukin neliö käytetään vain yhteen kertaan:
23^2-22^2=529-484=45
21^2-20^2=441-400=41
19^2-18^2=361-324=37
17^2-16^2=289-256=33
15^2-14^2=225-196=29
13^2-12^2=169-144=25
11^2-10^2=121-100=21
9^2-8^2=81-64=17
7^2-6^2=49-36=13
5^2-4^2=25-16=9
3^2-2^2=9-4=5
Toistetaan näille luvuille sama menettely kuin edellä
45-41=4
37-33=4
29-25=4
21-17=4
13-19=4
Valitaan näille nelosille vuorotellen ja - -etumerkit ja ynnätään muistaen, miten ne on muodostettu ja poistetaan etumerkit
4-4 4-4 4 = 4 = (45-41)-(37-33) (29-25)-(21-17) (13-9)
=((23^2-22^2)-(21^2-20^2))-((19^2-18^2)-(17^2-16^2)) ((15^2-14^2)-(13^2-12^2))-((11^2-10^2)-(9^2-8^2)) ((7^2-6^2)-(5^2-4^2))
=23^2-22^2-21^2 20^2-19^2 18^2 17^2-16^2 15^2-14^2-13^2 12^2-11^2 10^2 9^2-8^2 7^2-6^2-5^2 4^2
Käyttämättä ovat vielä neliöt 1^2, 2^2 ja 3^2
Näistä voidaan muodostaa 'korjaustermi' 3^2-2^2-1^2=4.
Valitaan tälle negatiivinen etumerkki.
Näin saadaan esitys
23^2-22^2-21^2 20^2-19^2 18^2 17^2-16^2 15^2-14^2-13^2 12^2-11^2 10^2 9^2-8^2 7^2-6^2-5^2 4^2-( 3^2-2^2-1^2)
=23^2-22^2-21^2 20^2-19^2 18^2 17^2-16^2 15^2-14^2-13^2 12^2-11^2 10^2 9^2-8^2 7^2-6^2-5^2 4^2-3^2 2^2 1^2=4-4=0
Näin voidaan aina menetellä, sillä
1) neljästä peräkkäisestä kokonaisluvun neliöstä saadaan eo. tavalla sopivalla etumerkkien muodostettua luku neljä
(k 3)^2-(k 2)^2-(k 1)^2 k^2=k^2 6k 9-k^2-4k-4-k^2-2k-1 k^2=4
2) Muodostamalla tällaisia nelosia lopusta lukien ja laskemalla ne positiivista ja negatiivista etumerkkiä vuorotellen yhteen päädytään joko lukuun 0 tai lukuun 4
3) Jäljelle jää 0-3 pienintä neliötä, joista voidaan aina muodostaa välillä [0,4] oleva korjaustermi, joka joko lisätään summaan tai vähennetään siitä
2^2-1^2=3
3^2-2^2-1^2=4
Näin lopullinen summa saadaan pysymään välillä [0,4], joten väite on todistettu.
Huom 1:
Tulosta voidaan vielä parantaa siten, että luvun 4 tilalle tulee ylärajaksi luku 1 kun n on suurempi tai yhtäsuuri kuin 6. Tämä on paras mahdollinen tulos, sillä summa nolla saavutetaan silloin ja vain silloin kun lukua n pienempien tai yhtä suurien positiivisten kokonaislukujen määrä on parillinen ja summa 1 muulloin. Summaan 0 päästään silloin kun n = 0 tai 3 (mod 4) ja summaan 1 muulloin.
Tämän todistaminen on vain hieman vaikeampaa kuin edellä esitetty.
Huom 2:
Vastaavat tulokset voidaan esittää myös kokonaislukujen korkeammille potensseille, kolmannelle, neljännelle jne. Silloin summan yläraja käy aluksi hiukan suuremmissa luvuissa mutta näyttäisi (pienten tietokonetestien perusteella) asettuvan pian parhaaseen mahdolliseen ts. lukuun 1.
Heikkioskari tuolla ylempänä ehdotti seuraavaksi tehtävää 19:
Tehtävä 19. Kahdeksan hengen juhlissa jokainen ihmispari joko tuntee tai ei tunne toisiaan.
Jokainen ihminen tuntee täsmälleen kolme muuta. Voivatko seuraavat ehdot toteutua yhtä aikaa:
- missä tahansa kolmen hengen joukossa on ainakin kaksi, jotka eivät tunne toisiaan;
- missä tahansa neljän hengen joukossa on ainakin kaksi, jotka tuntevat toisensa.
Tämä vaikuttaa minusta helpolta. Ratkaisuni:
Ensimmäinen ehdoista sulkee pois vaihtoehdot, joissa kolme ihmistä tuntisivat kaikki toisensa. Kaksi ihmistä, jotka sama ihminen tuntee, eivät siis voi tuntea toisiaan.
Toinen ehdoista taas sulkee pois vaihtoehdot, joissa meillä olisi kaksi neljän ihmisen ryhmää, joiden kaikki ihmiset tuntisivat kolme ihmistä toisesta ryhmästä (eivätkä ketään omastaan). Tällainen ratkaisuhan olisi muutoin helppo löytää niin, että muut ehdot täyttyvät, näin:
Ryhmä 1: A, B, C, D
Ryhmä 2: E, F, G, H
A tuntee F:n, G:n, H:n
B tuntee E:n, G:n, H:n
C tuntee E:n, F:n, H:n
D tuntee E:n, F:n, G:n
Mutta ehdon 2 mukaan tämä siis ei käy.
Tehtävän ratkaisemiseksi tehdään siis osallistujista rengas: A, B, C, D, E, F, G, H.
Vierekkäiset ihmiset tuntevat toisensa (A tuntee H:n ja B:n, B tuntee A:n ja C:n jne.). Jokainen tuntee tässä vaiheessa siis kaksi ihmistä, eivätkä ketkään kolme tunne kaikki toisiaan (ehto 1). Toisen ehdon vaatimus sen sijaan ei vielä täyty: valitsemalla joka toisen saisi aikaiseksi neljän ryhmän, jossa kukaan ei tunne toistaan. Koska vierekkäiset ihmiset tuntevat aina toisensa, tämä on ainoa tapa valita neljä niin, että ketkään kaksi eivät tunne toisiaan.
Nyt sijoitetaan ne kolmannet kontaktit siten, että nuo 'joka toinen' ryhmät saadaan hajotettua. Koska kahden askeleen päähän (esim. A-C) ei saa luoda kontaktia (ehto 1 ei enää täyttyisi), luodaan se neljän askeleen päähän, renkaan läpi (A-E, B-F, C-G, D-H).
Ensimmäinen ehto täyttyy edelleen: A tuntee B:n, E:n ja H:n, eikä kukaan näistä tunne toisiaan, ja muiden ihmisten tilanne on täysin symmetrinen näiden kanssa.
Toinenkin ehto täyttyy: Koska vierekkäiset ihmiset tuntevat toisensa, pitäisi valita aina joka toinen ihminen, ettei kukaan tunne toistaan, mutta tällöin renkaan vastakkaiset, jotka tuntevat toisensa, päätyisivät samaan ryhmään.
Ehdot siis voivat toteutua yhtä aikaa.
piirtämällä paperille yksinkertaisen kuvion.
Valitaan ryhmästä joku mielivaltainen henkilö. Olkoon tämä henkilö nyt sitten vaikka A.
Piirretään graafi, jonka yläreunaan (yläriville) tulee solmupiste A.
Henkilö A tuntee täsmälleen kolme muuta. Olkoot nämä B, C ja D.
Piirretään kuvaan toiselle riville henkilöitä B, C ja D kuvaavat solmupisteet ja yhdistetään ne viivoilla pisteeseen A (tuntevat A:n ja päinvastoin).
Henkilöistä B, C ja D kukaan ei tunne toisiaan, mutta he tuntevat A:n lisäksi täsmälleen kaksi muuta henkilöä. Näitä henkilöitä täytyy olla vähintään kolme.
Valitaan kolme henkilöä. Merkitään näitä E, F ja G. Piirretään näitä kuvaavat solmupisteet graafin kolmannelle riville. Piirretään tuttavuutta kuvaavat jänteet graafiin vaikkapa siten, että
B tuntee E:n ja F:n,
C tuntee F:n ja G:n ja
D tuntee G:n ja E:n.
Nyt jokainen henkilöistä E, F ja G tuntee kaksi henkilöä joukosta A, B ja C. Jokaiselle heistä tarvitaan siis vielä ainakin yksi henkilö, jonka he tuntevat. Helposti todetaan, että tämä ei voi olla kukaan jo luetelluista.
Valitaan henkilö H ja piirretään graafin neljännelle riville tätä kuvaava solmupiste. Piirretään graafiin tuttavuutta kuvaavat jänteet solmupisteistä E, F ja G tähän solmupisteeseen.
Tässä vaiheessa todetaankin graafin olevan valmis. Siinä on tarkalleen kahdeksan solmupistettä eli henkilö. Jokainen tuntee täsmälleen kolme muuta. Yhdetäkään kolmen henkilön joukosta kaikki eivät tunne toisiaan ts. siinä ei esiinny 'kolmioita'.
Ratkaisun hahmotteleminen paperille kaikkine pähkäilyineen vei minulta ehkä pari kolme minuuttia. Tällaisen sanallisen kuvauksen kirjoittaminen kesti paljon pitempään. Vahinko, ettei näille keskustelupalstoille voi liittää kuvia sellaisinaan. Sama koskee valitettavasti myös matemaattisia kaavoja.
Tehtävän toinen ehto (missä tahansa neljän hengen joukossa on ainakin kaksi, jotka tuntevat toisensa) ei täyty ratkaisussasi:
Ryhmästä A, E, F, G kukaan ei tunne toistaan, kuten ei myöskään ryhmästä B, C, D, H.
(Vastauksesi on täysin analoginen ehdon 2 yhteydessä esittämäni virheellisen ratkaisun kanssa, vain vaihdetuilla kirjaimilla.)
Piirtämällä minäkin tämän muuten ratkaisin.
se turha kiire teettää.
Mutta yritetäänpä pikaista (=kiireellistä) korjausta.
Laitetaankin kolmannelle riville kaksi henkilöä, E ja F. E:n tuntevat C ja D ja F:n B ja C.
Neljännelle voidaan sitten sijoittaa G ja H, jotka tuntevat toisensa. E tuntee G:n ja F tuntee H:n. Lisäksi G tuntee B:n ja H tuntee D:n.
OK?
Näyttäisi toimivan. Lisäksi ratkaisusi on eri kuin minun. :)
Mahtaakohan tähän olla vielä muunkinlaisia ratkaisuja?
Eipäs olekaan erilainen, vaan sama kuin minulla, kun tarkemmin katsoo. Lienee ainoa ratkaisu?
Tehtävä vaatii todistusta siitä että Ramsey-luku R(3,4) > 8. Itse asiassa R(3,4) = 9.
Luvulla R(m,n) tarkoitetaan minimilukua R, jolle pätee että mikä tahansa R solmua sisältävä graafi sisältää joko m solmua joista kaikkien parien välillä on kaari tai n solmua joiden kesken ei löydy yhtäkään kaarta.
Otetaan 8 solmun syklinen graafi ja yhdistetään eka ja neljäs solmu kaarella. Tämä esimerkki todistaa että R(3,4) > 8.
On helppo todistaa että R(3,3) = 6. Kuusisolmuisen graafin kullakin solmulla on joko 3 naapuria tai 3 ei-naapuria. Ensimmäisessä tapauksessa voimme välttää kolmion vain jos kolmen naapurin välillä ei ole yhtään kaarta. Toinen tapaus on symmetrinen
Oletetaan että graafissa on 9 solmua. Huomaa, että R(3,4) = R(4,3) . Koska R(3,3) on 6, on helppo todeta että ainoa ei-triviaali tilanne on se, että kullakin solmulla on täsmälleen 5 naapuria. Mutta silloin kaarien määrä on 9*5/2 mikä ei ole kokonaisluku.
Siispä R(3,4) on 9.
Piti sanoa sittenkin näin: Otetaan 8 solmun syklinen graafi ja yhdistetään i:s solmu i 4:een solmuun luvuille i=1,2,3,4.
itseasiassa täsmälleen sama kuin omani.
Tämä havaitaan, kun asetetaan solmut vastaamaan toisiaan vaikkapa seuraavasti: 1=A, 2=D, 3=H, 4=F, 5=C, 6=E, 7=G ja 8=B.
Tämä on helppo todeta, kun etsitään esittämästäni graafista ns. Hamiltonin sykli, joka oli ratkaisusi lähtökohtana.
Toki esitystapasi on havainnollisempi ja helpommin yleistettävissä kattamaan muitakin tapauksia.
suomalaisenkin lukiolaisen ratkaistavaksi. Siinä pitää vain oivaltaa, että nämä positiiviset kokonaisluvut ovat joko parillisia tai parittomia...
Tehtävä 9: Määritä kaikki positiiviset kokonaisluvut n, joilla 2^(n 1)-n^2 on alkuluku.
Alkuluvut 2:ta lukuunottamatta ovat parittomia. 2^(n 1)-n^2 voi olla pariton vain jos n^2 on pariton, eli kun n on pariton. Kun n on pariton, voidaan 2^(n 1) voidaan esittää muodossa (2^((n 1)/2))^2, eli m^2, missä m=2^((n 1)/2) (1).
m^2-n^2 = (m n)(m-n). Jotta luku voisi olla alkuluku, ei sillä saa olla ykköstä suurempia kokonaislukujakajia. Siispä m-n = 1 (2).
(1) ja (2) saamme 2^((n 1)/2)-n = 1, missä n on pariton kokonaisluku. Näemme helposti, että vain n = 1 ja n = 3 käyvät ratkaisuiksi (n = 5 antaa jo liian ison luvun, ja 2^((n 1)/2)^2-n kasvaa kun n kasvaa).
Tarkistetaan vielä, että emme voi saada ainoaa parillista alkulukua, 2, tulokseksi. Jo arvolla n=1: 2^(n 1)-n^2=3, ja arvo kasvaa kun n kasvaa.
Vastaus: n = {1,2} (joita vastaavat alkuluvut {3,7})
Piti tietenkin olla:
Vastaus: n = {1,3} (joita vastaavat alkuluvut {3,7})
Jos n on parillinen, niin se on muotoa 2m ja
2^(n 1)-n^2=2^(2m 1)-(2m)^2=2(4^m-2m^2), missä sulkulauseke on aina suurempi kuin 1.
Luku on siis yhdistetty luku.
Jon n on pariton, niin
2^(n 1)-n^2=(2^((n 1)/2)-n)(2^((n 1)/2) n)
Tästä saadaan ei-triviaali tekijöihinjako, kun n>3
Tapauksissa n=1 ja n=3 saadaan mainitsemasi alkuluvut 3 ja 7.
Ratkaisuhan on periaatteessa ihan samanlainen kuin sinulla, mutta päättely etenee suoraviivaisemmin.
Tällaisessa tehtävässä lienee jo tehtävänannon perusteella helposti arvattavissa, että alkulukuja esiintyy vain äärellisen monta, ja kaikki voidaan eo. tavalla yksilöidä, koska päinvastaisen todistaminen olisi vaikeaa.
Juu, samalla periaatteella nuo parittomat käsittelimme. Parillisissa sen sijaan minä en tullut ajatelleeksi yleisen tapauksen tutkimista, kun niitä parillisia alkulukuja ei tosiaan ole kuin yksi eikä lausekkeesta selvästikään ei voi saada kakkosta tulokseksi.
Epäselvemmissä tai yleistä ratkaisua vaativissa tapauksissa tuo parillisten 2m=n on yleensä erittäin näppärä tapa lähestyä asiaa, mikä kannattaa pitää mielessä.
Mun mielestä et ratkaissut lainkaan tuota tehtävää.
Siinä haetaan matemaattista osaamista, ja todellinen ratkaisu on esitettävä matemaattisesti,
vähän niinkuin seuraavasti:
jos Z (n>N0) ja (n E P) niin 2^(n 1) = P
eli jos kokonaisluku, ehto(luonnollinen luku n on suurempi kuin nolla) ja ehto (luonnollinen luku n kuuluu alkulukuihin) niin lauseke; 2 potenssiin (luonnollinen luku n 1) vähennettynä luonnollinen luku n potenssiin 2 on silloin alkulukujen P joukkoon kuuluva.
Tämä on mielipide, kaava voi olla oikein tai väärin. Matematiikkapalsta, kun on surkea typo-toteutukseltaan.
perehtynyt lukuteoriaan?
Esittämäni tyyppiset todistukset ovat lukuteorian alalla aivan yleisiä.
Voisit ehkä hiukan vaivautua pohtimaan itse asiaa.
Siis jos luku hajoaa ei-triviaaleihin tekijöihin, se on yhdistetty luku. Esittämälläni tavalla esitettyä tyyppiä olevat luvut voidaan hajottaa ei-triviaaleihin tekijöihin (joiden ei välttämättä tarvitse olla alkulukuja) em. kahta tapausta lukuun ottamatta.
Todistusten formaaleihin esityksiin tämä foorumi soveltuu erittäin huonosti. Parempi on keskittyä keskeisten ratkaisuperiaatteiden mielellään sanalliseen esitykseen. Pikku yksityiskohdat saavat myös jäädä lukijoiden oman pohdinnan varaan (esim. että em. tekijät ovat tosiaan ei-triviaaleja).
Todistuksen tärkein ominaisuus on se, että se vakuuttaa lukijansa. Mutta yleensä se asettaa myös lukijalle pieniä vaatimuksia. Jos kaiken mahdollisen pitäisi aina todistaa ihan perusaksioomeista lähtien, ei minkäänlainen edistys matematiikan alalla olisi mahdollista. Siksi matemaattista tietämystä rakennetaan aina askel askeleelta edellisen tietämyksen varaan.
Olen toki tutustunut, Golbachin A. Doxiadidisin väittämiin. Sinunkin nikkisi hakukoneessa yhdistyi
noihin nimiin.
Mitään, yhtään mitään, missä mainitaan sanat; Lappi, Rovaniemi ja matematiikka, en usko pientä palastakaan argumenteista. Sillä mainitulta alueelta ei ole koskaan aiemmin tullut yhtään matematiikkaa
ymmärtävää henkilöä, ja siitä huolimatta nikkisi on Rovaniemellä.
Keskustelun lähtökohta on tuo Norjassa pidetty matemaattinen kutsukilpailu, joten miksi nikkisi
käy kiinni tämän nikin mielipiteisiin? Onko pakko keskustella? Netti on niistä huolimatta täynnä pollutoituneita matematiikan teorioita, ja niiden määrä vain kasvaa.
Perusaksioomia ei tarvitse todistaa, mutta pitäisikö?
Jos jokin aksiooma on kaikille lukijoille triviaali (luvut 1,2,3, ... kuuluvat luonnollisten lukujen joukkoon N)
niin voidaanko aksiooma ilmoittaa nollan arvolla (tyhjä joukko), luonnollisten lukujen merkin N asemesta?
Eikö sellainen menettely matematiikan keskustelupalstalla ole suomeksi sanottuna valehtelua ja
filosofisesti epätieteellistä.
Matemaattisen todistus esitetään väitöstilaisuudessa, ei netissä tuntemattoman nikin edessä.
jos vähän yrittää saada aikaan keskustelua tällaisilla foorumeilla.
Kaikki päättyy epäasialliseen haistatteluun.
Se siitä sitten.
Matti K. S.
http://terveysnetti.turkuamk.fi/nuorisonetti/uni/unih
http://keskustelu.suomi24.fi/node/3161050ygienia.htm
Ratkaisu tehtävään 10.
M=(2*sqrt(n)/(d(n)))^2=4n/(d(n))^2
Valitaan M parittoman alkuluvun neliöksi M=p^2
Nyt
p^2=4n/(d(n))^2, joten
n=p^2*d(n)^2/4=(p*d(n)/2)^2
Koska p on pariton, luku 2 jakaa välttämättä luvun d(n) ts. d(n) on parillinen.
Toisaalta n on positiivisen kokonaisluvun neliö, joten se on muotoa
n = p_1^(2e_1)*p_2^(2e_2)*...*p_m^(2e_m),
missä p_1,p_2,...,p_m ovat luvun n erisuuret alkuluvut ja e_1,e_2,...,e_m positiivisia kokonaislukuja.
Mutta nyt
d(n)=(2e_1 1)(2e_2 1)...(2e_m 1),
joten parittomien lukujen tulona d(n) on pariton. Tämä on ristiriita.
Koska parittomia alkulukuja ja siten myös niiden neliöitä on ääretön määrä, on väite todistettu.
Tehtävä 6: Olkoot a ja b sellaisia kokonaislukuja, että yhtälöllä x^3-ax^2-b=0 on kolme kokonaislukujuurta. Osoita, että b=dk^2, missä d ja k ovat kokonaislukuja ja että d jakaa luvun a.
Mahtaakohan tässä olla tehtävässä virhe, koska d ei välttämätä jaa lukua a?
Esimerkiksi yhtälöllä (x-6)(x-3)(x 2)=x^3-7x^2-36=0 on kolme kokonaislukujuurta. 36 voidaan esittää muodossa 4*3^2 tai 9*2^2, mutta 4 ja 9 eivät kumpikaan taatusti jaa lukua 7.
Tässä vielä tehtävän alkuosa, mikä toki pitää paikkansa:
x^3-ax^2-b voidaan esittää muodossa (x e)(x f)(x g) = x^3 (e f g)x^2 (ef eg fg)x efg, missä e, f ja g kokonaislukuja. Saamme:
a = e f g
b = efg
ef eg fg = 0
Ratkaistaan viimeisestä g = -ef/(e f) ja sijoitetaan b:n yhtälöön:
b = ef(-ef/(e f)) = -(e f)(ef/(e f))^2 (kun lavennetaan (e f):llä).
Tiedämme, että e f on kokonaisluku, kuten myös ef/(e f) (= -g tuossa ylempänä), joten luku on muotoa dk^2.
Sen sijaan tuo toinen väite, että d jakaisi a:n ei kyllä pidä paikkaansa, ellei tässä sitten todella tarkoiteta, että edellisen viestini esimerkissä d = -1 ja k = 6, eli myös 1 kelpaa jakajaksi. Mikä olisi minusta outoa.
meni seuraavasti.
Olkoot x_1,x_2 ja x_3 polynomin x^3-ax^2-b nollakohdat
Nyt
x^3-ax^2-b = (x-x_1)(x-x_2)(x-x_3)=x-(x_1 x_2 x_3)x^2 (x_1x_2 x_2x_3 x_1x_3)x-x_1x_2x_3
Kertoimia vertailemalla saamme
x_1 x_2 x_3=a
x_1x_2 x_2x_3 x_1x_3=0 ja
x_1x_2x_3=b
Jos x_i=0 jollakin i=1,2 tai 3, niin b=0 ja voidaan valita d=1 ja k=0 ts. väite toteutuu triviaalisti.
Oletamme jatkossa, että nollakohdat ovat nollasta eroavia.
Yhtälöstä
x_i^3-ax_i^2-b=0
saamme
x_i^2(x_i-a)=b
kaikilla i=1,2,3.
Siis x_i^2 jakaa luvun b kaikilla i=1,2,3 ja edelleen
lcm(x_1^2,x_2^2,x_3^2)|b
ts.
lcm(x_1,x_2,x_3)^2|b
Merkitään b=dk^2, missä
k=lcm(x_1,x_2,x_3)
Nyt
a/d = a/(b/k^2)) =(x_1 x_2 x_3) lcm(x_1,x_2,x_3)^2/(x_1x_2x_3)
=x_1*lcm(x_1,x_2,x_3)^2/(x_1x_2x_3) x_2*lcm(x_1,x_2,x_3)^2/(x_1x_2x_3) x_3*lcm(x_1,x_2,x_3)^2/(x_1x_2x_3)
=lcm(x_1,x_2,x_3)^2/(x_2x_3) lcm(x_1,x_2,x_3)^2/(x_1x_3) lcm(x_1,x_2,x_3)^2/(x_1x_2)
Tämä on kokonaisluku.
Näin väite on todistettu.
"Yhtälöstä
x_i^3-ax_i^2-b=0
saamme"
Mistä tuo yhtälö tulee?
Ymmärsin muuten että tuoaiempi ihmettelyni oli sikäli turhaa, että d:n täytyy tietenkin voida olla myös 1, jolloin esimerkissäni dk^2 = 36 tekijöihin jako on 1*6^2, eikä ongelmaa ole. Nyt vielä kun ymmärtäisin sen toisen osuuden todistuksen...
luvut x_1, x_2 ja x_3 ovat polynomin x^3-ax^2-b nollakohtia.
Tällaisen riviesityksen lukeminen saattaa olla hiukan hankalaa, mutta se kannattaa kirjoittaa 'auki' perinteiseen matematiikassa käytettyyn 2D-esitykseen. Silloin se loppuosakin selviää.
Oma ratkaisusi ei sellaisenaan toimi, mutta olet ratkaisun jäljillä.
Todistuksen lopussa tarvitaan paria pikkukikkaa, joiden hoksaaminen lienee tässä se avainasia.
lukiolaisten skabassa?
kannattaa huomata, että lukuja n, n 1, ... , n 8 on pariton määrä (9 kpl).
Tästä seuraa, että tulot eivät voi olla yhtäsuuria jostakin n:n arvosta eteenpäin.
Tällainen yläraja luvulle n voidaan määrätä arvioimalla mahdollisia tuloja ylös- ja alaspäin.
Pienet luvun n arvot voidaan sitten käsitellä erikseen etsimällä sellaiset alkuluvut p, että p kuuluu välille [n,n 8], mutta 2p on suurempi kuin n 8.
Näin päädyin siihen tulokseen, etteivät tulot voi olla yhtä suuria millään luvun n arvoilla.