Klika

[Gość: grzesiek]

Zagadka Bociana, oraz brawurowe rozwiązanie Uważnego przypomnialy mi
że znalem podobną zagadkę, której rozwiązania nie znam. Oto ona:

Są trzy grupy ludzi, po N ludzi w każdej. Każdy czlowiek zna N+1 ludzi
z innych grup niż swoja (znajomości w ramach jednej grupy są nieistotne).
Wykazać że istnieje co najmniej jedna klika, t.zn. taka trójka osób, że
każda jest z innej grupy i że znają się nawzajem.
Relacja znajomości jest tu symetryczna, czyli że jeśli A zna B to i B zna A.

[Gość: Student]

Dla N=1 jest to oczywiste.(Można sprawdzić rownież dla n=2) Z zalozenia,że dla
N=k istnieje ww trójka,można łatwo udowodnić,że dla N=k+1 też istnieje taka
trojka.

[Gość: grzesiek]

Chyba masz rację, ale nie do końca to rozumiem. Jeśli dowód polega na tym
że do zastanej sytuacji N=k dodajesz po jednym czlowieku do każdej grupy, to
owszem - ci trzej nowi będą musieli stanowić klikę. Jest tak dlatego, bo
ci trzej nowi muszą domknąć 3*k znajomości z czlonkami starego ukladu, a suma
ich znajomości to 3*(k+2), czyli jest o sześć za dużo. Te sześć muszą
zrealizować między sobą, czyli muszą utworzyć klikę.

Ale czy każdy uklad dla N=k+1 musi dać się skomponować z ukladu N=k + trzech
nowych?

Jaki jest Twój dowód?

[Gość: PM]

Dla uproszczenia wyjasnień ograniczę się do N=10 i zastępuję „znajomośc =
połaczenie telefoniczne”. Każdy z mieszkańców A ma 11 połączeń z mieszkańcami
sąsiednich B i C, podobnie pozostali Z każdego miasta wybiega więc 110
połączeń, rozdzielonych dokładnie po 55 do każdego z pozostałych miast. (Gdyby
np. z A do B było 33, a z A do C – 77 połączeń, to z B do C musiałoby być 77 ,
ale wtedy z C wybiegałoby 154 – co jest sprzeczne z treścią zadania)
Przypuśćmy, że nie istnieje trójka mieszkańców różnych miejscowości połączonych
bezpośrednio ze sobą,,tzn.:idąc wzdłuż połączeń nie trafimy kolejna na te same
osoby. Przejdźmy więc z A do B, ż B do C, z C do A i dalej w tej kolejności jak
utworzone są połączenia. W co najwyżej dziesięciu początkowych obiegach
możemy trafiać na co raz to innych, ale tych obiegów jest u nas 55, więc już w
11 obiegu powtórzymy którąś parę i w dalszych obiegach dobierzemy potrzebny
trzeci w C .Może być ich kilka wśród 10.
W przypadku ogólnym połączeń między dwoma miastami jest n(n+1)/2 i tyle jest
obiegów, a w tym co najwyżej n bez powtórzeń .

[Gość: grzesiek]

Zgadzam się z tym że musi być 55, ale reszta mnie nie przekonuje. To czy
można zrobić 10 obrotów bez powtórzenia osoby nie zależy wcale od faktu
istnienia czy nieistnienia kliki. I dlatego liczenie obrotów wydaje mi się
niepotrzebne. Ale mogę się mylić 8-:)

[Gość: Student]

To nie trzej nowi muszą domknąc klikę (skąd taka nazwa?), tylko na podstawie
załozenia wśród k+1 jest rownież k, dla ktorych (z zalozenia) jest ta trójka,
zresztą nie jedna, bo jest ich kilka.Sprawdź dla n=2 sa dwie takie trójki.

[Gość: grzesiek]

Klika - w takiej wersji usłyszałem tę zagadkę, a zresztą ta nazwa mi pasuje.

Twierdzisz że w k+1 zawiera się k. W takim razie udowodnij że sytuacja k+1
jest redukowalna do sytuacji k przez proste wyjęcie po jednym człowieku
z każdej z trzech grup, ale bez reorganizacji pozostałych znajomości.
Trzeba wykazać że pozostałe po redukcji znajomości spełniają warunek że
każdy człowiek zna k+1 innych.

