czerwiec 2012

Zad. 1. Wprowadźmy układ współrzędnych, tak by współrzędne wszystkich wierzchołków dużego sześcianu były liczbami -½ lub 99½. Poprowadźmy po 99 dobrych prostych - w płaszczyźnie xy przechodzące przez pary punktów: (1, 0, 0) i (1, 99, 0), (2, 0, 0) i (2, 99, 0), ... oraz (99, 0, 0) i (99, 99, 0), w płaszczyźnie xz przechodzące przez pary punktów: (0, 0, 1) i (99, 0, 1), (0, 0, 2) i (99, 0, 2), ... oraz (0, 0, 99) i (99, 0, 99) i w płaszczyźnie yz przechodzące przez pary punktów: (0, 1, 0) i (0, 1, 99), (0, 2, 0) i (0, 2, 99), ... oraz (0, 99, 0) i (0, 99, 99). Wówczas nie da się poprowadzić kolejnej dobrej prostej rozłącznej z tymi. Jeśli zaś założyć, że szukane w zadaniu n<297, to musiałaby istnieć oś, taka że liczba dobrych prostych poprowadzonych równolegle do niej w ekstremalnym układzie (oznaczmy ją przez k) wynosiłaby najwyżej 98 (w przeciwnym wypadku prostych byłoby co najmniej 3·99=297). W każdej warstwie sześcianików prostopadłej do owych k prostych może zatem biec co najmniej 100-k dobrych prostych z nimi rozłącznych. Razem daje to 100(100-k)=10000-100k, natomiast poprowadzonych w z założenia najlepszym przypadku jest najwyżej 296-k. Nierówność 296-k≥10000-100k daje k≥9704/99>98, co przeczy założeniu. 297 jest zatem szukaną w zadaniu liczbą.

Zad. 2. m-elementowych podzbiorów n-elementowego zbioru jest [tex]{n}\choose{m}[/tex], a wszystkich podzbiorów ma on 2ⁿ, czego nietrudne do zrozumienia dowody można łatwo odnaleźć. W zadaniu chodzi zatem o znalezienie wzoru na [tex]\sum_{m=1}^{n}m{{n}\choose{m}}[/tex], co można zrobić np. tak: [TEX]\sum_{m=1}^{n}m{{n}\choose{m}}=\sum_{m=1}^{n}\frac{n!}{(m-1)!\cdot(n-m)!}=\sum_{m=1}^{n}\frac{n\cdot(n-1)!}{(m-1)!\cdot((n-1)-(m-1)!}\ .[/TEX] Po wyłączeniu wspólnego czynnika n przed sumę mamy dalej: [tex]n\sum_{m=1}^{n}{{n-1}\choose{m-1}}[/tex], co po przenumerowaniu składników jest tym samym co [tex]n\sum_{m=0}^{n-1}{{n-1}\choose{m}}[/tex], czyli n·2^n-1 (bo sumowane są kolejno liczby 0-, 1-, 2-, ... i (n-1)-elementowych podzbiorów (n-1)-elementowego zbioru). Warto zauważyć, że ten sam wynik można uzyskać również tak: podzbiorów zbioru {1, 2, 3, ..., n} zawierających jego dany element d jest tyle samo co podzbiorów d niezawierających (bo każdy podzbiór bez d odpowiada wzajemnie jednoznacznie zbiorowi, który powstaje z niego przez dodanie {d}). Zatem każdy element zbioru {1, 2, ..., n} jest elementem dokładnie połowy spośród wszystkich 2ⁿ jego podzbiorów i tyle razy powinien być zliczony w szukanej sumie. Otrzymujemy zatem n·2ⁿ/2.

Zad. 3. Łatwo sprawdzić, że jeśli trójka (x, y, z) jest rozwiązaniem danego równania, to trójka (x/2, y/2, z/2) również, tak samo zatem trójka (x/4, y/4, z/4) itd. Jednocześnie zauważmy, że x³=2(3xyz-y³-2z³), x musi być więc parzyste. Skoro jednak tak, to jest postaci 2k dla pewnego k całkowitego i y³=2(3kyz-2k³-z³) oznacza parzystość y. Analogicznie parzyste musi być z kolei z, zatem x/2, y/2 i z/2 to również liczby całkowite i także muszą być parzyste (bo jako do rozwiązania danego równania stosuje się do nich to samo rozumowanie), podobnie x/4, y/4, z/4 itd. w nieskończoność. Jest to możliwe tylko dla x=y=z=0 i jest to jedyne rozwiązanie, co sprawdzamy, podstawiając.