13

The maximum period is Warm-up 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 ...


12

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: Well, Suppose we are interested in So what's the biggest But this means we are done! Because


12

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$,...


10

I think this works: The adjacent number pairs are restricted to where each pair sums to Note that it is necessary to because


9

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 ...


7

This is not a mathematical, but more of a logical approach:


7



6

(I'm understanding the problem to mean that each if the six distances appears exactly once.) Explanation:


6

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.


5

I think we need at least with the example coloring of To see this is the minimum, first consider Then, consider one of the colors used to color a center cell: Therefore, we conclude that


5

My answer: My method: Explanation of my method: Output of my method:


4

I think they can, in theory, In the following way. Second generation Now we have a second generation consisting of Third generation Now we have a third generation consisting of Fourth generation Now we have a fourth generation consisting of Assumptions I've assumed no intergenerational breeding: e.g. we can't have one of the original male astronauts ...


3

We can achieve with the following pattern: This is optimal because: (In fact, this pattern can tile the plane - there's no need to restrict it to a 5×5 grid.)


3

The smallest $n$ will be And here’s the grid (all possible grids will be mirrors and rotations of this): This is because Now to find the grid


3

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)=...


2

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.


2

Here is an example


2

The minimum is


1

The minimum is


1

I think the answer is which can be achieved by coloring the grid like this: First, consider the Then consider the Finally, consider the The rest can be filled as in the top grid.


1

Quite easy using a constraint solver. For example Minizinc language and then using Gecode solver: include "alldifferent.mzn"; 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]) ); ...


1

One of many: --30 characters--


1

Simpler proof of maximum:


Only top voted, non community-wiki answers of a minimum length are eligible