Zadania 2011/12

1. Jak z udowodnionych przez nas ostatnio własności kongruencji wynikają te pierwsze (że do obu stron można dodać lub obie pomnożyć przez tę samą liczbę)?

2. A jak, że obie strony kongruencji można podnieść do dow. potęgi naturalnej? (A czy otrzymamy wówczas zawsze kongruencję równoważną?)

3. Kiedy z kongruencji ab≡ac wynika b≡c (mod p)?

4. Znajdź x spełniające jednocześnie warunki: x≡5 (mod 7), x≡2 (mod 3) i x≡18 (mod 101). A gdyby dodać jeszcze x≡5 (mod 9)? A x≡13 (mod 14)? Jakie mogą być m, żeby po dorzuceniu do początkowych trzech warunku x≡a (mod m) z zupełnie dowolnym a istniały x spełniające wszystkie cztery?

Zadania 2010/11

Ad Fermat (Euler?):

- wykazać, że dla dowolnego naturalnego a każda liczba pierwsza p dzieli a - a^pⁿ (a do potęgi pⁿ)
- znaleźć wszystkie pierwsze p i , dla których p^q = q^p+1
- udowodnić, że jeśli p jest prawie dowolną (tzn. jaką dokładnie?) liczbą pierwszą, to pewna jej wielokrotność ma w zapisie dziesiętnym same dziewiątki
- spróbować przenieść powyższe twierdzenie na inne systemy pozycyjne

Na 2 XII proszę znaleźć reszty z dzielenia przez (pierwsze!) p sum:

1. 1^p+2^p+3^p+...+(p-1)^p
2. 1^p-2^p+3^p-...+/-(p-1)^p

Na 4 XI proponuję przemyśleć:

1. czy istnieje graf płaski o liczbie chromatycznej 4 niezawierający 4-elementowej kliki,
2. czy istnieje graf o liczbie chromatycznej 5 (zatem niespłaszczalny - jasne dlaczego?) niezawierający kliki 5-elementowej,
3. czy twierdzenie o czterech barwach zachodzi również dla sfery.

Zadania na 6 X:

1. Udowodnij, że [prosty] graf płaski o w wierzchołkach ma najwyżej 3w-6 krawędzi.
2. Czy istnieje wielościan o 2011 wierzchołkach i 1001 ścianach?
3. Udowodnij, że jeśli każda ściana wielościanu wypukłego jest 5- lub 6-kątem foremnym, to ścian pięciokątnych jest dokładnie 12, a wielościanów takich jest skończenie wiele.

1. Czy K₅ da się narysować na płaszczyźnie bez przecięć krawędzi?
2. Udowodnij, że każdy [prosty] graf płaski (czyli taki, który da się narysować na płaszczyźnie bez przecięć krawędzi) ma wierzchołek stopnia mniejszego niż 6.
3. Udowodnij, że każdy wielościan wypukły ma ścianę trójkątną lub kąt trójścienny (tzn. w pewnym wierzchołku schodzą się trzy ściany). Podpowiedź: dla wielościanów wypukłych też działa wzór Eulera (można przy okazji pomysleć nad dowodem tego faktu - przeprowadzimy go na zajęciach).

1. Znajdź wszystkie grafy regularne o 7 wierzchołkach. Staraj się zrobić to systematycznie, tak żeby żadnego nie pominąć, i pomyśl nad uzasadnieniem, czy wszystkie znalezione są faktycznie różne.
2. Ile cykli Hamiltona ma pełny graf o n wierzchołkach?
3. Przypomnę, że dopełnieniem grafu G nazywamy graf o tych samych wierzchołkach co G, taki że dla każdych dwóch wierzchołków są one połączone wtedy i tylko wtedy, gdy nie są połączone w G.
   Czy zachodzą poniższe implikacje?
   1) Jeśli G jest spójny, to jego dopełnienie nie.
   2) Jeśli G nie jest spójny, to jego dopełnienie jest.
4. Ile krawędzi może mieć graf prosty o n wierzchołkach? To proste, ale jeśli pytać tylko o grafy spójne? A niespójne?
5. Dowiedź, że (nieizomorficznych oczywiście) drzew o n wierzchołkach jest nie więcej niż (n-1)!. A może znajdziesz lepsze oszacowanie? A może dokładny wzór?!! :)

Michal.Sliwinski@math.uni.wroc.pl