Jeśli się tego nie uda udowodnić to nie można mówić o tym że k+1 zawiera k,
a co za tym idzie z faktu że dla k jest klika nie będzie wynikało że dla k+1
też musi byc klika.

Bez indukcji

[Gość: Uwazny]

Jeżeli zbiory A, B i C liczą po dziesięć osób i każda z nich łączy się (relacja
znajomość)z 11 osobami z innych zbiorów, to między każdą parą tych zbiorów musi
być dokładnie 55 połączeń, przy czym każdy ma przynajmniej po jednym znajomym
w pozostałych zbiorach. Przypuśćmy, że trójka osób, z różnych zbiorów,
znających się parami, nie istnieje. Znaczy to, że żadna para znajomych z B i C –
takich par jest 55 – nie ma wspólnego znajomego w A. Inaczej mówiąc; każda
para znajomych z B i C zna inna parę osób z A. Ponieważ w A jest 10 osób,
takich par jest tylko 45, zatem istnieje 10 par(z B i C ) w których każda z
osób musi mieć tego samego znajomego.
Przypuszczenie, że poszukiwana trójka nie istnieje,. Doprowadziło do
sprzeczności.
Przy N osobach między parą zbiorów jest n(n+1)/2 połączeń ( i tyle par
znajomych w B i C) natomiast różnych par w A – n(n-1)/2, więc o n więcej.
To mógł wykorzystać Student w dowodzie indukcyjnym. Tam dowód nie polegal na
wykazaniu,ze po odrzuceniu trzech z k+1 pozostali znają po k+1 innych, tylko na
tym,że z liczby ich połączeń da sie otrzymac trójkę.

[Gość: grzesiek]

Już prawie uwierzyłem że to dobry dowód. Ale jest ale. Jeśli B1 zna A1 i C1
zna A2, to nie przeszkadza to w tym że B2 zna A1 i C2 zna A2. Czyli że te 45
par w grupie A to nie jest jakaś wyczerpywalna pula.

Trzeba myśleć dalej. Nadzieję stwarza fakt że w powyższym przypadku już
wiadomo że nie mogą się znać: B1 z C2 i B2 z C1.

Jednak indukcja

[Gość: Uważny]

Masz rację - wyczerpanie zapasu róznych par nie wyklucza użycia ich
wielokrotnie i sprzecznośc jest rudniejsza do wykazania.
Wróćmy jednak do indukcji, Dla n=2 istnieje trojka (konkretnie dwie)
spełniajaca warunki zadania Załozmy,ze i dla n=k taka trójka istnieje.
Wykażemy ,że i dla n=k+1 również taka trójka istnieje. Przy k+1 osobach kazda
zna k+2 osoby i pula wszystkich połączeń wynosi 3(k+1)(k+2)/2. Jezeli odrzucimy
z kazdego zbioru jedna osobę,to wszystkich polaczeń jest 3k(k+2)/2, zaś przy k
osobach było ich "tylko" 3k(k+1)/2. Jesli w poprzedniej sytuacji dla k istniała
poszukiwana trójka, to tym bardziej, przy zwiększonej puli połaczeń, istnieje
dla pozostawionych k (z k+1), a wiec teza została odowodniona.

[Gość: grzesiek]

> Przy k+1 osobach kazda
> zna k+2 osoby i pula wszystkich połączeń wynosi 3(k+1)(k+2)/2. Jezeli odrzucimy
> z kazdego zbioru jedna osobę,to wszystkich polaczeń jest 3k(k+2)/2, zaś przy k
> osobach było ich "tylko" 3k(k+1)/2.

Policzyłem: 3(k+1)(k+2)/2 - 3k(k+2)/2 = 3(k+2)/2

Dlaczego tak? Co to jest to 3(k+2)/2, o które miała by zmaleć liczba połączeń?

[Gość: Uważny]

To nie ma znaczenia - wazne tylko,że w nowym układzie , po odrzuceniu 3, zbiory
dysponują większa liczbą polączeń, niż w poprzednim układzie, więc łatwiej im
zbudować trójkę, o której mowi zalożenie.Przemyśle jeszcze, czy nie ma w tym
rozumowaniu luki. Chwilowo przerwa. Pozdrawiam!

[Gość: grzesiek]

