psychodom wrote:Assuming in our motley office we can identify a scrupulous individual, how about:
1) everyone writes their name on a piece of paper and on an envelope, then folds the paper and puts it into an envelope
2) a trusted individual thoroughly shuffles all the envelopes with the name-side-down
3) once shuffled our trusted individual lines up the envelopes (still name-side-down) and takes each slip of paper and places it in the next envelope)
4) envelopes are then returned to each individual with their name on
Very neat, and it solves my more difficult problem as well apart from the limitation jfgw mentioned, that each person knows the person they gave a present to didn't give one to them. So probably the solution jfgw was thinking of, or equivalent to it.
And I think it can be made more secure against accidents, unscrupulousness, etc, by making step 1 a bit more complex: everyone is given two small envelopes of different colours (say white and brown), a label with their name on it and a slip of paper with their name on it, and a bigger envelope. They're told to verify that that's what they've got, seal the slip of paper in the small white envelope and the label in the small brown envelope, put both small envelopes in the larger envelope, and close (but not seal) the larger envelope.
Steps 2 and 3 are more-or-less the same, apart from shifting the sealed white envelopes rather than slips of paper. As a result they can be done in full view of everyone and so don't rely as much on having a trusted individual - not total non-reliance, but it would basically require the individual who does the shuffling and shifting to be an accomplished stage magician to frustrate it, not just unscrupulous.
Then shuffle the envelopes thoroughly again and go through them one by one. For each, take the two smaller envelopes it contains out of it, open the brown one and affix the label it contains to the white one, again in full view of everyone. Everybody then takes the white envelope labelled with their name away to open and read the slip of paper it contains at their leisure.
Furthermore, a slight modification produces a full solution to my more difficult problem if there are 5 or more people in the office: for step 3, arrange the envelopes as a top row of two envelopes and a bottom row of more than two envelopes. Swap the small white envelopes between the two top-row envelopes, and in the bottom row transfer each small white envelope to the next envelope, wrapping around from the last to the first. The rest of the procedure is unchanged, and in the end no-one can logically exclude anyone else from being the person who gave them their present.
Like the original problem, my more difficult one is insoluble for 3 people or fewer, so that just leaves my more difficult problem for 4 people. And that's solvable by a not-too-brute-force solution: of the 24 possible permutations of four people, just 9 don't have someone giving a present to themselves. In full sight of everyone, prepare 9 sealed big envelopes, one for each of those 9 permutations. Each contains four small envelopes, each one labelled with one person's name, filled with a slip of paper naming another in accordance with the permutation, and sealed. Thoroughly shuffle those nine big envelopes and draw one. Open it, hand each small envelope to the person it's labelled with, and thoroughly destroy the remaining big envelopes without opening them (the office shredder will probably come in handy!). Each person then takes their envelope away to open and read at their leisure.
One final afterthought: rather than slips of paper, use adhesive gift labels and tell people to affix them to the gifts to indicate who they are for, without adding any other message. Provided that instruction is adhered to, it prevents any gift-giver inadvertently (or deliberately?!) giving themselves away by handwriting, writing style, etc!
Gengulphus