1.68
Jos permutaatiossa jokaisen alkion paikka muuttuu, sitä voidaan kutsua
sekoitukseksi. Jos tehdään peräkkäin kaksi sekoitusta, onko niiden
yhteistulos välttämättä sekoitus?
1.91
Joukossa X on ensimmäiset 2n positiivista kokonaislukua, ja siitä
valitussa osajoukossa S on n + 1 lukua. Osoita, että joukossa S on
kaksi kokonaislukua, joista toinen on jaollinen toisella.
1.94
Osoita, että 10 henkilön ryhmässä on aina (a) 3 henkilöä, jotka
ovat toisilleen vieraita, tai 4 henkilöä, jotka tuntevat toisensa, ja
(b) 3 henkilöä, jotka tuntevat toisensa, tai 4 henkilöä, jotka ovat
toisilleen vieraita.
1.95
Osoita, että 20 henkilön ryhmässä on aina joko 4 henkilöä, jotka tuntevat
toisensa, tai 4 henkilöä, jotka ovat toisilleen vieraita.
1.98
Osoita, että jos m ja n ovat kokonaislukuja ja suurempia
kuin 2, niin R(m, n) ≤ R(m - 1, n) + R(m, n - 1). (Tämä
epäyhtälö antaa erään ylärajan luvulle R(m, n).)
1.99
Osoita, että jos m ja n ovat kokonaislukuja ja suurempia
kuin 1, niin R(m, n) ≤ C(m + n - 2, m - 1). (Tässä yläraja
saadaan ilman rekursiota.)
1.100
Osoita, että jos R(m - 1, n) ja R(m, n - 1) ovat kumpikin
parillisia ja suurempia kuin 2, niin R(m, n) ≤ R(m - 1, n) + R(m, n
- 1) - 1.
1.101
Osoita, että R(4, 3) = 9.
1.110
Aritmeettinen jono muodostuu luvuista a, a + d, a + 2d, ..., a + (n -
1)d, kun a on ensimmäinen luku, d on kahden
peräkkäisen luvun erotus ja n on lukujen määrä. Osoita, että
kun luvut 1, 2, ..., 9 jaetaan kahteen joukkoon, ainakin toisessa
joukossa on aritmeettinen jono, jossa on kolme jäsentä.
1.111
Geometrinen jono muodostuu luvuista a, ad, ad2,
ad3, ..., adn - 1, kun a on ensimmäinen
luku, seuraava luku saadaan kertomalla edellinen d:llä ja lukuja on
kaikkiaan n. Osoita, että kun luvut 1, 2, 3, ...,
28 jaetaan kahteen joukkoon, ainakin toisessa joukossa
on geometrinen jono, jossa on kolme jäsentä.