I. megoldás. Elég azt bizonyítani, hogy van a társaságban 16 ember úgy, hogy közülük bármely kettő ismeri egymást. Ekkor ugyanis közülük valakinek ismernie kell a fennmaradó $15$ résztvevő mindegyikét; a társaságnak ez a tagja tehát mindenkit ismer.
Ennek igazolásához pedig $n$ szerinti indukcióval azt bizonyítjuk, hogy minden $2\le n\le 16$ esetén van a társaságban $n$ ember úgy, hogy közülük bármely kettő ismeri egymást. Ez $n=2$ esetén nyilvánvaló, ha pedig $2\le n<16$ esetén már tudjuk, hogy van a társaságban $n$ megfelelő ember, akkor őket további $15-n$ résztvevővel kiegészítve, van a társaságban valaki, aki mind a 15-öt ismeri. A szóban forgó $n$ résztvevővel együtt ez $n+1$ ember, akik közül bármely kettő ismeri egymást.