Return to Answer

Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution. If $S=S'$ one might call it a symmetric solution. This requires that $n$ and/or $m(n)$ is even. In any case it might be pleasant to try to maximize $|S \cap S'|.$ A possible alternate, or further, goal would be to minimize the number of distinct jumps between successive entries.Aside from aesthetics, when there are several optimal solutions, the ones with the must symmetry or regularity might be fruitful for suggesting generalizations.

In a somewhat trivial sense, for any two solutions $S_1,S_2$ of size $m(n),$ One can change $S_1$ to $S_2$ by shifting entries. So it is hard to say if one solution is essentially different from another.

Many values of $n$ (but not all) seem to have optimal solutions with this structure:

Start with $0,1,2,\cdots, d-1=s_d$ end with $s_{d+p+1}=n-(d-1),\cdots, n-2,n-1,n$ and in the middle put entries $s_{d+1},s_{d+2},\cdots,s_{d+p}$ which satisfy $s_{i+1}-s_i \leq d$ for $d-1\leq i \leq d+p.$

This will always give a solution of size $2d+p$. For an optimal solution $d$ should be around $\sqrt{\frac{n}2}$ and $p$ as small as possible given $n,d,$ so $p=\lceil \frac{n+2}d-3\rceil.$

For example, $m(38)=15$ and the solution $$S=\{0,1,2,3,4,9,14,19,24,29,31,34,35,37,38\}$$ can be shifted to give this solution with $d=4$

$$S=\{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 35, 36, 37, 38\}$$

and also this one with $d=5$

$$\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 35, 36, 37, 38\}.$$ In those cases there is no choice for the middle entries as $\frac{40}{4}-3=7$ and $\frac{40}5-3=5.$

For $n=2d^2-2$ there are optimal symmetric solutions with $|S|=4d-3$. These are the ones listed by Rob Pratt for $n=6,16.$

• $\{0,1,2,3,7,11,15,19,23,27,28,29,30\}$ works for $d=4.$
• $\{0,1,2,3,4,9,14,19,24,29,34,39,44,45,46,47,48\}$ works for $d=5.$

One last example: $m(43)=16$ and one solution is $$S=\{0, 1, 3, 4, 5, 8, 14, 20, 26, 29, 35, 38, 39, 40, 42, 43\}$$

A symmetric solution is $$S =\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 39, 40, 41, 42, 43\}.$$

Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution. If $S=S'$ one might call it a symmetric solution. This requires that $n$ and/or $m(n)$ is even. In any case it might be pleasant to try to maximize $|S \cap S'|.$ A possible alternate, or further, goal would be to minimize the number of distinct jumps between successive entries.Aside from aesthetics, when there are several optimal solutions, the ones with the must symmetry or regularity might be fruitful for suggesting generalizations.

In a somewhat trivial sense, for any two solutions $S_1,S_2$ of size $m(n),$ One can change $S_1$ to $S_2$ by shifting entries. So it is hard to say if one solution is essentially different from another.

Many values of $n$ (but not all) seem to have optimal solutions with this structure:

Start with $0,1,2,\cdots, d-1=s_d$ end with $s_{d+p+1}=n-(d-1),\cdots, n-2,n-1,n$ and in the middle put entries $s_{d+1},s_{d+2},\cdots,s_{d+p}$ which satisfy $s_{i+1}-s_i \leq d$ for $d-1\leq i \leq d+p.$

This will always give a solution of size $2d+p$. For an optimal solution $d$ should be around $\sqrt{\frac{n}2}$ and $p$ as small as possible given $n,d,$ so $p=\lceil \frac{n+2}d-3\rceil.$ In some cases there are $3$ values of $d$ which work.

$m(23)=12$ and one solution is $S=\{0,1,3,5,6,13,15,16,18,20,22,23\}$

There are $22$ symmetric solutions. The lower halves are

$ \left\{ 0,1,2,3,4,9 \right\} , \left\{ 0,1,2,3,6,10 \right\} , \left\{ 0,1,2,3,7,10 \right\} , \left\{ 0,1,2,3,7,11 \right\} , \mathbf{\left\{ 0,1,2,4,5,11 \right\}} , \left\{ 0,1,2,4,6,9 \right\} , \left\{ 0,1,2,4,7,10 \right\} , \left\{ 0,1,2,5,6,8 \right\} , \left\{ 0,1,2,5,7,10 \right\} , \left\{ 0,1,2,5,8,10 \right\} , \left\{ 0,1,2,5,8,11 \right\} , \mathbf{\left\{ 0,1,3,4,5,11 \right\} , \left\{ 0,1,3,4,6,11 \right\} , \left\{ 0,1,3,4,7,9 \right\} , \left\{ 0,1,3,4,8,9 \right\} , \left\{ 0,1,3,4,8,10 \right\} , \left\{ 0,1,3,4,9,10 \right\} , \left\{ 0,1,3,4,9,11 \right\} , \left\{ 0,1,3,5,6,8 \right\} , \left\{ 0,1,3,5,6,10 \right\} , \left\{ 0,1,3,5,6,11 \right\} , \left\{ 0,1,3,5,7,8 \right\}} $

