There are N colours, N balls of each, and N+1 lanes that hold N balls. At the start one lane is empty and every other lane holds the colours 1, 2, …, N from bottom to top, so each row has one colour. A move takes the top ball of a lane to any lane with room. How many moves does it take to make every lane one colour?
色は N 色、玉は各色 N 個、レーンは N+1 本で、1 本に N 個入る。最初は 1 本が空で、残りのレーンはどれも下から色 1, 2, …, N の順。つまり横の段ごとに 1 色になっている。1 手で、あるレーンの一番上の玉を、空きのある別のレーンへ移す。どのレーンも 1 色にするには、最少で何手かかるか。
Write T(N) for the minimum number of moves.
最少手数を T(N) と書く。
T(2), …, T(6) = 3, 10, 21, 36, 55. The values up to five colours were known from exhaustive search. Six colours is settled here: a 55-move solution exists, and a pruned search over 4.7 million states shows that 54 moves are not enough.
T(2), …, T(6) = 3, 10, 21, 36, 55。5 色までは全探索による既知の値。6 色はここで確定した。55 手の手順があり、54 手以内では解けないことを 471 万状態の枝刈り全探索で示した。
Every ball but one must move, and about half of the balls must move at least twice. The bound is proved by hand; three versions of it, each stronger than the last, are checked against exact distances on all 37 million states for four colours.
1 個を除くすべての玉は動かす必要があり、およそ半数の玉は 2 回以上動かす必要がある。証明は手で書いたもので、段階的に強くした 3 つの下界を、4 色の全 3,745 万状態で正確な距離と照合した。
The upper bound is an explicit solution. The lower bound comes from the same pruned search; each further move multiplies the number of states by about eight.
上界は実際の手順。下界は同じ枝刈り全探索による。証明する手数を 1 上げるごとに、状態数はおよそ 8 倍になる。
Each upper bound is a stored move sequence that a short script replays from the start. For 13 colours and more the sequences come from a construction and are far from the lower bound.
上界はどれも保存した手順で、短いスクリプトが最初から再生して確かめる。13 色以上の手順は組み立てによるもので、下界とはまだ大きく離れている。
| N | lower | upper | (2N−1)(N−1) | |
|---|---|---|---|---|
| 2 | 3 | 3 | exact | 3 |
| 3 | 10 | 10 | exact | 10 |
| 4 | 21 | 21 | exact | 21 |
| 5 | 36 | 36 | exact | 36 |
| 6 | 55 | 55 | exact | 55 |
| 7 | 75 | 78 | open | 78 |
| 8 | 95 | 106 | open | 105 |
| 9 | 117 | 140 | open | 136 |
| 10 | 145 | 179 | open | 171 |
| 11 | 175 | 224 | open | 210 |
| 12 | 208 | 272 | open | 253 |
| 13 | 245 | 329 | open | 300 |
| 14 | 285 | 387 | open | 351 |
| 15 | 328 | 457 | open | 406 |
| 16 | 374 | 525 | open | 465 |
| 17 | 423 | 625 | open | 528 |
| 18 | 475 | 719 | open | 595 |
| 19 | 530 | 853 | open | 666 |
| 20 | 588 | 992 | open | 741 |
| 21 | 649 | 1,114 | open | 820 |
| 22 | 713 | 1,355 | open | 903 |
| 23 | 780 | 1,568 | open | 990 |
| 24 | 850 | 1,672 | open | 1,081 |
| N | 下界 | 上界 | (2N−1)(N−1) | |
| 2 | 3 | 3 | 確定 | 3 |
| 3 | 10 | 10 | 確定 | 10 |
| 4 | 21 | 21 | 確定 | 21 |
| 5 | 36 | 36 | 確定 | 36 |
| 6 | 55 | 55 | 確定 | 55 |
| 7 | 75 | 78 | 未確定 | 78 |
| 8 | 95 | 106 | 未確定 | 105 |
| 9 | 117 | 140 | 未確定 | 136 |
| 10 | 145 | 179 | 未確定 | 171 |
| 11 | 175 | 224 | 未確定 | 210 |
| 12 | 208 | 272 | 未確定 | 253 |
| 13 | 245 | 329 | 未確定 | 300 |
| 14 | 285 | 387 | 未確定 | 351 |
| 15 | 328 | 457 | 未確定 | 406 |
| 16 | 374 | 525 | 未確定 | 465 |
| 17 | 423 | 625 | 未確定 | 528 |
| 18 | 475 | 719 | 未確定 | 595 |
| 19 | 530 | 853 | 未確定 | 666 |
| 20 | 588 | 992 | 未確定 | 741 |
| 21 | 649 | 1,114 | 未確定 | 820 |
| 22 | 713 | 1,355 | 未確定 | 903 |
| 23 | 780 | 1,568 | 未確定 | 990 |
| 24 | 850 | 1,672 | 未確定 | 1,081 |
Sources, move sequences and logs are on the data page.
根拠・手順・ログはデータのページにある。
The upper bounds depend only on a short replay script. The lower bounds for six and seven colours are computer-assisted: they rest on the written proof that the bound J never exceeds the true distance, on the check of J against exact distances for four colours, and on the correctness of one search program. That program has not been reimplemented independently.
上界は、短い再生スクリプトだけに拠る。6 色と 7 色の下界は計算機を使った証明で、下界 J が正確な距離を超えないことの証明(文章)、4 色での J と正確な距離の照合、そして 1 つの探索プログラムの正しさに拠る。このプログラムを独立に書き直しての確認は、まだしていない。
It is known that T(N) grows like N² (Szegedy and Yu). The constant is open: the lower bound gives 1.5.
T(N) が N² に比例して増えることは知られている(Szegedy と Yu)。係数は未解決で、下界からは 1.5 が出る。