MathDB

Several policemen try to catch a thief who has

2m

accomplices. To that end they place the accomplices under surveillance. In the beginning, the policemen shadow nobody. Every morning each policeman places under his surveillance one of the accomplices. Every evening the thief stops trusting one of his accomplices The thief is caught if by the

m

-th evening some policeman shadows exactly those

m

accomplices who are still trusted by the thief. Prove that to guarantee the capture of the thief at least

2^m

policemen are needed.

Problem Statement