A village of pick pockets!

Question

There is a small village of 100 people. An unknown number of these villagers are pick pockets. Each day, you're allowed to take as many villagers as you wish out of the village. When a pick pocket has been taken out, he will not pick any pockets.

Each day, pick pockets still in the village will pick one pocket.

Each night, people will report if and how many times they were victim to pick pocketing.

Pick pockets do not know who each other are, so they may pick pocket each other. They will also still report if they are victim.

You have to successfully find who are the pick pockets. My question is if there's an optimal solution to this problem, and if there is, what's the worst case scenario?

Answer 1

$41$ days suffice.

Compare this question. In some sense, it is almost the same question, but with 12 instead of 100. There is a hidden subset $S$ of $[100]:=\{1, 2, \dots, 100\}$, and every time you query a subset $T\subseteq [100]$, you discover $|T \cap S|$. You want to minimize the number of queries.

One answer on the linked question cites a paper called "Determination of a subset from certain combinatorial properties," of which one result is that you can solve $2^{k-1}k$ people in $2^k-1$ queries. Thus, you can solve 80 people in 31 queries.

There's one catch. In this question, you presumably can't query a subset of size 1, because no self-respecting pickpocket will pickpocket themselves. But as Joffan points out in the comments, using Mohit's method, you can query one person by pairing them with any other person.

There are 20 people left. Using Mohit Jain's clever pairing strategy, you can solve them all in 10 queries. So the final tally is 31+10=41.

Answer 2

My solution yield result in

50 days (Both in best and worst case)

And here is the approach

Make groups of 2. Leave first group in village on first night, second group on second night and so on and keep a count of pickpockets in that group.
If both are pick-pocketed, both are accused. If both aren't victim, none of them is accused. If person 1 is reported victim once, person 2 is accused and vice versa.
After 50 days you have the list of all pick-pocketers

Answer 3

Here is what I think the optimal solution would be (assuming the goal is to isolate the pickpockets and that you can label people as pickpocket minesweeper flag style):

The first day, have two people in the town. If the count is 0 or 2 after that, label the two as either not pickpockets or pickpockets, respectively. If the count is 1, replace one of the people and wait another day. If the count is still 1, replace the same person and wait another day. Keep going like this and when you finally get a count of 0 or 2, you will know what everyone tested is. This will take $x-1$ days for $x$ people tested. This method will guarantee a solution in between 50 days and 100 days depending on how many groups of 2 pickpockets/non-pickpockets you get. Worst case scenario example is having one pickpocket and one non-pickpocket and replacing the non-pickpocket with a non-pickpocket 98 times before comparing two of the non-pickpockets. Best case scenario example is comparing pairs of non-pickpockets or pickpockets each time.

Potential shorter number of expected days method:

Day 1:

Wait one day to know how many total pickpockets there are

Day 2:

Take out 50 people

Day 3:

From the result of day two, you know how many pickpockets are in each group by subtracting the amount of pickpockets in the 50 remaining from the total. Whichever group had less put half (25) back in the town. Keep track of the 25 staying out of the town.

Day 4:

You can calculate the number of pickpockets in each group of 25 using the logic in day 3. Now, put 25 of the original 50 back in (with the larger amount of pickpockets). Keep track of the 25 staying out of the town like previously.

Day 5 and on:

At this point, you should know the number of pickpockets in each of the four 25 people groups. Extend this logic to find out the number of pickpockets in the 8 groups of 12(4)/13(4) people. Then extend this to find the number of pickpockets in the 16 groups of 6/7(4). Then, extend this to find the number of pickpockets in the 32 groups of 3/4(4). Then extend this to find the number of pickpockets in the 64 groups of 1/2(36). Test the remaining 36 groups of 2 with known values.

From this logic,

Each extension will take the number of groups. For any groups along the way, if the entire group is pickpockets or not pickpockets you'll know and can take it out of the future tests.

Worst case scenario,

If none of the groups are full of pickpockets/non-pickpockets in the groups, that's 160 days worst case, but this number can be dramatically reduced if groups can be taken out early. I may be a bit off in my numbers so I'll be double checking but this should be in the ballpark.

Answer 4

Since "optimal" is undefined I suggest the following solution:

Take one day to count pickpockets. Then take one person out of the village per day. Worst case: after you have taken each person (except one) out of the village, you know who all the pickpockets are. Time: 100 days. Cost: 99 hotel days