A friend gave me the following riddle:
Given n people with n distinct names, you place n names tags on a round table with n seats. If the n people now sit at those seats randomly such that exactly one person sits correctly (in the seat with the correct name tag with their name one it), can we rotate the table such that (at least) two people sit correctly?
For odd n this is false, which you can see by considering by placing the name tags 1, ..., n in order and seating the people as 1, n, n - 1, ... 2. I haven't been able that this true for even n so I wanted to try out small even n with a python script.
I wrote the following code. Unfortunately, it is very slow (n = 10 takes about 25 seconds, but n = 12 takes nearly 11 minutes!) so I am searching for libraries which can speed up the things I implemented from scratch or maybe a method which speeds things up.
I have 4 methods:
perms(n), which gives me all permutations of 0, ..., n- 1 which have one fixed point,
fixtest(L,m), which tests if the permutation L has m fixed points,
rot(L), which rotates the permutation L, i.e. [1,2,3] becomes [2,3,1] and
test(n)which, for a given n generates all permutations of 0, ..., n- 1 which have one fixed point with
perms(n)and then for each one, performs all rotations and for every rotation checks the number of fixed points and writes them in a list
Conly contains ones, we have found a counterexample to the riddle above.
My code looks like this
from itertools import permutations from collections import deque # find all permutations of [n] with 1 fixed point def perms(n): P = (perm for perm in permutations(range(n))) D =  # D will contain the 'right' permutations (those with one fixed point) for perm in P: # count fixed points (counter c) c = 0 for idx, k in enumerate(perm): if idx == k: c +=1 if c == 1: D.append(perm) return D # tests if a sequence L has m fixed points def fixtest(L,m): L = list(L) c = 0 for idx, k in enumerate(L): if idx == k: c +=1 if c == m: return True else: return False # rotates the list L def rot(L): L = deque(L) a = L.pop() L.appendleft(a) return list(L) def test(n): for f in perms(n): k = 0 C =  f_real = list(f) while k < n - 1: f = rot(f) C.append(fixtest(f,1)) k +=1 if all(x == True for x in C): return n, 'Counterexample found:', f_real return n, 'no counterexamples found'