4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Can pickpockets pickpocket other pickpocketers and will pickpockets report pickpocketing of their own pockets? pickpocket $\endgroup$ – Quark Jan 22 '15 at 3:14
  • $\begingroup$ @Quark I almost laughed at that. Anybody will report if they are pickpocketed. $\endgroup$ – warspyking Jan 22 '15 at 3:36
  • 2
    $\begingroup$ What's the goal? To find out who are the pickpockets? $\endgroup$ – xnor Jan 22 '15 at 3:46
  • 6
    $\begingroup$ @xnor actually it's a trick question; the goal is to get into the spaghetti party by picking the guards pocket without getting your own pocket picked. $\endgroup$ – Michael Jan 22 '15 at 4:30
  • 4
    $\begingroup$ If there is only one pickpocket left in the village, will he pick his own pocket? And report it? $\endgroup$ – Florian F Jan 22 '15 at 11:44
7
$\begingroup$

$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.

$\endgroup$
  • 1
    $\begingroup$ Actually, you can query a subset of size 1. You just need to use Mohit's method and put one other random person in the village with the person being queried. So I guess your solution improves to 41 days. $\endgroup$ – Joffan Jan 23 '15 at 17:24
  • $\begingroup$ @Joffan Edited. That's clever! $\endgroup$ – Lopsy Jan 23 '15 at 21:39
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I agree with your solution if the pickpocket report isn't anonymous. $\endgroup$ – Quark Jan 22 '15 at 5:29
  • $\begingroup$ @Quark Thanks. I drew my inference from Each day, pick pockets still in the village will pick one pocket and Each night, people will report if and how many times they were victim to pick pocketing $\endgroup$ – Mohit Jain Jan 22 '15 at 5:30
  • $\begingroup$ Yeah I saw that line and originally thought that although it isn't strictly specified (the people can still report quantity anonymously). If the report isn't anonymous, the question is trivial and there is no cases or optimization which is why I made that assumption. $\endgroup$ – Quark Jan 22 '15 at 6:05
  • $\begingroup$ @anonymous_downvoter Any reason to downvote the answer? $\endgroup$ – Mohit Jain Jan 22 '15 at 9:44
  • $\begingroup$ I agree with your answer. Anonymity doesn't play a role in case of 2 people unless the pickpocket is allowed to pickpocket himself (and report that) which I think could be ruled out by common sense. I also think one can not get down below 50 in the general (or worst) case. $\endgroup$ – BmyGuest Jan 22 '15 at 10:34
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you get short than 100 worst case (with another method)? $\endgroup$ – warspyking Jan 22 '15 at 9:29
  • $\begingroup$ Your worst-case scenario is 100 days, like practically any well-designed scheme based just on counting pickpockets in reduced populations. $\endgroup$ – Joffan Jan 23 '15 at 14:28
  • $\begingroup$ This scheme was from the assumption that all pickpocket counts are anonymous. $\endgroup$ – Quark Jan 23 '15 at 14:34
  • $\begingroup$ Yes, that's what I was assuming also. 1+1+2+4+8+16+32+36=100. $\endgroup$ – Joffan Jan 23 '15 at 17:26
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @mystery_downvoter - don't be shy, tell me why! $\endgroup$ – Joffan Jan 23 '15 at 3:22
  • $\begingroup$ (not downvoter but:) This answer would be better as a comment. You know as well as I do what we're trying to optimize. $\endgroup$ – Lopsy Jan 23 '15 at 8:54
  • $\begingroup$ @Lopsy Thanks for the response, but I disagree. I know what the answers so far have tried to optimize. Looking for options in the puzzle wording is part of the fun of puzzles. $\endgroup$ – Joffan Jan 23 '15 at 14:24
  • $\begingroup$ Normally I oppose bending the rules, but this is a fairly valid answer. $\endgroup$ – dmg Jan 24 '15 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.