1
$\begingroup$

[This may be the wrong SE for this question. But as a non-mathematician I feel it may be too simple for MathOverflow, and that I might benefit from a school-level explanation. Also, it might make a fun seasonal class assignment.]

If everyone in a classroom is involved in a Secret Santa style present exchange then, intuitively, it seems to make sense that it requires an even number in order to be fair. Someone gives a present, another receives: that's a pair. If there's an odd number in the class, someone will lose out.

Except they won't. Let there be three people in the class: pupils A, B and C. A gives to B, B gives to C, C gives to A.

In terms of "common sense" thinking this appears to be a paradox. Obviously it isn't. Can someone explain why not, mathematical terms?

$\endgroup$
4
  • 1
    $\begingroup$ Perhaps it would be easier for students to understand if the situation was drawn as a directed graph? Model each student as a vertex, an arrow from a vertex to a different vertex represents the giving and receiving of a present, and each vertex should have exactly two edges (one incoming, the other outgoing). $\endgroup$ – Joel Reyes Noche Nov 10 '15 at 13:06
  • 5
    $\begingroup$ This is definitely not appropriate for MathOverflow (which is for research mathematics). In general if you have a simpler maths question you should go to Math.SE. As it is, I can't work out whether you are asking for the answer or for how to explain the answer. $\endgroup$ – Jessica B Nov 10 '15 at 17:36
  • 6
    $\begingroup$ It is sufficient to group people in pairs to organize a Secret Santa exchange, but not necessary. I am not sure what further explanation you want besides a counterexample. It is not a paradox, but a mistaken understanding of what is required to organize a Secret Santa exchange. $\endgroup$ – Michael Joyce Nov 10 '15 at 17:39
  • 1
    $\begingroup$ "...intuitively, it seems to make sense that it requires an even number in order to be fair." An even number of what? If you mean people, then you have indicated why this needn't be the case. But I wonder whether you are, perhaps, getting muddled up in computing the total number of actions (viz., the actions of giving and receiving); indeed, in your example of A to B to C to A, the number of actions is 3 giving + 3 receiving = 6 actions, which is even. $\endgroup$ – Benjamin Dickman Nov 21 '15 at 7:28
6
$\begingroup$

If someone gives a present and another receives it, they are indeed a pair. If there are n pairs, it would seem there are 2n students. The problem with that is the pairs overlap and every student is in two pairs.

This is shown in your counterexample. A gives to B, B gives to C, and C gives to A. There are 3 pairs and 3 students. The can be generalized to n pairs and n students. For example if there are 5 students: A gives to B, B gives to C, and C gives to D, D gives to E and E gives to A.

IF n is odd, the number of pairs will be odd. Thus there can be an odd number of students and an odd number of pairs.

$\endgroup$
0
$\begingroup$

Notice the word "Secret" in "Secret Santa": The recipient is not supposed to know who his or her Santa is. If presents were swapped then the receiver of my present would be presenting the present for me, so I would know who my Secret Santa is and so would they.

That's why the receivers are a permutation of the givers, with no fixed point (because nobody should buy their own present), and nobody being told that they are part of a cycle of length 2.

$\endgroup$
0
$\begingroup$

Mathematically you are looking at a bijection G (for Giving) with no fixed point, on a finite set S with at least 2 members, and its inverse bijection R (for Receiving). When S has at least 3 members it is not inevitable that a "gift-pair" exists. A gift-pair is a pair (x,y) of members of S for which G(x)=y and G(y)=x.(Or equivalently R(x)=y and R(y)=x.) And if S has an odd number of members, at least 3 them do not belong to any gift-pairs.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.