The Skeptic Santa Problem

This Saturday is the Merseyside Skeptics Christmas Party (at the View Two Gallery on Mathew Street from 7pm, everyone is welcome).  And as part of that event, we’re planning our own version of the Secret Santa game that some of you may be familiar with.

This is how it works: each person who wants to play the game brings a gift, to no more than £5 value.  Each gift is exchanged for a raffle ticket.  At the end of the night, raffle tickets are drawn and people are awarded their gifts.  You must have a ticket to get a gift, so you only get a gift if you gave a gift.

Lovely. Though there are a couple of problems.

First, we don’t want people getting their own gift back.  It’s not particularly nice, and for less than a £5 value, it’s probably some piece of gift-wrapped tat anyway. You brought it to the party because you wanted to get shot of it, you don’t want it back.  So that’s problem number one.  Problem number two: we don’t want people to be able to game the system.  By that we mean, we don’t want people to be able to engineer things so they can guarantee  their gift goes to a particular person, or a particular person’s gift goes to them.  It has to be fair.

We have come up with a few solutions to this problem. Some mathematical, some empirical, some just plain daft.  Most of them are flawed in some way, but we think we have one which works.

What solutions can you come up with?  We’ll publish ours after the party.

  1. #1 by Jason Jones on December 13, 2013 - 13:29

    Not to difficult, say there are 100 people participating, have 2 sets of number 1-50 and 51-100

    when the person drops of the gift he/she/it draws a number out of the 1-50 pile, thats its number for the draw, then someone else draws a number from the 51-100 pile and that goes on the gift….but this should be done out of site of the person so they dont know what number is on their gift, after the first 50 numbers have gone, reverse the piles and keep going.

    This is simple if you know how many people will be taking part

    If you dont know how many people will be taking part, take a chance that the gods will randomise the draw enough for you

  2. #2 by Mike on December 13, 2013 - 13:39

    Won’t that solution break when there are an odd number of people turning up to the party?

    So, say for example there are only three people turning up.

    You have two piles of tickets, 1-2, and 3. The first person comes in, they draw ticket 1, and their gift is marked ticket 3. The second person comes in, and they draw ticket 2, and their gift… has nothing to be marked up with?

    (Plus, we don’t know how many people will turn up, never mind how many turn up with gifts)

  3. #3 by Jason Jones on December 13, 2013 - 13:39

    or, use a spreadsheet and some numbers, first column in number order.. 1-whatever, next column put the persons phone number, 3rd column the pone number again. Then sort third column ascending (or whatever), this should randomise, then use function to check if col 2 and 3 are the same, if they are separate and shift them all down 1 spot

    so simple

  4. #4 by Howard on December 13, 2013 - 14:21

    My first thought was to split the tickets into 2 piles, red and green. You get issued a ticket that’s a different colour to the one your gift is assigned; thus you can’t possibly pick your own gift. But like Jason’s first attempt, that breaks if there is an odd number of people.

    There must be a more elegant way to solve it than using an excel function and sorting columns. It’s not very efficient; if you forget about excel and actually wrote down the steps there’s a heck of a lot of work going on there. Performing a sort is quite a complex task when you break it down.

    I think the best solution will be one that minimises the amount of work required. I mean you could search through the pile before each draw and remove the drawer’s gift ticket from the pool of available tickets – it works but it’s not a very good solution.

    For me the fun part is finding a solution that works, and is elegant.

  5. #5 by Joe Thompson on December 13, 2013 - 14:55

    It’s not mentioned that the person who gave each gift needs to remain a secret, so if that isn’t a requirement, a good solution is this:

    Each gift giver is given a number that both matches them and their gift. This doesn’t have to be random, it can simply start from 1 and increment from there. For the drawing, if you draw ticket A, then draw ticket B, person B will take gift A. C will take gift B, etc. Person A will take the last remaining gift. This way ensures that there is no possibility that someone will get their own gift, no possibility to game the system, and will work with all sample sizes larger than 1.

    If it’s a requirement that only whoever gave the gift knows which theirs is then I don’t think a perfect solution exists. It could all be worked out beforehand by someone who knows who each gift came from, but given that you want a drawing I don’t think it would be possible to design a solution with perfect secrecy, matching the other requirements.

  6. #6 by Mike on December 13, 2013 - 14:59

    I think there is a way to game that, Joe. I make sure that my wife and I arrive at the same time, so I am C and she is D and so she gets my gift C.

  7. #7 by Joe Thompson on December 13, 2013 - 15:01

    You can be 3 and she can be 4, but C and D will be whichever ticket is drawn out of the hat 3rd and 4th, which could be 8 and 14 or whatever.

  8. #8 by Mike on December 13, 2013 - 15:06

    I don’t think I’m following the solution then?

  9. #9 by Joe Thompson on December 13, 2013 - 15:11

    Say you have 5 people, and the tickets are drawn out of the hat in the following order:
    4, 2, 3, 1, 5

    Gift 4 goes to person 2, gift 2 goes to person 3, gift 3 goes to person 1, gift 1 goes to person 5, and gift 5 goes to person 4! You can imagine it by randomly placing the gifts in a circle and everyone taking the gift to their own gift’s left. The key is that the random permuting of the gifts cannot be gamed, and that by taking adjacent gifts to their own, no-one can be left with their own gift.

  10. #10 by Mike on December 13, 2013 - 15:39

    Ahhh, I see. I like it 🙂

  11. #11 by claire on December 13, 2013 - 15:39

    I have come up with another solution by misunderstanding Joe’s solution.

    Person 1 comes up and pulls a ticket out of the hat and pulls out person 3’s gift. After that person 3 comes up and pulls a ticket out of the hat and pulls out person 2’s gift. Then person 2 pulls a number out of the hat etc. until all the numbers are gone and all the gifts are taken.

    With the exception of the first person, whenever a person comes up to pull a number out of the hat their number wont be there so cannot get their own gift and works with any number of participants.

    To solve the first person problem you could order the name pulling by having the last person to arrive not put their number in the hat, pull out the first number and after getting a gift their number goes in the hat

  12. #12 by claire on December 13, 2013 - 16:15

    Flaw in that plan – if the last person to come in, lets say person F, choose person A’s number, then person A chooses person F’s number the whole system grinds to a halt.

    You’d have to leave out their number and just have them take the gift that’s left.

  13. #13 by Jason Jones on December 13, 2013 - 18:09

    May have an easy solution, lets say there are 9 people, each get a number and then you select a random number somewhere around the mid point, say 5, add this to the original number to get the number of the gift, so it may look like

    1 6
    2 7
    3 8
    4 9
    5 1
    6 2
    7 3
    8 4
    9 5

    this should work with any amount of people, and the larger the group the lager the separation from the person to the gift

  14. #14 by Mike on December 13, 2013 - 19:34

    Not bad, Jason!

  15. #15 by Jason Jones on December 13, 2013 - 20:51

    think of a one wheeled single key Enigma machine

  16. #16 by Howard on December 14, 2013 - 10:59

    That’s more like it!

  17. #17 by Laurie on December 14, 2013 - 11:24

    The odd number extension to my odd/even solution:

    Number people as they arrive and put their tickets into two buckets, odd and even. Each group picks from other bucket.

    If the total number of people is even, it’s all straight-forward.

    However, if the total number is odd, have a person from the odd numbers pick first. Then, swap their number over to the even bucket and proceed as for an even number problem. Simple…

  18. #18 by Dave C on December 14, 2013 - 11:37

    I built a solution in VBA behind Excel, You have, say 4 people, so I make a tracking string “1111” of available items. To person 1 there are three available items, because their own is not, so a random number from 1 to 3 is chosen. The 2nd available item is chosen (which is item 3), the tracking string is changed to “1101”. The second person now has two options, item 1 or item 4. A random number between 1 and 2 is chosen to decide if they’ll have item 1 or item 4. It’s a 2 so they get item 4, the string becomes “1100”, 3rd person has two options, item 1 or 2. Random choice produces 1 so they get the first item, tracking becomes “0100”, the last person searches the string for the first (and only) 1 and has that item. The approach only gets into difficulty if the last person ends up with their own item… at which point they can be swapped with any other person which will give a suitable outcome. DC

  19. #19 by Adam Cuerden on December 16, 2013 - 03:31

    Simplest way is to just have a bowl where the a person draws a number, they get that gift, and the person who provided the gift draws next. Some minor tweaks need to be made to this to keep it fulfilling the restrictions:

    1. The ticket for the first person who draws is kept out of the bowl.

    2. To randomise who gets the first person’s ticket, a ticket is drawn and set aside without looking. For the last two people, The person corresponding to that ticket gets the first person’s gift, and the other person gets the gift corresponding to that ticket.

    This lets people know who brought their gift, but that wasn’t one of the restrictions

  20. #20 by Richard on December 17, 2013 - 20:46

    Play dodgeball with the gifts, those who choose not to play can trade their bricks, knives, and yankee candles amongst one another.

  21. #21 by Ben Twilly on December 19, 2013 - 10:15

    Two thoughts spring to mind.
    The gift has a 76.987% chance of being a vibrating cock ring/dildo or some sort of tingling lube, so why not just throw them all into the middle of the room and everyone have fun together.
    Secondly it’s a MSS event full of Scousers, so even if someone doesn’t get the gift they fancy they can always nip down Boots on Monday and “borrow” one for themselves.

  22. #22 by Creeper on January 17, 2014 - 15:54

    What was the outcome?

(will not be published)