New answers tagged graph-theory
2
a)
! My choice is: 3,9,110=2*55, 154=2*77. Here, 3 and 9 are connected, as are 110 and 154 as both have 11 as prime factor. These numbers are mapped to 10, 28, 77, 55.
In this chain of numbers we have the connections 10-28-77-55-10, so we get the graph on the right.
b)
6
Following on from a Python program posted on the first question of this type, I made some minor modifications - it turns out that the squares identified by @Steve are sufficient to guarantee a solution that fits the criteria of the problem, without explicitly taking squared-number criteria into account. Here is the solution:
Here is the program I used:
"""
...
15
First it is easy to see that
From here, there is only one "odd" square that
as stated by @daw in comments,
It looks to me like this
The only remaining way to
Continuing, we could turn left or right, but
The upper route
For the other route shown above,
Thus, only one possibility remains for
Looking to the next square number,
Now turning our ...
10
This seems to work:
6
Human mind can brute force too :P
2 is obvious and 3 is easy. Then: List of prime distances from 3 onward: 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, (5) - to get from 61 to 2.
Draw path in corners, then
Let's assume
Because
Assume the first option
Second option:
Therefore, after a lot of work
What now?
Let's write the remaining distances:
...
2
I think there are two more solutions than Rob suggests, though the differences are quite slight. One is:
And the other is a similar adjustment to the difference between Rob's 2. I'm afraid I did this by brute force on Python having tried and failed to find an elegant method.
19
I used integer linear programming, as follows. Let binary decision variable $x_{i,j,k}$ indicate whether cell $(i,j)$ contains value $k$. Let $N_{i,j}$ be the set of neighbors of cell $(i,j)$. The constraints are:
\begin{align}
\sum_{k=1}^{64} x_{i,j,k} &= 1\\
\sum_{i=1}^8 \sum_{j=1}^8 x_{i,j,k} &= 1\\
x_{i,j,k} &\le \sum_{(i',j')\in N_{i,j}} x_{...
5
A solution using all vertical transpositions. All changes annotated and words defined.
5
Not sure if this is optimal, but here's my solution
Top 50 recent answers are included