The values of $d$ represented are $3,4,5.$ The ones in bold merit further perusal. They do not fully fit the scheme described as there are jumps greater than the relevant $d$.

$m(20)=10$ and the given solution $S=\{0,1,3,4,9,11,16,17,19,20\}$ is symmetric.

There are no solutions which fit the scheme above as $$6+\lceil \frac{22}3 \rceil-3=8+\lceil \frac{22}4 \rceil-3=11.$$

$m(38)=15$ and the solution $$S=\{0,1,2,3,4,9,14,19,24,29,31,34,35,37,38\}$$ can be shifted to give this solution with $d=4$

$$S=\{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 35, 36, 37, 38\}$$

and also this one with $d=5$

$$\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 35, 36, 37, 38\}.$$ In those cases there is no choice for the middle entries as $\frac{40}{4}-3=7$ and $\frac{40}5-3=5.$

For $n=2d^2-2$ there are optimal symmetric solutions with $|S|=4d-3$. These are the ones listed by Rob Pratt for $n=6,16.$

• $\{0,1,2,3,7,11,15,19,23,27,28,29,30\}$ works for $d=4.$
• $\{0,1,2,3,4,9,14,19,24,29,34,39,44,45,46,47,48\}$ works for $d=5.$

One last example: $m(43)=16$ and one solution is $$S=\{0, 1, 3, 4, 5, 8, 14, 20, 26, 29, 35, 38, 39, 40, 42, 43\}$$

A symmetric solution is $$S =\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 39, 40, 41, 42, 43\}.$$

Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution. If $S=S'$ one might call it a symmetric solution. This requires that $n$ and/or $m(n)$ is even. In any case it might be pleasant to try to maximize $|S \cap S'|.$ A possible alternate, or further, goal would be to minimize the number of distinct jumps between successive entries.Aside from aesthetics, when there are several optimal solutions, the ones with the must symmetry or regularity might be fruitful for suggesting generalizations.

In a somewhat trivial sense, for any two solutions $S_1,S_2$ of size $m(n),$ One can change $S_1$ to $S_2$ by shifting entries. So it is hard to say if one solution is essentially different from another.

Many values of $n$ (but not all) seem to have optimal solutions with this structure:

Start with $0,1,2,\cdots, d-1=s_d$ end with $s_{d+p+1}=n-(d-1),\cdots, n-2,n-1,n$ and in the middle put entries $s_{d+1},s_{d+2},\cdots,s_{d+p}$ which satisfy $s_{i+1}-s_i \leq d$ for $d\leq i \leq d+p.$

This will always give a solution of size $2d+p$. For an optimal solution $d$ should be around $\sqrt{\frac{n}2}$ and $p$ as small as possible given $n,d,$ so $p=\lceil \frac{n+2}d-3\rceil.$

For example, $m(38)=15$ and the solution $$S=\{0,1,2,3,4,9,14,19,24,29,31,34,35,37,38\}$$ can be shifted to give this solution with $d=4$

$$S=\{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 35, 36, 37, 38\}$$

and also this one with $d=5$

$$\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 35, 36, 37, 38\}.$$ In those cases there is no choice for the middle entries as $\frac{40}{4}-3=7$ and $\frac{40}5-3=5.$

For $n=2d^2-2$ there are optimal symmetric solutions with $|S|=4d-3$. These are the ones listed by Rob Pratt for $n=6,16.$

• $\{0,1,2,3,7,11,15,19,23,27,28,29,30\}$ works for $d=4.$
• $\{0,1,2,3,4,9,14,19,24,29,34,39,44,45,46,47,48\}$ works for $d=5.$

One last example: $m(43)=16$ and one solution is $$S=\{0, 1, 3, 4, 5, 8, 14, 20, 26, 29, 35, 38, 39, 40, 42, 43\}$$

A symmetric solution is $$S =\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 39, 40, 41, 42, 43\}.$$

Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution. If $S=S'$ one might call it a symmetric solution. This requires that $n$ and/or $m(n)$ is even. In any case it might be pleasant to try to maximize $|S \cap S'|.$ A possible alternate, or further, goal would be to minimize the number of distinct jumps between successive entries.Aside from aesthetics, when there are several optimal solutions, the ones with the must symmetry or regularity might be fruitful for suggesting generalizations.

In a somewhat trivial sense, for any two solutions $S_1,S_2$ of size $m(n),$ One can change $S_1$ to $S_2$ by shifting entries. So it is hard to say if one solution is essentially different from another.

Many values of $n$ (but not all) seem to have optimal solutions with this structure:

Start with $0,1,2,\cdots, d-1=s_d$ end with $s_{d+p+1}=n-(d-1),\cdots, n-2,n-1,n$ and in the middle put entries $s_{d+1},s_{d+2},\cdots,s_{d+p}$ which satisfy $s_{i+1}-s_i \leq d$ for $d-1\leq i \leq d+p.$

This will always give a solution of size $2d+p$. For an optimal solution $d$ should be around $\sqrt{\frac{n}2}$ and $p$ as small as possible given $n,d,$ so $p=\lceil \frac{n+2}d-3\rceil.$

