Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Deranged Santa solution

      1 January, 2003
      January 2003

      Deranged Santa

      Heap of presents

      It is Christmas Eve, and Santa is getting ready to deliver presents to children all round the world. He has a little glass of the season's spirits, and one thing leads to another, and before he knows it he is thoroughly "confused"... and he has completely mixed up all the labels with the children's names on, and put them randomly on the presents!

      Supposing he has one parcel each for N children, what is the probability that every child gets presents intended for someone else?

      The solution

      You may wonder why we gave this puzzle such a strange name - the reason is that a way of muddling up all the presents so that every child gets someone else's presents is called a derangement. We need to find the total number of derangements of N items.

      The total number of ways Santa can give presents to N children is N!=N×(N−1)×(N−2)×2×1. We need to know how many of these ways involve Santa giving no child the correct present.

      Let's start by counting the ways Santa can give {\bf one particular} child the correct present. This is easy - it is just (N−1)!. So if we write S(i) for the collection of ways Santa can deliver the presents, giving the correct present to the ith child, then S(i) has (N−1)! members.

      We want to know the number of ways he can deliver the presents, that are not in {\em any} S(i). The trouble is, the S(i) overlap - there are ways Santa can get it wrong for two children, or three children, and so on. So we can't find the total number of wrong ways just by adding the number of wrong ways in S(1),S(2) and so on all the way up to S(n). We have to take account of the overlap.

      Let's write S(i,j) for the collection of all the ways Santa can deliver the presents, giving the correct present to the ith child AND the jth child, and S(i,j,k) for the collection of all the ways Santa can deliver the presents, giving the correct present to the ith child AND the jth child AND the kth child, and so on. \par Then we can find the number of ways in which Santa gets it right for some child, somewhere (and subtract this from the total number of ways he can mix up the presents) like this:

      1. Let's add the sizes of S(1),S(2),..., all the way up to S(n). This includes all the ways Santa can give at least one child the right present - but lots of ways of delivering the presents have been counted more than once.
      2. Now we'll subtract the sum of all the ways Santa can deliver the presents, getting the right present to at least TWO children - this will get rid of all the overcounting in the first step, but unfortunately, lots of ways of delivering the presents will have been taken away too many times! For this step, we have to find the sum of the sizes of all the S(i,j) - for every pair i,j.
      3. So now we add back in all the ways Santa can deliver the presents, getting the right present to at least THREE children - but once again, we've added too much back in, and lots of ways of delivering the presents have been counted more than once again. This means finding the sum of the sizes of all the S(i,j,k) - for every possible choice of three children i,j, and k.
      4. So we'll subtract the sum of all the ways Santa can deliver the presents, getting the right present to at least FOUR children - but now we've taken off too much again!
      5. We continue like this until we're up to the number of ways Santa can deliver the presents, getting the right present to EVERY SINGLE CHILD.

      So what are these numbers we're adding? There are NC1 ways of choosing the number i, so adding together all the Si gives NC1×N. \par Next we have to find the sum of the sizes of all the S(i,j) - for every pair i,j. It's easy to see that there are (N−2)! ways of delivering presents to all the children so that two particular children get the right present - so S(i,j) has size (N−2)!. How many ways of choosing the two children i and j are there? This is easy too - it's NC2 - so this term is NC2×(N−2)!. Remember, NCM=N!(N−M)!×M!. \par Similarly, the next term isNC3×(N−3)!, and so on, until the last term is NCN×(N−N)!=1. (Actually, we could have worked the last term out directly, because there's only one way Santa can give the right present to every single child!) \par We subtract the second term, then add the third term, and so on, to find that the number of ways Santa can get it right for at least one child is N!1!(N−1)!(N−1)!−N!2!(N−2)!(N−2)!+N!3!(N−3)!(N−3)!−...−(−1)NN!0!N!(N−N)!=N![11!−12!+13!…+(−1)N1N!]. \par Since there are N! ways in total of delivering the presents, the number of ways Santa can get it wrong for every single child is N!−N![1−12!+13!...−(−1)N1N!]=N![12!−13!...+(−1)N1N!], and finally, the chance that Santa gets it wrong is this number divided by N! - the answer to the puzzle is [12!−13!...+(−1)N1N!].

      If you've made it this far down the page - Happy New Year from the Plus team!


      Back to main puzzle page
      • Log in or register to post comments
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms