Harjoitus 3 (26.9.2007)

1.61
Liisalla on 11 työtoveria, 8 miestä ja 3 naista, joista hän kutsuu osan syömään. Kuinka monta eri seuruetta voi syntyä, jos Liisa kutsuu (a) ainakin 9 työtoveriaan, (b) kaikki naiset ja miehiä sen verran, että naisia ja miehiä on yhtä monta (Liisa mukaan lukien).

1.74
Reaalilukujono (a₁, a₂, ..., a_n) on unimodaalinen, jos on olemassa positiivinen kokonaisluku 1 < j < n niin, että a₁ < a₂ < ... < a_{j - 1} ≤ a_j > a_{j + 1} > ... > a_n. Osoita, että lukujono (C(n, 0), C(n, 1), ..., C(n, n)) on unimodaalinen, kun n > 1, ja määritä lukujonon suurin luku.

1.76
Joukossa X ovat luvut 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ja 10. Osoita, että kun joukosta valitaan 7 luvun osajoukko, siihen kuuluu varmasti kaksi lukua, joiden summa on 10. Esim. osajoukko {0, 2, 3, 5, 6, 8, 9} täyttää tämän vaatimuksen, 2 + 8 on näet 10.

1.78
Eräässä turnauksessa oli n pelaajaa, jotka pelasivat kaikki toisiaan vastaan, ja kukin pelaaja voitti ainakin kerran. Osoita, että kaksi pelaajaa voitti väistämättä yhtä monta kertaa.

1.79
Osoita, että mistä tahansa n kokonaisluvun joukosta voidaan valita epätyhjä osajoukko, jonka lukujen summa on jaollinen n:llä.

1.80
Joukossa X on 9 eri positiivista kokonaislukua. Mikä joukon suurin luku n voi olla pienimmillään ja suurimmillaan, jotta joukosta voidaan aina valita kaksi eri epätyhjää osajoukkoa, joiden lukujen summat ovat samat.

1.84
Osoita, että mikä tahansa joukko, jossa on 7 eri kokonaislukua, sisältää kaksi kokonaislukua, joiden summa tai erotus on jaollinen 10:llä.

1.85
Urheilujoukkue pelasi 15 päivän pelikauden aikana 20 peliä. Sääntöjen mukaan joukkueen täytyy pelata vähintään yksi peli päivässä. Osoita, että pelikauteen kuului peräkkäisten päivien jakso, jonka aikana joukkue pelasi tasan 9 peliä.

1.86
Osoita, että jos n esinettä pannaan r laatikkoon ja n < r(r - 1) / 2, niin ainakin kahdessa laatikossa on yhtä monta esinettä.

1.90
Osoita, että mikä tahansa lukujono, jossa on n² + 1 eri reaalilukua, sisältää vähintään n + 1 luvun monotonisen (nousevan tai laskevan) alijonon. Osoita vastaavasti, että jos lukujonossa on n eri lukua, monotonisen alijonon pituus on ainakin √n.