Matek házinál segítség?

Hát annyi ideje kint van hogy beírom a választ az elsőre főleg mert fogalmam sincs hogy lehetne rávezetni. Teljes indukció, négyre nyilvánvalóan igaz.

Hát nevezzük az ürgét az első N-ből aki mindenkit ismer (ez az indukciós feltétel) mondjuk A-nak, az N+1-et B-nek. Ha A ismeri B-t, kész. Ha nem, akkor vegyünk egy tetszőleges négyest ezzel a két ürgével, A,B,C,D hát ki lehet ebben a bandában aki ismer mindenkit? C vagy D hiszen A és B nem ismeri egymást. De akár C akár D, Mindenképpen C és D ismeri egymást. Ebből következik hogy A és B kívül minden pár ember ismeri egymást. Hát akkor vegyünk egy konkrét ilyen párost, valamelyikük közülük ismeri A-t és B-t is -- és mindenki mást is. Tehát ha ezen közösségi oldalon egy új ember beregisztrál akkor azt vagy az ismeri az aki eddig is a társaság közepe volt vagy ha nem akkor ez eddigi tagok közül mindenki ismer mindenkit és a társaság közepén kívül max egy kivételével az új embert is ismeri mindenki. Ez már csak ilyen :)

Itt van egy még jobb eredmény indukció nélkül: mi van ha van egy ember aki nem ismer egy másikat?

Vegyük ezt a párost, A-t és B-t, és mint az előbb, vegyünk egy tetszőleges párost hozzájuk. Ez a páros ismeri egymást. Tehát A-n és B-n kívül mindenki ismeri egymást. És minden ilyen párosból lesz egy a kezdeti feltétel szerint aki ismeri A-t és B-t is.

Másképpen szólva: nézzük az idegeneket. A feltétel szerint nem találsz két pár idegent. Ha találtál három embert akik nem ismerik egymást akkor ott több idegen már nem lehet -- ha rajtuk kívül van egy idegen páros, az az előző észrevétel szerint bukik. Ha van egy negyedik aki nem ismer valakit ebből a háromból, akkor az megint csak az eredeti feltételt bukja. Tehát az összes lehetséges idegen eset mindössze ez: van két ember akik nem ismerik egymást, van egy ember aki nem ismer másik kettőt és van három akik egymásnak teljesen idegenek. Rajtuk kívül mindenki ismer mindenkit.