Az F. 2255 feladathoz fűzött megjegyzésben megemlítettük, hogy Ruzsa Imre igazolta, hogy a feladat feltételei mellett annak eldöntésére, hogy ki hová való, legalább $5N/4$ kérdésre szükség van. Később Fred Galvin bizonyította, hogy általában $4N/3$ kérdésnél kevesebb sem elegendő, végül a cikk szerzője, P. Blecher mutatta meg, hogy a fentebb ismertetett megoldásban a kérdések száma már nem csökkenthető tovább; kevesebb kérdéssel, akárhogyan is teszi fel azokat a feladattal megbízott matematikus, nem mindig tud célhoz jutni. Pontosabban, a tudósok megismeréséhez legalább $q=3k+1$ kérdés szükséges, ha $N=2k+2$, páros szám, és legalább $q=3k$ kérdés, ha $N=2k+1$, páratlan szám.
E két állítás közül elegendő csak az elsőt igazolnunk. Valóban, tegyük fel, hogy $N=2k+1$ tudóst legfeljebb $q<3k$ kérdéssel meg tudunk ismerni. Ha a konferencián $2k+2$ tudós vesz részt, akkor bármely tudóst elhagyva, a megmaradt $2k+1$ tudós többsége is piripócsi lesz. Róluk a feltevésünk szerint $q$ kérdéssel megtudhatjuk, ki honnan jött. Ezután a $2k+1$ tudós közül egy piripócsitól megkérdezzük, hogy a kihagyott $2k+2$-edik tudós honnan jött. Így a $2k+2$ tudós szülőhelyét legfeljebb $q+1<3k+1$ kérdéssel tisztázhatjuk. Ez viszont ellentmond annak, hogy $2k+2$ tudós megismeréséhez legalább $3k+1$ kérdést kell feltennünk.
Képzeljük most el, hogy az $A$ matematikus azt állítja, hogy ő tud egy olyan eljárást, amely $N=2k+2$ tudós esetén $q<3k+1$ kérdéssel eldönti, hogy ki hol született. $B$ nem hiszi, hogy ez az eljárás jó, és meg akarja mutatni $A$-nak, hogy tévedett. Hogyan fogjon hozzá? $A$-nak az az érdeke, hogy a tudósokat minél hamarább megismerje, $B$ viszont azt akarja, hogy $A$-nak ez ne sikerüljön. $A$ azt állítja, hogy mindig el tudja érni a célját, s így el kell fogadnia $B$ következő ajánlatát:
,,Állítsuk sorba az $N=2k+2$ tudóst. Ha a sorban az $i$-edik tudóst akarod megkérdezni arról, hogy a $j$-edik honnan jött, akkor ezt tőlem kérdezed meg, és én fogok válaszolni az $i$-edik tudós helyett. Összesen legfeljebb $3k$ kérdést tehetsz fel, és azt állítom, hogy válaszaim alapján legalább egy tudósról nem tudod eldönteni, hogy honnan jött. Vagyis lesz olyan tudós, hogy vele együtt legfeljebb $k$ nekeresdi vesz részt a kongresszuson, és az a tudós akár piripócsi, akár nekeresdi, a piripócsiak által adott válaszok mindig igazak lesznek.''
Miután $A$ elfogadta $B$-nek ezt, az ajánlatát, lássuk, $B$ hogyan válaszol $A$ kérdéseire. $B$ először is lerajzol $N$ pontot, $P_1\mathrm{,}{P}_2\mathrm{,}\text{...}\mathrm{,}{P}_N$-et. Azután $A$ első $k-1$ kérdésére mindig azt feleli, hogy ,,nekeresdi'', továbbá ha $A$ az $i$-edik tudást kérdezte a $j$-edikről, akkor a $P_i$ és a $P_j$ pontokat egy (másik ponton át nem menő) vonallal ‐ éllel ‐ összeköti. Ezzel a $k-1$ kérdés után egy gráfot kap, melyben $P_1\mathrm{,}{P}_2\mathrm{,}\text{...}\mathrm{,}{P}_N$ a csúcspontok, és melyben összesen $k-1$ él van. Jelöljük $H$-val azoknak a csúcspontoknak a halmazát, melyekből nem indul (és melyekbe nem érkezik) él. A többi csúcsot szétosztjuk a $G_1\mathrm{,}{G}_2\mathrm{,}\text{...}\mathrm{,}{G}_s$ részbe úgy, hogy ha $i\ne j$, akkor $G_i$-beli és $G_j$-beli csúcs között nem fut él, de egy $G_i$-n belül bármely csúcsból bármely csúcsba a behúzott élek mentén el lehet jutni. (A $G_1\mathrm{,}{G}_2\mathrm{,}\text{...}\mathrm{,}{G}_s$ gráfokat a nagy gráf komponenseinek nevezzük.)
Legyen a $G_i$ részhalmazban $c_i$ csúcs, és $e_i$ él. Mivel $G_i$-ben bármelyik csúcsból bármelyikbe el kell tudnunk jutni, azért $c_i\le e_i+1$; s mivel az egész gráfban összesen $k-1$ él van, azért