Sunday Times Teaser 2995 – Pub Celebration

by Howard Williams

Published Sunday February 16 2020 (link)

While celebrating with friends in the pub, it was my round, and I worked out the number of ways that I could get everybody else’s drink wrong. I could remember the drinks (and they all wanted different drinks), but not who wanted which drink.

More friends arrived (there were fewer than twenty of us in total), and everyone still wanted different drinks. Again assuming that I could remember the drinks but not who wanted which drink, I worked out the number of ways that I could get everybody else’s drink wrong, and found that the number was 206 times the first number. Fortunately, it was no longer my round!

What was the second number?

2 Comments Leave one →

Brian Gladman permalink

This runs in less than a millisecond.


# The number of derangements, D(n), of N items (permutations in
# which all items change their original positions) is given by:
#
#        D(1) = 0; N > 1: D(N) = N.D(N - 1) + (-1)^N 
# or:
#
#        D(n) = [n! / e]

d, ds = 0, [0]
for n in range(2, 20):
  # compute D(n) and add 206 times its value as a target
  d = n * d + 1 - 2 * (n & 1)
  ds.append(d)
  # have we hit a target?
  q, r = divmod(d, 206)
  if r == 0 and q in ds:
    print(f"{d} derangements and {n} friends (earlier {q} and {ds.index(q) + 1}).")

# The number of derangements, D(n), of N items (permutations in

# which all items change their original positions) is given by:

# D(1) = 0; N > 1: D(N) = N.D(N - 1) + (-1)^N

# or:

# D(n) = [n! / e]

d, ds = 0, [0]

for n in range(2, 20):

# compute D(n) and add 206 times its value as a target

d = n * d + 1 - 2 * (n & 1)

ds.append(d)

# have we hit a target?

q, r = divmod(d, 206)

if r == 0 and q in ds:

print(f"{d} derangements and {n} friends (earlier {q} and {ds.index(q) + 1}).")

GeoffR permalink


from itertools import permutations
sf = []

def sub_fact(n):
  if n == 0: return 1
  return n * sub_fact(n - 1) + (-1 if n % 2 == 1 else 1)

for n in range(1, 20):
  sfact = sub_fact(n)
  sf.append(sfact)

for a, b in permutations(sf, 2):
  if b > a and a != 0 and b // a == 206:
      num1, num2 = sf.index(a) + 1, sf.index(b) + 1
      print (f"1st number of friends/derangments = {num1}/{a}")
      print (f"2nd number of friends/derangments = {num2}/{b} ")

from itertools import permutations

sf = []

def sub_fact(n):

if n == 0: return 1

return n * sub_fact(n - 1) + (-1 if n % 2 == 1 else 1)

for n in range(1, 20):

sfact = sub_fact(n)

sf.append(sfact)

for a, b in permutations(sf, 2):

if b > a and a != 0 and b // a == 206:

num1, num2 = sf.index(a) + 1, sf.index(b) + 1

print (f"1st number of friends/derangments = {num1}/{a}")

print (f"2nd number of friends/derangments = {num2}/{b} ")

Sunday Times Teaser 2995 – Pub Celebration

by Howard Williams

Published Sunday February 16 2020 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta