Zad. 1. Dana jest liczba naturalna a>0. Wykaż, że istnieje nieskończenie wiele takich liczb naturalnych n>0, że 2a+1 | 2an+1.
Zad. 2. Udowodnij, że jeżeli n jest liczbą naturalną większą od 2, to 2n(n–1)/2 > n!.
Zad. 3. Grafem dopełniającym grafu G o n wierzchołkach nazywamy graf G' o tym samym zbiorze wierzchołków, taki że równoważne są warunki: a) w G jest krawędź pomiędzy wierzchołkami v i w oraz b) w G' nie ma krawędzi pomiędzy wierzchołkami v i w. Załóżmy, że pewien graf G po permutacji nazw wierzchołków jest równy swojemu grafowi dopełniającemu. Udowodnij, że liczba wierzchołków n daje z dzielenia przez 4 resztę 0 lub 1.
W tym miesiącu 30 pkt. zdobyła Hanna Osajda III LO Wrocław.
Zad. 1. Niech q = 2a+1. Ponieważ q i a są względnie
pierwsze, istnieje d takie, że [tex]a^d \equiv 1[/tex] (mod q). Niech n = kd+1 dla dowolnego k naturalnego. Wówczas
[tex]2a^n + 1 = 2a^{kd+1} +1 == 2a(a^{d})^k + 1 \equiv_q 2a+1 \equiv_q 0[/tex],
zatem 2a+1 | 2an+1 dla n takiej postaci.
Zad. 2. Pokażemy najpierw, że dla m ≥ 2 mamy 2m > m+1, stosując indukcję względem m. Po pierwsze 4 > 3. W kroku indukcyjnym mamy 2k+1 = 2k · 2 > 2(k+1) = 2k+2 > k+2. Wracając do głównego problemu, zauważmy, że 2½n(n–1)=2 · 22 · 23 · ... · 2n–1 > 2 · 3 · 4 · ... · n = n!, c.k.d.
Zad. 3. W
treści zadania n to liczba wierzchołków. Niech m będzie liczbą
krawędzi grafu G. Graf dopełniający ma tyle samo wierzchołków (a nawet te same
wierzchołki). Wszystkich możliwych krawędzi między n wierzchołkami jest
½n(n–1), więc graf dopełniający ma ½n(n–1) – m krawędzi.
Otrzymujemy równanie ½n(n–1) – m = m, czyli 4m = n(n–1). Skoro n i n–1 są względnie pierwsze, to 4 musi dzielić albo n albo n–1,
co oznacza że reszta z dzielenia n przez 4 jest równa 0 lub 1.
To zabawny samouczek, który zaczynając się niewinnie intrygującą historyjką, krok po kroku, poczynając od najłatwiejszych łamigłówek, prowadzi nas w szpony, nie bójmy się użyć tego słowa, uzależnienia.
