Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko

23.04.2009
czwartek

Najmniej drużyn

23 kwietnia 2009, czwartek,

Dziękuję Jazzowi, pixlowi i Michałowi, także w imieniu mojego niepołamanego ołówka, za eleganckie dowody, że:

nie ma takich pięciu liczb naturalnych (bez zera) niepodzielnych przez 3 i 7, by suma każdych dwóch z nich była podzielna przez 3 lub 7.

Na wyróżnienie zasługuje moim zdaniem dowód pixla – oparty na grafie i niemal klasyczny, bo bliski twierdzeniu i liczbom Ramseya. Pixl wykazał, że żaden graf pełny K5 (5 wierzchołków) bez klik monochromatycznych K3 nie spełnia warunków zadania („klika” to matematyczne określenie podgrafu pełnego, a więc stanowiącego część większego grafu pełnego).

Dowód można by uprościć, nie kolorując krawędzi, a pozostając tylko przy liczbach lokowanych w wierzchołkach. Powinny one należeć do dwu różnych podzbiorów – A i B (od tego zaczęli Jazz i Michał), przy czym w wierzchołkach żadnego trójkąta-kliki nie mogą występować liczby z tego samego podzbioru. Są zatem tylko dwa podstawowe sposoby umieszczenia liczb z podzbiorów A i B w wierzchołkach jakiegoś trójkąta, powiedzmy ostrokątnego:

W obu przypadkach nie da się oznaczyć dwóch pozostałych wierzchołków literami A i B tak, by nie pojawił się trójkąt „monoliterowy”, czyli dochodzimy do sprzeczności.

Korzystanie z grafów często bywa pomocne przy dowodzeniu, ilustrowaniu lub rozwiązywaniu zadań, w których występują zależności między podzbiorami, zwłaszcza gdy sformułowanie tych zależności powoduje lekki mętlik w głowie – jak w pamiętnej łamigłówce o dyngusowym polewaniu (dotychczas w komentarzach pod wpisem „Dziewki i parobcy” nie pojawiło się poprawne rozwiązanie; pomijając 1 parobka i 6 dziewek).

Oto inny przykład, łatwiejszy od „folwarcznego” zadania.

Zakończył się turniej siatkówki, w którym każde dwie drużyny rozegrały dokładnie jeden mecz.

Czyli na razie sprawa jest jasna, nic trudnego do zrozumienia – typowy system rozgrywek „każdy z każdym”, zwany także kołowym. I oto pojawia się stwierdzenie wprowadzające niejaki zamęt:

Dla dowolnych trzech drużyn można wskazać taką, która pokonała każdą z tych trzech.

I pytanie:

Ile drużyn startowało w turnieju, jeżeli liczba ta była najmniejszą, przy której mogło pojawić się to zadanie?

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 11

Dodaj komentarz »
  1. Jeśli drużyna X wygra swoje wszystkie mecze – a często tak bywa – to powyższe stwierdzenie nie będzie nigdy prawdą, bez względu na to, ile drużyn wystartuje, bo dla X nie da się wskazać takiej, która z nią wygrała.
    Pozdrawiam PM.

  2. Według mnie 9-kąt mógłby spelniać warunki podane w zadaniu

  3. Można sprawdzić (udowodnić), czy (że) liczba drużyn (wierzchołków grafu) jest poprawna, rysując krawędzie grafu w postaci strzałek. Powstanie wówczas graf pełny quasi-skierowany, w którym każda strzałka będzie wychodzić z punktu A (drużyna zwycięska w meczu A z B) do punktu B (drużyna pokonana w tym meczu). Jeżeli uda się tak oznaczyć kierunki strzałek, że warunki zadania będą spełnione, to będzie prawie OK.
    Prawie, bo wypadałoby jeszcze udowodnić, że dla grafu z mniejszą liczbą wierzchołków nie może być OK.
    m

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Panie Marku, będę upierdliwy: ten problem nie ma wogóle rozwiązania !!!
    Bo może być, że jedna wygra wszystkie mecze, prawda ?
    Warunki zadania nigdy nie będą spełnione.
    Pozdrawiam PM.

  6. empiotr1:
    Oczywiście, że w jakimś turnieju może tak być, ale w turnieju, którego dotyczy zadanie – nie. Przecież wtedy nie będzie spełniony warunek, że dla dowolnych trzech drużyn… (itd).
    Wszak turniej już się odbył i wyniki istnieją (i spełniają określone warunki), a Pan chce go zorganizować jeszcze raz tak, żeby jakaś drużyna wygrała wszystkie mecze.
    m

  7. Z tym 9 ciokątem przesadzilem.
    Teraz jestem pewien że taki 14-kąt istnieje, ale nie wiem
    czy nie ma przypadkiem jakiegoś 13-kąta

  8. Jmaurycy:
    Z 14-stokatem na pewno sie nie uda.
    Nie mam pomyslu, jak graficznie w komentarzu przedstawic schemat turnieju dla 14 druzyn, ale gdybys potrafil to zrobic, to chetnie bym taki schemat zobaczyl.
    Z mojego dowodu, ktory jest oparty na tym, jaki podal w następnym wpisie autor bloga wynika, ze ponizej 15-kata sie nie zejdzie.
    a

  9. w 14 kącie są aż 364 trójki.
    w pewnej konstrukcji 14 -kąta nie znalazlem trójki której nie bylo, ale nie moglem ręcznie sprawdzić tych kombinacji.
    Dlatego mam zamiar napisać w tym tygodniu program, który będzie takie rzeczy sprawdzal.

    Swoje przekonanie opieram na czymś takim
    w 6-kącie jest 20 trójek
    w 7-kącie jest 35 trójek
    w 8 kącie są 54 trójki
    14 kąt ma 364 trójki
    W 14-kącie
    każdy punkt ma do dyspozycji 13 punktów(max 13 wygranych)
    tak więc 13/2=6,5 czyli w pewnym 14-kącie
    – jest 7 punktów które wygralo z 6 drużynami
    – jest 7 punktów które wygrało z 7 drużynami
    7*20+7*35=385
    385>364
    {jeśli nawet znalazlbym trójki której nie ma
    mogbym zmienić ten 14-kąt poprzez likwidacją jakiegoś powtórzenia
    które mogę usunąć i taką zamianę }

    Dla dwójek pokazany jest siedmiokąt
    w 7-kącie jest 21 dwójek
    ponieweważ teoretycznie latwo jest skonstruować
    taki siedmiokąt, w którym każda drużyna wygrala z 3 drużynami
    a w trójce są 3 dwójki
    więc 3*7=21

  10. W Siedmiokącie Pana Marka
    Każdy punkt ma wlasnie po 3 wygrane

    Co do 13-kąta
    13 kąt ma 286 trójek każdy punkt ma do dyspozycji 12 innych
    // w sytuacji w której każda drużyna wygrala z 6
    13 * 20{{liczba 3 w 6-kacie}} =260
    260 < 286 {a można jeszcze kombinować z 8-kątami ale nie wiem czy to oplacalne}

  11. Panie marku jaka jest prawidlowa odpowiedz

  12. Andy podał poprawną odpowiedź – 15.
    Ogólnie, jeśli dla każdych d drużyn znajdzie się taka, która z żadną nie przegrała, wówczas liczba drużyn startujących w turnieju nie może być mniejsza od 2^(d+1) – 1, czyli dla kolejnych d mamy ciąg 3, 7, 15, 31…
    Szczerze mówiąc, nie mam jednak pewności, czy ten wzór „działa” dla wszystkich d.
    m

css.php