Intereting Posts

Borel set preserved by continuous map
Can there be generalization of Monty Hall Problem?
Can someone explain consensus theorem for boolean algebra
Locally continuously differentiable implies locally Lipschitz
Asymptotic (divergent) series
Veronese Surface Represented by an Intersection of Quadratics
How to find $ \lim\limits_{ x\to 100 } \frac { 10-\sqrt { x } }{ x-100 }$
Does square difference prove that 1 = 2?
How is the notion of adjunction of two functors usefull?
Meaning of a set in the exponent
What is the distribution of primes modulo $n$?
Universal property of initial topology
Distributional derivative of a hölder function
the measurability of $\int_0^t X(s)ds$
Norm of ideals in quadratic number fields

We decided to do secret Santa in our office. And this brought up a whole heap of problems that nobody could think of solutions for – bear with me here.. this is an important problem.

We have 4 people in our office – each with a partner that will be at our Christmas meal.

Steve,

Christine,

Mark,

Mary,

Ken,

Ann,

Paul(me),

Vicki

- Counting primes
- What would be the shortest path between 2 points when there are objects obstructing the straight path?
- In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
- Do dynamic programming and greedy algorithms solve the same type of problems?
- How do Gap generate the elements in permutation groups?
- Are some real numbers “uncomputable”?

Desired outcome

Nobody can know who is buying a present for anybody else. But we each

want to know who we are buying our present for before going to the

Christmas party. And we don’t want to be buying presents for our partners.

Partners are not in the office.

Obvious solution is to put all the names in the hat – go around the office and draw two cards.

And yes – sure enough I drew myself and Mark drew his partner. (we swapped)

With that information I could work out that Steve had a 1/3 chance of having Vicki(he didn’t have himself or Christine – nor the two cards I had acquired Ann or Mary) and I knew that Mark was buying my present. Unacceptable result.

Ken asked the question: “What are the chances that we will pick ourselves or our partner?”

So I had a stab at working that out.

First card drawn -> 2/8

Second card drawn -> 12/56

Adding them together makes 28/56 i.e. 1/2.

i.e. This method won’t ever work… half chances of drawing somebody you know means we’ll be drawing all year before we get a solution that works.

My first thought was that we attach two cards to our backs… put on blindfolds and stumble around in the dark grabbing the first cards we came across… However this is a little unpractical and I’m pretty certain we’d end up knowing who grabbed what anyway.

Does anybody have a solution for distributing cards that results in our desired outcome?

**I’d prefer a solution without a third party..**

- Proving $\phi(m)|\phi(n)$ whenever $m|n$
- Probability question about married couples
- Number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is
- Proving $k \binom{n}{k} = n \binom{n-1}{k-1}$
- Bell numbers and moments of the Poisson distribution
- Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially
- Mutual set of representatives for left and right cosets: what about infinite groups?
- Ways to create a quadrilateral by joining vertices of regular polygon with no common side to polygon
- To find the total no. of six digit numbers that can be formed having property that every succeeding digit is greater than preceding digit.
- Odd and even numbers in Pascal's triangle-Sierpinski's triangle

1) You could have a third party party handle the distribution of cards in the hat so that every draw will be valid.

And after each draw the third party will remove invalid cards and put valid ones for the next draw. That should happen without any of the participants knowledge of how much cards are placed and removed.

The downside is that you will have that person know (or at least have enough information to deduce it) about who draws who.

2) Another solution would be if you take 8 cards with each persons name on one side and then every pair makes a unique mark on the other side and puts them in envelopes.

Then you shuffle the envelops, put the cards on the table unique mark up and everyone draws in sequence. In this way you could distinguish the invalid choice without knowing who’s who.

3) A modification of the above idea. Use cards with names, then every couple puts the in unique marked box (or envelopes) and then in a bigger box identical to the other ones.

Then someone puts the boxes in one of the offices, opens the big boxes and choses one card from one of the small boxes. Then everyone goes in one by one.

If no one looks at his own box no one knows if he/she was drawn or not.

**UPDATE** There is a chance that this scheme will fail if the last pair have less then 2 valid choices.

**UPDATE** If you have people enter the room randomly and without knowing the order of entrance that will solve the problem. That could be done (without third party) if you have one of the participants pick people at random to go there and then taking the last one.

This I hope works just as needed. ðŸ™‚

On a side Note : I would go for the script – it’s easier, but organizing all of the above might be a lot of fun to all.

**UPDATE** Well the stared look of someone looking **at you** will be the hint no algorithm can deal with.

If each of you just draws a random name out of the hat, the probability that nobody gets their own or their partner’s name is

$$\frac{4752}{40320} = \frac{33}{280} \approx 11.8\%.$$

Thus, the expected number of times you’ll need to repeat the process before getting “a solution that works” is $280/33 \approx 8.5$. This could get a bit tedious, but it’ll hardly take “all year”, at least unless you’re both really slow and really unlucky with the draw.

*Ps.* I went and calculated the odds for other numbers of couples too:

- $2$ couples: $\frac{4}{24} = \frac{1}{6} \approx 16.7\%$ chance of nobody getting their own or their partner’s name
- $3$ couples: $\frac{80}{720} = \frac{1}{9} \approx 11.1\%$
- $4$ couples: $\frac{4752}{40320} = \frac{33}{280} \approx 11.8\%$
- $5$ couples: $\frac{440192}{3628800} = \frac{3439}{28350} \approx 12.1\%$
- $6$ couples: $\frac{59245120}{479001600} = \frac{16831}{136080} \approx 12.4\%$

If I’m not mistaken, as the number of couples involved tends to infinity, the probability of nobody getting their or their partner’s name should tend towards the limit $e^{-2} \approx 13.5\%$, and thus the expected number of retries needed should tend towards $e^2 \approx 7.4$.

You take your own name out and your partners name out of the hat. You then draw a card which you keep. Hand the hat to your partner. They then get to draw a card, that they keep. You can now put your card and your partners card back in the hat. Hand the hat to someone else. Rinse and repteat.

See this algorithm here: http://weaving-stories.blogspot.co.uk/2013/08/how-to-do-secret-santa-so-that-no-one.html. It’s a little too long to include in a Stack Exchange answer.

Essentially, we fix the topology to be a simple cycle, and then once we have a random order of participants we can also determine who to get a gift for.

- Is every connected metric space with at least two points uncountable?
- How many digits of the googol-th prime can we calculate (or were calculated)?
- Norm equivalence (Frobenius and infinity)
- Different methods of evaluating $\int\sqrt{a^2-x^2}dx$:
- Closed form for $\prod\limits_{l=1}^\infty \cos\frac{x}{3^l}$
- diophantine equation $ |x^2-py^2|=\frac{p-1}{2} $
- Evaluate $\int_{0}^{\infty} \mathrm{e}^{-x^2-x^{-2}}\, dx$
- Inequality involving the sup of a function and its first and second derivatives
- Does $\cdot =$? Here $$ is the GIF function.
- Is it really possible to find primary decomposition of given ideal without using Macaulay2?
- Thurston's 37th way of thinking about the derivative
- Deriving a Quaternion Extension of Euler's Formula
- Can it happen that the image of a functor is not a category?
- Odd Mathematica series result
- Show that $\left(1+\frac{1}{n}\right)^{n}\geq \sum_{k=0}^n\left(\frac{1}{k!}\prod_{i=0}^{k-1}\left(1-\frac{i}{n}\right)\right)$