Mam prośbę o pomoc w rozwiązaniu zadania. Chciałbym to wyjaśnić synowi ale wstyd przyznać mam z tym zadaniem problem.
"Na przyjęcie przyszło n osób. Początkowo każdy znał dokładnie 3 znajomych wśród pozostałych osób obecnych na przyjęciu. W trakcie przyjęcia niektóre osoby poznały się, w wyniku czego pod koniec przyjęcia każdy miał wśród pozostałych dokładnie 4 znajomych. Wyznacz wszystkie liczby n, dla których opisana sytuacja jest możliwa. (Przyjmujemy, że jeśli osoba A zna osobę B, to osoba B zna osobę A)".
Moim zdaniem warunek spełni n większe lub równe5 ale nie jestem pewien czy to jest ok i nie wiem jak to rozpisać.
Jesli dobrze zrozumialem zadanie
Poczatek -> osoba A ma 3 znajomych
Koniec -> osoba A ma 4 znajomych
Wychodzi na to, ze:
A zna poczatkowo B,C,D a pod koniec B,C,D,E - co najmniej 5 osob, zeby zadanie mialo sens.
Osoba B zna juz A, wiec ma do wyboru jeszcze dwojke znajomych - musi tam byc E i na przyklad C.
C zna B i zna A, wiec nie moze znac D, bo musi znac E.
E zna B,C,D bo nie moze znac A (musi byc nowym znajomym dla A).
Zostaje nam D, ktory zna A, oraz E, lecz nie moze znac ani C (bo C zna B,A,E), ani B (bo B zna C,A,E). Skoro wszyscy mieli po 3 znajomych, to mamy sprzecznosc - D ma tylko 2 znajomych w sytuacji gdy jest tylko 5 osob. Musi byc jeszcze jedna osoba.
Wtedy mamy osobe F, ktora jest trzecim znajomym brakujacym znajomym.
Latwo wyznaczyc to na podstawie wieloboku - narysujesz pieciokat (wierzcholki to osoby), to nie bedzie mozliwosci, zeby wychodzily poczatkowo tylko 3 wektory z kazdego wierzcholka. Przy szesciokacie (6 osob) juz jest taka mozliwosc. Ale jak wezmiesz siedmiokat, to sie nie uda - zostanie jeden wierzcholek. Musi byc parzysta liczba osob. Przy nieparzystej liczbie, zawsze zostanie jeden wierzcholek, z ktorego nie wyjda 3 wektory (2, albo 4). Mozna powiedziec, ze kwadrat tez sie nadaje, bo z kazdego wierzcholka wychodza 3 wektory, ale to sprzeczne z zalozeniami zadania, bo nie moga rownoczesnie wyjsc 4 wektory (czyli pozniejsza liczba znajomych).
Tak wiec, rozwiazanie zapisalbym w postaci: n e (nalezy do zbioru) [2m] dla m>=3, m e (nalezy do) N (zbior liczb naturalnych)
No nie jestem przekonany :)
Żeby każdy miał 3 znajomych wystarczą 4 osoby
A, B, C, D
i mamy konfig
AB, AC, AD
BA BC BD
CA CB CD
DA DB DC
Żeby zadanie było spełnione musi być jednak minimum jedna osoba więcej czyli dojdzie E
AB, AC, AD, AE
BA BC BD BE
CA CB CD CE
DA DB DC DE
Ale w zadanie jest napisane: "W trakcie przyjęcia niektóre osoby poznały się," czyli nie wszystkie muszą się poznać - czyli teoretycznie może być np 100 osób, z których każda pozna tylko jedną nową osobę.
Chyba, że czegoś nie rozumiem :/. Nigdy nie lubiłem takich zadań, kiedyś miałem nadzieje, że skończyło się to wraz z edukacją ale niestety po czasie dopadło mnie znowu :)
Może jeszcze ktoś potwierdzi wersję szymona_majewskiego lub podpowie mi coś?
MiB -> no dobra, ale wychodzi na to, ze osoba E nie miala zadnych znajomych i to probowalem udowodnic.
Ale przemyslalem tresc zadania i wynika na to, ze tez sie mylilem.
"każdy miał wśród pozostałych dokładnie 4 znajomych"
Co by oznaczalo, ze kazda osoba na przyjeciu oprocz swoich 3 znajomych poznala 4 nowe (wsrod pozostalych) - a wiec wychodziliby z 7 znajomymi. Tutaj juz nie dziala to co napisalem powyzej. Zaraz zastanowie sie jak to ugryzc
Skoro A zna E to E zna A
Wychodzi na to że E zna dokładnie 4 znajomych
EA EB EC ED.
Szymon -> zaczynając każdy miał 3 znajomych, kończąc miał 4 znajomych. Skąd Ci się bierze 7?
Normalnie masakra jakaś - to jest zadanie konkursowe dla I klasy gimnazjum a powiem szczerze, że wyłożyli się wszyscy w pracy u mnie :). Ciekawe gdzie jest kruczek :)
Okej, chyba juz mam.
Zalozmy, ze mamy grupke 4 znajomych - kazdy z osobna ma 3 znajomych w grupce, to jasne. Jest druga grupka, dokladnie taka sama. Wowczas mamy mozliwosc poznania 4 nowych osob. Dla ulatwienia beda to grupki A1,B1,C1,D1 oraz A2,B2,C2,D2
Teraz zalozmy hipotetycznie, ze do pierwszej grupki 4 znajomych dolacza jedna osoba - F1. Nie zna czworki A2,B2,C2,D2 - wiec moze poznac 4 osoby. Ale nie ma mozliwosci, zeby znala 3 osoby, bo w grupce A1,B1,C1,D1 wszyscy znajac sie nawzajem - znaja juz 3 osoby. Kiedy przyjdzie kolejna osoba - G1, mamy ten sam problem. Musi byc kolejna grupka, gdzie beda osoby F1,G1,H1,I1. Dopiero oni moga sie pomieszac z innymi grupkami, znajac poczatkowo tylko siebie nawzajem.
Tak wiec rozwiazanie - n e[4m], m>=2, m e N
"Na przyjęcie przyszło n osób. Początkowo każdy znał dokładnie 3 znajomych wśród pozostałych osób obecnych na przyjęciu. W trakcie przyjęcia niektóre osoby poznały się, w wyniku czego pod koniec przyjęcia każdy miał wśród pozostałych dokładnie 4 znajomych. Wyznacz wszystkie liczby n, dla których opisana sytuacja jest możliwa. (Przyjmujemy, że jeśli osoba A zna osobę B, to osoba B zna osobę A)".
Czyli każdy wychodząc z przyjęcia miał dokładnie 7 znajomych - 3 starych, 4 poznanych na przyjęciu.
Wg mnie n>=8
Szymon -> nadal nie jestem pewien czy to co podajesz jest ok.
Może ktoś to potwierdzi? Bo mi jednak nie do końca pasuje podane rozwiązanie.
K42a_ -> Na początku każdy miał dokładnie 3 znajomych, na końcu dokładnie 4 znajomych wśród pozostałych osób obecnych na przyjęciu.
Początkowo każdy znał dokładnie 3 znajomych wśród pozostałych osób obecnych na przyjęciu. W trakcie przyjęcia niektóre osoby poznały się, w wyniku czego pod koniec przyjęcia każdy miał wśród pozostałych dokładnie 4 znajomych.
Grupa n była określona od samego początku. Na przyjęciu zjawiło się np. 150 osób z których każdy znał tylko 3 osoby. Po wyjściu znał moim zdaniem jedną więcej, mając 4 znajomych. Nie jest napisane, że ktoś dochodził, że poznawał nowe osoby. Niektórzy poznawali nowe osoby.
Zagmatwane to dla mnie. A jeszcze mam to wyjaśnić 13-latkowi. Wypas.
Zle czytacie tresc. Przyjecie zaczelo sie gdy kazdy znal 3 osoby, a skonczylo sie, gdy kazdy znal 4 osoby. W zadaniu chodzi o znalezienie takich n, dla ktorych istnieja grafy 3-regularne i 4-regularne.
nagytow - nie wiem czy grafy o których wspominasz wchodzą w zakres gimnazjum. http://pl.wikipedia.org/wiki/Graf_regularny - jeżeli o to chodzi to powiem szczerze, że nie spotkałem tego w jego podręcznikach, a przynajmniej nie pod taką nazwą/postacią.
Zresztą pierwsza dziesiątka wyników dla zapytania graf regularny to już delikatnie mówiąc chyba wyższa matematyka :)
MiB -> przy zalozeniach, ktore poczynilem, mysle ze mam racje. A dokladnie dlatego bo:
Mamy n jako zbior wszystkich osob. Dzielimy go na zbiory 4 osobowe ("ja i moich 3 znajomych") i zbiory "pozostalych" (analogicznie w kazdym przypadku n-4). I to wlasnie ze zbioru "pozostalych" mamy miec owych 4 znajomych, a nie 4 znajomych w ogole.
A teraz widze jeszcze jedna sprzecznosc z moim rozwiazaniem. Musza dochodzic po dwie "czworki", bo w przeciwnym wypadku zrobia nam sie grupki z 5 nowymi znajomymi i wiecej (bo inaczej zasada nie bedzie zachowana) i owe czworki musza sie "parowac". Dlatego tez jeszcze raz modyfikuje rozwiazanie - n e [8m], m e N+ (zbior liczb naturalnych dodatnich)
Zrozumialem sens tak jak nagytow.
Zastanawia mnie jedno, skoro w trakcie przyjecia niektore osoby sie poznaly, to dlaczego pod koniec kazdy mial o jednego wiecej? :P
No wlasnie ja zrozumialem sens tak jak napisalem. Czyli mamy zbior n i dwa podzbiory - zbior X (czteroelementowy, gdzie jestem ja i moich 3 znajomych) i zbior Y (cala reszta osob na przyjeciu czyli n-4). I to wlasnie sposrod zbioru Y zdobywamy 4 znajomych
szymon-majewski -> z Twojego rozwiązania pasuje mi jedno i to rozumiem doskonale ;) czyli sam koniec, że n to "(zbior liczb naturalnych dodatnich)".
Dalej nie jestem pewien na 100% - ja jestem bliżej rozumienia tak jak nagytow. Dla mnie sens tego zadania jest w miarę jasny i zgadzam się z nim. Natomiast grafy regularne mnie rozkładają :)
edytuje -- moim zdaniem z tego drugiego zbioru zdobywasz tylko jednego znajomego :) żeby na końcu przyjęcia znać dokładnie 4 osoby :)
Jeszcze jedno - zanim syn poszedł do gimnazjum to wszędzie czytałem jaka ta gimbaza jest banalna i że dziś nic nie trzeba robić żeby zdać jak się trochę tylko uczy to się ma dobre oceny.
Założyłem, że będzie spokój jak w podstawowej gdzie spokojnie sobie dawałem rade ;p a tu taki zonk w pierwszej klasie :)
Hm... zapalilem i wszystko stalo sie jasne:P Zadanie jest prostsze niz wam sie wydaje
przy pieciu osobach na przyjeciu kazdy moze miec na poczatku 3 znajomych i na koncu 4
dziala to dowolnie wiekszej liczby gosci i dlatego "niektore osoby sie poznaly", bo przy szejsciu nie moga wszystkie sie poznac aby kazdy mial dokladnie 4 znajomych z tej grupy.
Czyli n=>5 zbiór liczb naturalnych
Tak mi sie wydaje przynajmniej
DUNCAN_83 - to napisałem na początku. Czyli znaczy to, że potwierdzasz moje rozumowanie ?
Duncan -> no wlasnie mi to nie pasuje. Jak masz 5 osob, to nie zrobisz tak, ze wszystkie osoby maja po 3 znajomych. Sprobuj sobie sparowac ABCDE - musi wyjsc tak, ze E zna albo tylko 2 osoby, albo 4 osoby, razem z jakas inna osoba
Sprawdź w jakim dziale podręcznika jest to kolejne jak się zdaje nieudolnie sformułowane zadanie z treścią. To cię naprowadzić powinno na właściwą interpretację.
to nie będzie coś z kombinatoryki?
AB, AC, AD
BA, BC, BD
CA, CB, CD
DA, DB, DC
EA, EB, EC
FA, FC, FE
Mogę tak w nieskończoność :) chyba da się tak przyjąć jak piszę.
MiB -> na serio nie widzisz co sie dzieje ?
"Przyjmujemy, że jeśli osoba A zna osobę B, to osoba B zna osobę A"
Skoro tak jest, to znaczy ze w twoim rozumowaniu A zna sie ze wszystkimi, bo zna B,C,D,E,F. Czyli juz 5 osob na wstepie. Nie chce byc niemily, ale zle rozumujesz
Her Pietrus -> pisałem wcześniej, że to zadanie konkursowe dla I klasy gimnazjum - etap szkolny :) (www.omg.edu.pl/uploads/attachments/1etap14.pdf) czyli najprostszy. Syn do tej pory dość dobrze sobie radzi na lidze zadaniowej i w innych konkursach ale tu poległ a ja z nim.
szymon_majewski - masz racje, bo musza miec na poczatku dokladnie 3 znajomych. Przy 8 sytuacja jest juz mozliwa bo kazdy z jednej czworki poznaje kogos z drugiej i sie zgadza.
I tak chyba dla kazdej kolejnej czworki
Czyli co dla n=>8 i podzielnego przez 4?
[Edit] glupi jestem , przeciez musi byc nastepna 8
czyli n=>8 i podzielnego przez 8... chyba:)
8,16,24,32...itd
[EDIT] [26] no wiem, glupio palnalem:)
MiB To zadanie jest z teorii grafow, przyjecia i znajomi to tylko otoczka. Poza tym z tego co sie orientuje, to zadanie pochodzi z jakiejs olimpiady czy konkursu matematycznego, wiec calkiem mozliwe, ze wychodzi nieco poza zakres. W kazdym razie skoro to gimnazjum, to na pewno istnieje jakis prosty sposob, ja go jednak nie znam. W pewnym momencie widzi sie tylko "duze" twierdzenia ;)
szymon_majewski 6 to najmniejsza liczba spelniajaca wymagania zadania.
Duncan -> nie dla kazdej czworki, bo zakladamy, ze poznawanie sie idzie w dwie strony. Kiedy dwie "czworki" sie poznaja nawzajem, to dla czworki "bez pary" nie ma z kim sie poznac. Dlatego musi to isc osemkami, jak napisalem, zeby kazda czworka miala swoja "pare".
Edit. dokladnie jak napisales. Czyli mamy konkluzje. Uff
nagytow -> 6 moglaby byc najmniejsza liczba, tylko jesli przyjmiemy rozwiazanie, ze maja miec 4 znajomych w ogole, a nie 4 dodatkowo
Tu nie ma co przyjmowac, tu wlasnie o to chodzi: bylo 3, jest 4. To jest matematyka, tu nie ma miejsca na swobodna interpretacje:
Początkowo każdy znał dokładnie 3 znajomych wśród pozostałych --> 3
pod koniec przyjęcia każdy miał wśród pozostałych dokładnie 4 znajomych. --> 4
szymon_majewski -> może źle rozumuje. Jest późno, jutro muszę iść do roboty i mam ciężki dzień za sobą. Nie przeczę. I nie chcę, żebyś był niemiły.
Nie neguję Twoich wyjaśnień, po prostu aktualnie tego nie rozumiem widocznie. Może muszę się przespać z tym, tym bardziej, że jest późno.
Okej, trudno mi to jasniej wytlumaczyc.
nagytow, dla mnie zadanie jest tak sformulowane, ze mozna rownie dobrze przyjac, ze jednak bylo 3 a potem 7. Juz pare bylo takich zadan, ktore robilem w zyciu i co gorsza sformulowane tak, ze zabierajac sie od drugiej strony tez mozna bylo je jakos sensownie rozwiazac. Moze i masz racje, wtedy to w ogole jest proste
ale maja mieć w ogóle, to jest chyab oczywiste, nawet ci wytłuścili
nagytow - możliwe, ale to chyba obecnie byłoby liceum i to o profilu matematyczno- fizycznym. Nie wiem czy to przeskok dobry na eliminacje szkolne dla pierwszej gimnazjum... W każdym razie jeśli maiłem w ogóle swego czasu w liceum (wątpię, że w gimnazjum) teorię grafów choćby w ułamku, to nic nie pamiętam. Jak patrzę na wiki, to nawet nie wiem, co by to mogło być - wyznaczenie takiej liczby wierzchołków dla której da się stworzyć graf 3- i 4-regularny?
jak potrzebny jakiś fachura-informatyk-prezes z GOL-a to akurat wszyscy spać wcześniej poszli :P
nagytow - pierwsze co zaczęliśmy robić to rysowanie grafu ale to nie takie proste.
szymon_majewski - ja też rozumuje jak nagytow i duncan_84 i Herr Pietrus, że zaczyna się z 3 znajomymi, kończy z 4. Nie z dodatkowymi czterema. Sens zadania jest raczej naprawdę jasny.
BTW - na konkurs to syn chyba sam powinien robić. czy nie zrobił i tak, tylko teraz po fakcie chcecie rozwikłać zagadkę? :)
To by bylo logiczne o tyle, ze to ma byc I klasa gimnazjum, nie moze byc za trudne zadanie mimo wszystko. Takze moze faktycznie zostanmy przy wersji z 6 osobami, to bedzie przynajmniej latwiej wyjasnic
BTW -> tak jak napisałem wcześniej - nie potrafi tego zrobić i poprosił mnie o wytłumaczenie. Niestety ja też nie potrafię tego wytłumaczyć, dlatego tak jak mój syn postanowiłem zapytać kogoś o większej wiedzy o wytłumaczenie. Tu jest duża społeczność, widuję tu osoby z różną, dużą wiedzą i dlatego pomyślałem, że warto spytać o poradę.
szymon_majewski: możesz w takim układzie wyjaśnić mi dlaczego 6 osób, dlaczego przy 6 będzie łatwiej i dlaczego końcówka zadania wspomina o "Wyznacz wszystkie liczby n, dla których opisana sytuacja jest możliwa".
Żeby nie było, że chcę być nieuczciwy i za syna rozwiązać zadanie to można to odłożyć do 16 grudnia kiedy termin odsyłania prac będzie zamknięty a ja pozostanę przy tym do czego doszedłem że n jest równe i większe 5 i to jako tako (może źle ale rozumiem).
Jak sie zastanowilem, to nie ma znaczenia czy 3 na wejsciu i 4 na wyjsciu, czy 7 na wyjsciu.
1. Na poczatku jest 4 (kazdy ma 3 znajomych)
Potrzebna jest kolejna 4 (aby kazdy mial na wejsciu tylko 3 znajomych)
1.1 Jesli kazdy z czworki pozna 1 osobe z drugiej czworki to kazdy bedzie mial 4 znajomych
1.2 Jasli kazdy z czworki pozna wszystkie osoby z drugiej czworki to kazdy bedzie mial 7 znajomych
Ta sytuacja powtaza sie co dwie czworki, czyli 8 osob
Czyli taki jak mowilem i poprawim mnie szymon
n=>8 dla liczb naturalnych podzielnych przez 8
Proszę usunąć zapytanie i nie publikować rozwiązań tego zadania!
Treść zadania stanowi własność intelektualną Stowarzyszenia na rzecz Edukacji Matematycznej, które nie wyraża zgody na publikowanie jej gdziekolwiek poza oficjalną stroną www.omg.edu.pl przed 15 grudnia 2014 r.
Zadania z Olimpiady Matematycznej Gimnazjalistów należy rozwiązywać samodzielnie! Warto zapoznać się z punktami X.2. i X.4. Regulaminu OMG: www.omg.edu.pl/uploads/attachments/regulamin.pdf
Hehe tak jak myslalem, to aktualna olimpiada :) http://www.omg.edu.pl/uploads/attachments/1etap14.pdf
Herr Pietrus wyznaczenie takiej liczby wierzchołków dla której da się stworzyć graf 3- i 4-regularny?
Dokladnie. Z tym, ze biorac pod uwage poziom gimnazjum, jest latwiejszy sposob niz sypanie twierdzeniami.
To raczej nie bot :) - drugi link w google jaki wklepałem po treści zadania to serwis z rozwiązaniami, skąd usunięto wpis - teraz jest 404 :)
Ale generalnie jeżeli rozwiązanie jest proste, wchodzące w skład nauczania matematyki w I kl gim. to nadal twierdzę, że dzisiejsze gimnazjum to nie bułka z masłem :)
nagytow -> Abstrahując od tematu. Nie wiem na jakim poziomie operujesz matematyką ale piszesz, że na pewnym poziomie zaawansowania nie patrzy się na proste rozwiązania.
Jak to się ma do zasady brzytwy Ockhama i dążenia do prostoty?
Pytam z czystej ciekawości i bez żadnego podtekstu :)
Zle mnie zrozumiales. W pewnym momencie "widzisz" tylko rozwiazania i schematy wymagajace wiedzy na jakims tam poziomie. Po prostu jak obracasz sie w kregu, nazwijmy to wyzszej matematyki (przynajmniej porownujac do gimnazjum), to bardzo czesto umykaja ci takie wlasnie bardzo proste sposoby. Dlatego niemal wszyscy wykladowcy czy instruktorzy, ktorych znam (nie tylko z uniwerkow) prowadza jakies zajecia z poczatkujacymi, wlasnie po to, aby nie uciekly im te "podstawy". Dziala to na tej samej zasadzie, na jakiej ty nie jestes w stanie sam pomoc synowi, po prostu nie masz juz do czynienia z tego typu zagadnieniami i zadaniami.
Sam widzisz jak to wyglada dzieje, ja rzucam teoria grafow, Aurelius podrzuca twierdzenie Ramseya. Im wyzej sie wspinasz, tym bardziej naturalne staja sie dla ciebie bardziej zaawansowane sposoby.
Przy okazji, nie mam juz za duzo wspolnego z matematyka, wszystko co pisalem pamietam jeszcze ze studiow :)
Okazuje się, że wyznaczenie wartości liczb Ramseya jest bardzo trudnym obliczeniowo zadaniem. Często mamy do dyspozycji bardzo dokładne ich oszacowania, a nie jesteśmy w stanie określić ich wartości, mimo że nie są to wielkie liczby. Poniżej dotychczasowe osiągnięcia w tej dziedzinie:
Gimnazjum, nie ma co :P
Jeśli faktycznie oto chodzi, to państwo od olimpiady albo wystawiają sobie niezłe świadectwo... albo chodziło o zadanie test - kto rozwiąże, wiadomo, że kombinował i korzystał z pomocy :P
nagytow - pytanie, czy zawsze istniej prostszy sposób :)
widuję tu osoby z różną, dużą wiedzą i dlatego pomyślałem, że warto spytać o poradę.
Dobry żarcik tak na początek dnia;)
Jak już wyżej było wspomniane - to jest zadanie z aktualnej OMG, zatem to nie jest poziom I gimnazjum, tylko gimnazjum ogólnie. I to raczej dla tych zdolniejszych uczniów. Nie ma nic dziwnego w tym, że zadanie przekracza poziom większości dorosłych :) To już nie przedszkole. Owszem - powinno się je dać rozwiązać prostymi metodami bez znajomości kosmicznych twierdzeń grafowych, bo i zadania z Olimpiady Matematycznej dla szkół średnich w większości da się rozwiązać metodami "z podstawówki/gimnazjum", co nie oznacza, że są one trywialne. Nie będę Ci zbyt podpowiadał co by nie łamać regulaminu. Ale w ramach lekkiego naprowadzenia: zastanów się ile w takim "grafie znajomości" (zarówno przed jak i po zawarciu nowych znajomości) będzie wierzchołków (jakieś n), a ile krawędzi (w zależności od liczby wierzchołków!) i co z tego wynika
jason900627 -> To nie żart. Jestem na tym forum zarejestrowany dość długo i czytałem tu wiele ciekawych wątków z których można było dużo wynieść.
Stare wątki o militariach, gdzie było wielu pasjonatów znających się na historii (vide stare CMHQ), można przytoczyć wątek o wklęsłej ziemi gdzie również było kilka osób z odpowiednią wiedzą i zapałem do tłumaczenia trudniejszych spraw.
Jak się zrobi odpowiedni przesiew informacji to wbrew pozorom jest tu całkiem dużo wiedzy z naprawdę wielu dziedzin. Wcale bym się tak nie śmiał.
Dexiu -> rozrysowałem to sobie, doszedłem do pewnych wniosków, pokrywających się w dużej mierze z tym co tłumaczyli poprzednicy. Ale racje mają organizatorzy i na razie się wstrzymam jeżeli chodzi o moje przemyślenia/obliczenia :)
Po 16 grudnia postaram się odświeżyć wątek.
To jest zadanie na olimpiadę matematyczną, synek mógłby się wykazać, a nie pracę robi za niego ojciec. Pozdrawiam