For example, $m(38)=15$ and the solution $$S=\{0,1,2,3,4,9,14,19,24,29,31,34,35,37,38\}$$ can be shifted to give this solution with $d=4$

$$S=\{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 35, 36, 37, 38\}$$

and also this one with $d=5$

$$\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 35, 36, 37, 38\}.$$ In those cases there is no choice for the middle entries as $\frac{40}{4}-3=7$ and $\frac{40}5-3=5.$

For $n=2d^2-2$ there are optimal symmetric solutions with $|S|=4d-3$. These are the ones listed by Rob Pratt for $n=6,16.$

• $\{0,1,2,3,7,11,15,19,23,27,28,29,30\}$ works for $d=4.$
• $\{0,1,2,3,4,9,14,19,24,29,34,39,44,45,46,47,48\}$ works for $d=5.$

One last example: $m(43)=16$ and one solution is $$S=\{0, 1, 3, 4, 5, 8, 14, 20, 26, 29, 35, 38, 39, 40, 42, 43\}$$

A symmetric solution is $$S =\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 39, 40, 41, 42, 43\}.$$

Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution.

In many of the solutions given by Rob Pratt the solution can remain valid with some shifting of entries to achieve symmetry or near symmetry. For example, if the first entries are $0,1,\cdots,d-1$ and the last $n-(d-1),\cdots n,$ then each of the central entries must be no more that $d$ from their neighbors.

Here are alternate solutions to those of Rob Pratt which also achieve $m(n).$ I use boldface to indicate that the listed solution is also symmetric.

• $n=7$ $\{0, 1, 2, 5, 6, 7\}$
• $n=9$ $\{0, 1, 2, 5, 7,8,9\}$
• $\mathbf{n=10}$ $\{0, 1, 2, 5, 8, 9, 10\}$
• $\mathbf{n=11}$ $\{0, 1, 2, 4, 7, 9, 10, 11\}$
• $n=12$ $\{0, 1, 2, 3, 5, 7, 10, 11, 12\}$
• $\mathbf{n=14}$ $\{0, 1, 2, 4, 7, 10, 12, 13, 14\} $
• $n=17$ $\{0, 1, 2, 5, 8, 9, 12, 15, 16, 17\}$

For $n=2d^2-2$ there are optimal symmetric solutions with $|S|=4d-3$. These are the ones listed by Rob Pratt for $n=6,16.$

• $\{0,1,2,3,7,11,15,19,23,27,28,29,30\}$ works for $d=4.$
• $\{0,1,2,3,4,9,14,19,24,29,34,39,44,45,46,47,48\}$ works for $d=5.$

This is, of course, just the scheme suggested by Gerry Myerson with a very minor adjustment.

Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution. If $S=S'$ one might call it a symmetric solution. This requires that $n$ and/or $m(n)$ is even. In any case it might be pleasant to try to maximize $|S \cap S'|.$ A possible alternate, or further, goal would be to minimize the number of distinct jumps between successive entries.Aside from aesthetics, when there are several optimal solutions, the ones with the must symmetry or regularity might be fruitful for suggesting generalizations.

In a somewhat trivial sense, for any two solutions $S_1,S_2$ of size $m(n),$ One can change $S_1$ to $S_2$ by shifting entries. So it is hard to say if one solution is essentially different from another.

Many values of $n$ (but not all) seem to have optimal solutions with this structure:

Start with $0,1,2,\cdots, d-1=s_d$ end with $s_{d+p+1}=n-(d-1),\cdots, n-2,n-1,n$ and in the middle put entries $s_{d+1},s_{d+2},\cdots,s_{d+p}$ which satisfy $s_{i+1}-s_i \leq d$ for $d\leq i \leq d+p.$

This will always give a solution of size $2d+p$. For an optimal solution $d$ should be around $\sqrt{\frac{n}2}$ and $p$ as small as possible given $n,d,$ so $p=\lceil \frac{n+2}d-3\rceil.$

For example, $m(38)=15$ and the solution $$S=\{0,1,2,3,4,9,14,19,24,29,31,34,35,37,38\}$$ can be shifted to give this solution with $d=4$

$$S=\{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 35, 36, 37, 38\}$$

and also this one with $d=5$

$$\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 35, 36, 37, 38\}.$$ In those cases there is no choice for the middle entries as $\frac{40}{4}-3=7$ and $\frac{40}5-3=5.$

For $n=2d^2-2$ there are optimal symmetric solutions with $|S|=4d-3$. These are the ones listed by Rob Pratt for $n=6,16.$

• $\{0,1,2,3,7,11,15,19,23,27,28,29,30\}$ works for $d=4.$
• $\{0,1,2,3,4,9,14,19,24,29,34,39,44,45,46,47,48\}$ works for $d=5.$

One last example: $m(43)=16$ and one solution is $$S=\{0, 1, 3, 4, 5, 8, 14, 20, 26, 29, 35, 38, 39, 40, 42, 43\}$$

A symmetric solution is $$S =\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 39, 40, 41, 42, 43\}.$$