Find multiple dishonest people

Question

Recently I travelled far distance by train and a stranger told me this riddle but I never got the answer:

100 years ago, when far distance travelling was something special, a traveller came back from far countries to his town. He was in 16 different countries and from each country he brought back 4 treasures. He hid each treasure in a different secret location. As those were gorgeous he wanted to show them to the people in the town who were all 512 honest people. At least he thought so. He heared the rumor that 4 people were not that honest and will steal the gorgeous treasures to get them for themself in the next month after the treasures were shown to all. But this wouldnt stop him from showing the culture of the far countries to the people. Each person will be shown 1 treasure of each country but he can choice which of the 4 treasures of each country to show whom. The honest people would never tell anybody else the location of the treasures they know but also accusing a honest person of stealing is also out of question.

Can he identify the dishonest people after the month and how? What is the minimum amount of treasures per country/maximum count of dishonest/honest people? Is there a formula/strategy?

My approach was: Show each person a unique combination of treasures and find the dishonest one according to the combination. But it only works for a single dishonest person.

Clarification:

1. He hides the treasures
2. He tells the people locations
3. 4 people steal every treasure they know
4. He notices the theft

He only see what they stole together, not what each individual stole.

After some research I found the minimum number of possible combinations of stolen treasures. I put it in spoiler in case someone wants to solve it on their own.

Number of combintations:

$$\binom{512}{4}=\frac {512!}{4!*(512-4)!}=2,829,877,120$$
(See https://en.wikipedia.org/wiki/Combination)

Also I solved it by bruteforce for 4 people, 2 dishonest people, 3 countries, 2 treasures per country:

1 1 1 1 1 2 1 2 1 2 1 1 where the number tells us if we show the treasure 1 or 2 to a person and each line is for a different person and each row is for a country. The possible outcomings are: 1 1 3 1 3 1 1 3 3 3 1 1 3 1 3 3 3 1 Each cell is the sum of the numbers of the stolen treasures in a country. We have a population of 4. We get 6 combination from this which also supports my found formula. $$\binom{4}{2}=\frac {4!}{2!*(4-2)!}=6$$

Answer 1

Let's come at it from extremes. If you show every treasure to every person, all your treasures will be stolen and you will learn nothing about who the thieves are. If you show each treasure to only one person, over 400 villagers will not see a treasure. If the thieves are in the 64 people who see your treasures, you'll know who they are, but if at least one thief isn't in that group, you don't have your information.

If you show each treasure to 8 people, everyone will get to see one treasure. But if a given treasure is stolen, you don't know which of the 8 people stole it. The only way to learn that is to show each person more than one treasure. If there is only one thief, you need to just make unique pairs - sure, 8 people saw treasure 1 from country A, and 8 people saw treasure 2 from country B, but only one person saw both A1 and B2, so that is the thief. The number of combinations is 64 choose 2, so 64*63/2 or 2016, so showing two items per person would be fine with only one thief.

Once you have multiple thieves, it gets a lot harder. If A1, B2, C3, and D4 go missing, and each person saw 2 treasures, are your two thieves A1B2 and C3D4 or A1D4 and B2C3? To overcome this, you need to use less of your combinations to eliminate these overlaps and that means you're going to need to show more items to each person.

With four thieves, more things will go missing - up to 8 if you show each person two items, up to 12 if you show each person three items, and so on. The question statement wants you to show each person 16 items. That means a LOT of items will be stolen. If you use some sort of symmetric assignment of who sees what, some of your 16 countries will have one item seen by each thief, so you'll lose all 4, some will have one item seen by all four thieves, so you'll just lose that 1, and the rest will have two or three thieves see the same thing so you'll lose between 1 and 4. You'll have a total of dozens of items stolen. Trying to split that up into clumps that you can say "this 16 was from person 27, and this 16 was from person 178" is going to be impossible.

I mean literally impossible. After you've shown 1 country, 128 people have seen each item. After country 2, 32 people have seen each combination. After country three, 8 people have seen each combination. After country four, 2 people. No matter how you deal out country 5, some people will have seen the same things. And even if they haven't, you will have the same A1B2 and C3D4 or A1D4 and B2C3 problem, because you used all your combinations. The only way to use sparser combinations would be if some people didn't see anything from country A, and some didn't see any from country B, and so on.

So some part of the puzzle has to give. Either you don't show everyone one item from each country, or you don't do all the showing followed by all the stealing. I think it's relatively easy if you show, wait, rule out certain people (item 3 didn't get stolen so the 128 people I showed it to are honest) and continue on like that. Some nights only one thing would be stolen, some nights 4 things, but you could work out who the thieves were eventually by making the combinations based on who is still under suspicion. But if the puzzle is posed as written, I say there is no solution.

Answer 2

This solution is to approach this problem with a divide-and-conquer strategy. You are right about the unique key. What mainly gives this away is the fact that all numbers we're given are powers of 2.

The idea is to divide the original 512 people into groups of even and odd people. This will leave two groups of 256 people, each of which has seen a unique treasure. This process will be repeated until the 8th break, in which we have a single person seeing a unique item.

Note however that since each person will be seeing a treasure from a country, each of the 8 times we divide, we are showing a single country's treasure to that group of people, but each split will be seeing a different box. So the first 256, for example, will be seeing country 1, box 1; the second 256 will be seeing country 1, treasure 2. This will continue per layer until we reach the 9th country. At this point we start back at the top, 512. We continue: even 256 country 9, treasure 1, etc.

At this point each person has seen a treasure from every country. We have made two sweeps through the 512 people; once breaking them in half for the first eight countries, then the remaining 8 countries.

Notice how each person will see a unique sequence of the 64 total treasures when we break it down this way. Ergo, even if you are only presented with the stolen goods of all 4 people (not each individual thief), you know that there will be 4 unique items to each of the 4 thieves.

How can we be sure this works? Each point in the tree that this forms will be identified by a unique code, say "c1t1" denoting country and treasure. There will only be 256 people with "c1t1" and only 128 with "c2t2". There will be no one with "c2t3" with "c1t1". This allows us to identify the culprits by identifying the only logical course through our tree.

Using your above example (the one you solved with brute force) with this strategy:

  2 people see country 1, object 1 (AB). //ABCD are the 4 townspeople 
  2 people see country 1, object 2 (CD).
  1 person sees country 2, object 1 (A).
  1 person sees country 2, object 2 (B).
  1 person sees country 3, object 1 (C).
  1 person sees country 3, object 2 (D).

Suppose we now have 2 thieves (dishonest people). If object 1, country 3 is missing and object 2 country 1 is missing, we know who the culprits are immediately. Notice that once a unique item of this kind is missing (and our assumption is the thieves steal unique items), then we know who they are.