ROSECODE 271
Beautiful permutations
n is an integer ≥ 2.
The n+1 point of a permutation of 0,1,...,n are placed on a circle.
The permutation is said beautiful if for any 4 numbers 0 ≤ a,b,c,d ≤ n with a+c = b+d, the chord joining a and c does not intersect the chord joining b and d.
For n=3, there are 4 beautiful permutations:
How many beautiful permutations are there for n=1000?
You are given:
C = 6 for n = 4
C = 10 for n = 5
[My timing: < 1 s]
The n+1 point of a permutation of 0,1,...,n are placed on a circle.
The permutation is said beautiful if for any 4 numbers 0 ≤ a,b,c,d ≤ n with a+c = b+d, the chord joining a and c does not intersect the chord joining b and d.
For n=3, there are 4 beautiful permutations:
How many beautiful permutations are there for n=1000?
You are given:
C = 6 for n = 4
C = 10 for n = 5
[My timing: < 1 s]