Enigmatic Code

Programming Enigma Puzzles

Teaser 2779: New Year Party

From The Sunday Times, 27th December 2015 [link]

We have a game planned for our forthcoming New Year party. Each person there will write their name on a slip of paper and the slips will be shuffled and one given to each person. If anyone gets their own slip, then all the slips will be collected up and we shall start again. When everyone has been given a name different from their own, each person will use their right hand to hold the left hand of the person named on their slip. We hope that everyone will then be forming one circle ready to sing Auld Lang Syne — but there’s a slightly less than evens chance of this happening.

How many people will there be at the party?

[teaser2779]

3 responses to “Teaser 2779: New Year Party

  1. Jim Randell 12 February 2019 at 8:54 am

    We can calculate:

    d(n) = the number of derangements of n elements
    d(1) = 0
    d(n) = n × d(n – 1) + (–1)^n

    and:

    c(n) = the number of cyclic permutations of n elements
    c(1) = 0
    c(n) = factorial(n – 1)

    by recursive formulae, or we can build them up from the previous terms as we consider increasing n.

    Run: [ @repl.it ]

    from enigma import fdiv, printf
    
    # consider increasing n
    (n, d, c) = (2, 1, 1)
    while True:
      printf("n={n} d={d} c={c} p={p:.3f}", p=fdiv(c, d))
      if 2 * c < d: break
      # increase n and calculate d(n) and c(n)
      c *= n
      n += 1
      d *= n
      d += (-1 if n % 2 else 1)
    

    Solution: There will be 6 people at the party.

  2. Hugh Casement 12 February 2019 at 9:19 am

    I confess your formula for d(n) is new to me.
    I calculated it as subfactorial(n) = !n, otherwise written ,
    which is the nearest integer to (n! / e).

    • Hugh Casement 12 February 2019 at 9:23 am

      What looks like ni is meant to be n followed by an inverted exclamation mark.   Perhaps it’s just my browser that doesn’t show it correctly.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: