Uganka

Vas ima 1000 prebivalcev. Vemo, da vsak pove novico vsem svojim znancem v enem dnevu. Koliko ljudi najmanj moramo izbrati v tej vasi, da jim sporočimo novico, če jo morajo v 10-ih dneh izvedeti prav vsi vaščani, vemo pa le, da se vsaka novica razširi na vse vaščane?

Opomba. Naš algoritem za izbiro `glasnikov' dobi kot vhod, kdo je s kom znanec, nima pa kontrole nad strukturo teh poznanstev (tj. delovati mora v vsaki taki vasi).