Dodam jeszcze jeden wynik, który wprawdzie nie rozwiązuje zagadki, ale
może pomoże. Już poprzednio wykazalem że jeżeli do zastanego ukladu N=k
dodamy nową trójkę, to żeby powstal prawidlowy uklad N=k+1 ci trzej nowi
muszą stanowić klikę. Udalo mi się udowodnić również coś odwrotnego: jeśli
z ukladu N=k+1 wyjmiemy trójkę, to znowu ta trójka musi stanowić klikę, aby
nowy uklad byl prawidlowym ukladem N=k. Warto również zauważyć że odwrotna
implikacja nie musi być sluszna - jeśli z N=k+1 wyjmiemy klikę nie musi wcale
powstać prawidlowy uklad N=k.

Dowód: liczba znajomości które znikną po wyjęciu trójki z ukladu N=k+1
wynosi 3(k+2)-x. Ten x to liczba znajomości wewnątrz usuniętej trójki.
Rozwiązując równanie 3(k+1)(k+2)/2 - (3(k+2)-x) = 3k(k+1)/2 wychodzi x=3.
Czyli to musi być klika.

jeszcze raz

[Gość: Uważny]

Zauważmy, że z każdego elementu wybiega N+1 połączeń, a po ustaleniu
znajomości od każdej pary znajomych, np. typu BiCj wybiega 2N+1 połączeń , z
tego część (co najmniej 2) do elementów zbioru A. Jeśli wykażemy, że istnieje
para znajomych BiCj połączona N+1 łączami z A, to udowodnimy istnienie kliki
(bo Bi oraz Cj maja wspólnego znajomego).
W zbiorach B i C jest N par o różnych końcach,(np. B1C1, B2C2…BnCn) Występujące
końce realizują wszystkie połączenia elementów Bi oraz Cj z elementami zbioru
A– połączenia np. B1C5 to tylko inna konfiguracja już prezentowanych połączeń.
Załóżmy, że z każdej wymienionej poprzednio pary wybiega do A najwyżej N
połączeń, wtedy wszystkich ich byłoby nie więcej niż N^2, a wiemy, że do A
dobiega N(N+1) łączy., zatem w niektórych parach jest ich więcej niż N, a to
znaczy, że któryś z Am jest połączony z oba końcami BiCj., mamy więc klikę. Co
wiecej, okazuje się,że takich „klik” jest N.
Sprawdź dla np. N=3 lub N=4 na grafach
W metodzie indukcyjnej nie powinno się zakładać, że trzy osoby dochodzą do
poprzedniej grupy, dla której klika istniała, bo istniałaby nadal i dowodzenie
byłoby zbędne. Trzeba założyć, że nic nie wiemy o „starych” układach, a
jedynie, że dla k osób da się zbudować klikę przy wprowadzonym założeniu.
Nowy A może znać wszystkich z B bez 2 i 3 z C; B wszystkich z C bez 2 i 3 z
A ;
C wszystkich z A bez 2 i 3 z C. A i C nie musza się znać i nie tworzą kliki.

[Gość: grzesiek]

To już chyba to, ale jedna rzecz wymaga jeszcze uściślenia. Piszesz że:

> W zbiorach B i C jest N par o różnych końcach,(np. B1C1, B2C2…BnCn)

Z reszty tekstu wynika że to chodzi o N par znajomych z B i C, a to jest
dla mnie niejasne że ich musi być aż N.

[Gość: Student]

Pozwolę sobie na uwagi
Tych par znajomych z B i C jest znacznie więcej, bo N(N+1)/2, ale par o różnych
końcach z B i C jest dokladnie N, przy czym jesli B1C1 się znają, to B1 lub C1
maja jeszcze znajomych poza A.Suma znajomych B1 lub C1 wynosi 2N i gdyby to
byli wszscy z A (teoretycznie mozliwe dla kilku par) wtedy taka para
wchodziłaby w sklad N klik. Wprowadzenie nowych znajomych dla B1 i C1 spoza A
pozwala tworzyć pary nowych elementów w B i C.

[Gość: grzesiek]

Widzę w Twoim tekście pewne nieścislości, ale to nic. Jeśli by Ci się
udalo udowodnić że par Bi-Cj znajomych, ale o różnych końcach jest N, to
byli byśmy w domu - to by wystarczylo do domknięcia dowodu Uważnego.