The maximum period is
An exchange instruction swaps two positions in line. Any permutation of the 16 positions can be achieved by a dance program with only exchange instruction, by decomposing the permutation into swaps.
To find the period of a dance program with only exchange instruction, note that it breaks down into cycles that split up the 16 ...
If my calculations are correct (it's a bit fiddly), then I believe the answer is
When we do a "partner" operation,
So, an equivalent way to state the problem is this:
Suppose we are interested in
So what's the biggest
But this means we are done! Because
An easy upper bound is
because each day contributes $8-2=6$ triples out of $8\cdot 7 \cdot 6$.
Here's an optimal solution with
I used integer linear programming as follows. For each of the $8!=40320$ permutations $p \in P$, let binary decision variable $x_p$ indicate whether that permutation appears. For each of the $8\cdot 7\cdot 6=336$ triples $t\in T$,...
I'll take "at most" to mean the absolute theoretical maximum, and the "no inbreeding" to mean the parents share no ancestors whatsoever, no matter how distant.
Since it is never better to add two ancestors where one would do, the best result can be achieved when the only men to reproduce are the ones in the original crew. At the ...
Here is another one:
Note that for any permutation of the first 4 columns there are 6 matching permutations of the last 4 that give rise to another solution. And similar for rows. So this is actually a family of solutions.
I think they can, in theory,
In the following way.
Now we have a second generation consisting of
Now we have a third generation consisting of
Now we have a fourth generation consisting of
I've assumed no intergenerational breeding: e.g. we can't have one of the original male astronauts ...
Greedy strategy gives at most (not optimal but close)
where the greedy strategy was to
In other words, in terms of graph theory:
I constructed a graph $G$ whose vertices are the permutations, $|V|=8!=40320$.
Two vertices $v,w\in V$ are connected by an edge if and only if they cannot form a solution together. Then, the degree of every vertex will be $d(v)=...
Here is a partial answer. It proves a fault-free rectangle can be assembled from rectangles of size mxn such that one dimension is not a multiple of the other.
The remaining cases can be converted to the 1xn case solved earlier by Bubbler.
Quite easy using a constraint solver.
For example Minizinc language and then using Gecode solver:
int: N = 8;
array[1..N,1..N] of var 1..N: p;
set of int: not_primes = array2set([4, 6, 8, 9, 10, 12, 14, 15, 16]);
constraint forall(n in 1..N)(
alldifferent([p[n,g] |g in 1..N]) /\ alldifferent([p[g,n] |g in 1..N])