12(rozwiązane przez binaja)
W pewnej szkole uczy się 1995 uczniów. Każdy z nich ma wśród pozostałych co najmniej 45 znajomych. Udowodnij, że zawsze znajdziemy takich czterech uczniów tej szkoły, którzy mogą usiąść przy okrągłym stole tak, by każdy siedział obok swoich znajomych.
12:
Rozważmy ucznia \(\displaystyle{ a_1}\) i jego znajomych \(\displaystyle{ a_2 \ldots a_{46}}\)
jeśli któraś dwójka z \(\displaystyle{ a_2 \ldots a_{46}}\) ma wspólnego znajomego to możemy go razem z tą dwójką i \(\displaystyle{ a_1}\) posadzić przy tym stole, załóżmy, że tak nie zachodzi wówczas każdy z \(\displaystyle{ a_2 \ldots a_{46}}\) ma innych znajomych, razem musi ich być co najmniej \(\displaystyle{ 45 \cdot 44 =1980}\) czyli wszystkich uczniów co najmniej 1980 +46 = 2026-sprzeczność
Moje pytanie: Co by było jeśli \(\displaystyle{ a_{2}}\) zna \(\displaystyle{ a_{3}}\) oraz \(\displaystyle{ a_{2}}\) i\(\displaystyle{ a_{3}}\) nie mają żadnych wspólnych znajomych poza \(\displaystyle{ a_{1}}\); \(\displaystyle{ a_{4}}\) zna \(\displaystyle{ a_{5}}\) i oraz \(\displaystyle{ a_{4}}\) i \(\displaystyle{ a_{5}}\) nie mają żadnych wspólnych znajomych poza \(\displaystyle{ a_{1}}\); \(\displaystyle{ a_{6}}\) zna \(\displaystyle{ a_{7}}\) itd.?
Bo jak dla mnie wtedy nie można udowodnić tezy zadania w sposób przedstawiony powyżej... Ludzi w szkole jest wtedy conajmniej 45*43+46<1995 (nie ma sprzeczności)
Napisz może, co konkretnie reprezentują u Ciebie liczby 45, 43, 46 w działaniu "45*43+46<1995"
Ja też miałem problem ze zrozumieniem rozwiązania binaja, ale chyba już kapuję, tzn. \(\displaystyle{ a_1}\) ma 45 znajomych. Zakładamy, że każdy z tych czterdziestu pięciu znajomych nie ma wspólnego znajomego, oprócz \(\displaystyle{ a_1}\) (gdyby taki istniał, to wsadzamy go pod stół i jest teza ). Z treści zadania wiemy, że każdy ma co najmniej 45 znajomych, więc znajomi \(\displaystyle{ a_1}\) mają po 45-1=44 znajomych (bo odjęliśmy \(\displaystyle{ a_1}\) ). Mamy więc już \(\displaystyle{ 44 \cdot 45 = 1980}\) uczniów, ale musimy jeszcze wziąć pod uwagę, że nie dodaliśmy do tego jeszcze znajomych \(\displaystyle{ a_1}\) oraz samego \(\displaystyle{ a_1}\). Więc razem mamy co najmniej 1980+45+1 - sprzeczność
Ponieważ kiepsko posługuję się słowem, narysowałam bohomazka. Może on lepiej objaśni o co mi chodzi?
A rozwiązanie binaja rozumiem całkowicie poza tym czemu pominięto przypadek, który w tym temacie nieudolnie opisuję.
Wiem, że jestem blondynka, ale naprawdę proszę o pomoc w zrozumieniu co z moim rozumowaniem jest nie tak;)
Hm, jeśli dobrze rozumuję Twój jakże ładny bochomazek, to masz tak: \(\displaystyle{ a_1}\) oraz jego 45 znajomych - razem 46 uczniów \(\displaystyle{ a_2}\) zna 43 swoich znajomych oraz \(\displaystyle{ a_3}\) - razem 44 znajomych, ale z treści zadania wiemy, że każdy ma co najmniej 45 znajomych, zatem wśród 43 znajomych musi się znaleźć jeszcze jakiś jeden, czyli jest ich razem 43+1=44
Analogicznie dla 43 znajomych \(\displaystyle{ a_3 , \ldots a_46}\).
Mam nadzieję, że nie piszę głupot i dobrze to napisałem
edit
O, widzę, że głupoty jednak popisałem Przepraszam i również czekam z niecierpliwością na rozwiązanie tego problemu
ok, chyba mam:
wykażemy, że istnieje gość co zna co najmniej 46 innych osób, gdyby tak nie było, każdy znałby dokładnie 45, czyli liczba znajomości byłaby: \(\displaystyle{ \frac{1995 \cdot 45}{2}}\) (przez 2 bo znajomości, zliczamy podwójnie), ale liczba znajomości byłaby wtedy niecałkowita-sprzeczność
Rozważmy ucznia \(\displaystyle{ a_1}\) i jego znajomych \(\displaystyle{ a_2 \ldots a_{47}}\)
Każdy z uczniów \(\displaystyle{ a_2 \ldots a_{47}}\) może mieć wśród \(\displaystyle{ a_2 \ldots a_{47}}\) maksymalnie 1 znajomego, gdyby miał 2 to sadzamy go z tymi znajomymi i \(\displaystyle{ a_1}\)
jeśli któraś dwójka z \(\displaystyle{ a_2 \ldots a_{47}}\) ma wspólnego znajomego to możemy go razem z tą dwójką i \(\displaystyle{ a_1}\) posadzić przy tym stole, załóżmy, że tak nie zachodzi wówczas każdy z \(\displaystyle{ a_2 \ldots a_{47}}\) ma innych znajomych, razem musi ich być co najmniej \(\displaystyle{ 46 \cdot 43 =1978}\) czyli wszystkich uczniów co najmniej 1978 +47 = 2025-sprzeczność
