A Very Merry Christmas Brainteaser

Ho Ho Hmmmmm

I adore brainteasers and am always excited when I stumble across one in the wild. So, as a kind of holiday gift, here’s an original Christmas-themed brainteaser. Enjoy and happy holidays!

The Puzzle

It’s the night before Christmas, and Santa is laying out his plans. He feels prepared, as his workshop can generate any kind of toy and any number of each kind.

Still, the task to delivery toys to all children in the world is a big one. Moreover, he has 3 requirements:

1. He must deliver exactly two toys to every child.

2. For any one child, the two toys must be different kinds.

3. No two children can receive the same exact pair of (kinds of) toys. More precisely, while he can give each kind of toy to many children, each child must receive a unique combination.

In short, he wants to ensure each child receives two different toys — what kid wants two of the same thing? — and each child, being unique, must receive a unique pair of toys.

Unfortunately, under the crushing pressure of running a globe-spanning, billion-user, but reindeer-dependent operation, Santa has become a wee bit unstable. After Spotify accidentally played “The Twelve Days of Christmas” on loop for seven hours, he’s become transfixed with the idea of giving distinct numbers of gifts. Specifically, he wants to distribute toys such that each kind of toy is given to a different number of children.

You, a loyal elf, are increasingly worried about Santa’s deteriorating mental state. Answer the question quickly to end his spiral and get Christmas back on track: Following the 3 original requirements above, can Santa distribute toys such that each kind of toy is given to a different number of children? If yes, provide a general strategy for doing so. If no, prove that it is impossible.

Some Examples and Clarifications

To illustrate the original 3 requirements, suppose there are just two kids, Alice and Bob. Also suppose Santa makes 4 distinct kinds of toys: Legos, Nintendo Switches, Taylor Swift Eras tickets, and socks.

Under the 3 original requirements, Santa could:

• Give Alice Legos and Taylor Swift tix; give Bob a Switch and socks.

• Give Alice Legos and Taylor Swift tix; give Bob a Switch and Taylor Swift tix. Even though both Alice and Bob get Taylor Swift tickets, they’re still each receiving a unique pair of toys.

But Santa could NOT:

• Give both Alice and Bob Legos and Taylor Swift tickets, as then two children would be receiving the same pair of toys.

• Give Alice Legos and tickets, while giving Bob two Switches, as Bob is not receiving two distinct gifts.

With regard to Santa’s desire to have each ‘kind of toy given to a different number of children’:

• A scenario where 4 children receive socks, 3 children receive Taylor Swift tickets, and 1 child receives a Nintendo Switch would do so. This scenario may or may not be possible — that’s up to you to determine!

• In contrast, the valid examples with Alice and Bob described above do not do so. In the first example, all toys were given to exactly one child. In the second example (Give Alice Legos and Taylor Swift tix; give Bob a Switch and Taylor Swift tix), the Legos and Nintendo Switch were each given to 1 child.

Santa’s workshop, a manufacturing marvel and the envy of Jeff Bezos, can generate any number of kinds of toys and any number of those toys.

Any strategy or proof should (and will!) work regardless of the number of children.

Only scroll further if you wants hints or the solution! Keep scrolling to get a first hint.

…

…

…

…

…

…

Hint 1

What limits can you put around the number of children that can receive any one kind of toy?

Continue scrolling for a second hint.

…

…

…

…

…

…

Hint 2

Remembering that each child must receive a distinct pair of toys, how many children can receive any one toy? It may be helpful to assume that there a specific, small number of toys that are given to any child.

Continue scrolling for the solution.

…

…

…

…

…

…

Solution

Sadly for Santa, it can’t be done. No matter the number of children or how you distribute the toys, you will always end up with at least two kinds of toys given to the same number of children.

To see why, consider a relatively small case that will generalize nicely.

Suppose that Santa ends up making 10 toys where each is given to at least one child. (This hypothetical world is very small, or most of the children in it are little sociopaths who didn’t make the nice list.)

Because every child’s pair of toys must be unique, any 1 kinds of toys can be paired with the 9 other kinds of toys. It can’t be paired with itself, and if it was ever paired with another toy twice, the pair be unique. Hence, any one kind of toy can only be given to at most 9 children.

So every one of the 10 kinds of toys must be given to at least 1 but no more than 9 children.

But there are 10 kinds of toys and only 9 possible numbers of children that can received each. Even if the first 9 kind of toys have distinct numbers of children, the 10th kind of toy must be given to the same number of children as some other kind of toy.

Or, the more general, mathematically-precise version: for any solution, Santa must give n kinds of toys to at least 1 child. However, each kind of toy can only be paired with the n - 1 other kinds, and therefore can only be given to n - 1 children. Thus, each of the n toys must be given to some number of children between (and including) 1 and n - 1. With more kinds of toys than options for the number of children, at least two kinds of toys must be given to the same number of children.

(If you’re curious to learn more, this is called the Pigeonhole Principle, which comes from the wonderful world of discrete math.)

Santa is disappointed to learn it can’t be done, but thanks to your proof, he’s snapped out of his trance and whisks himself off to deliver his pairs of presents to all.