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:
- He hides the treasures
- He tells the people locations
- 4 people steal every treasure they know
- 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$$