ネックレス問題(関口晃司氏出題)
n点のリングに自然数を割り当てて,連続する部分の和が1からn(n−1)+1までの数全てを表すことが出来るか?
(連続していない数は和をとることができません)
(例)
n=3 のとき,
3個の(三角形)リングに,それぞれ順に 1,2,4 を割り当てると,
1 ← そのまま, 2 ← そのまま, 3 ← 1+2, 4 ← そのまま, 5 ← 1+4, 6 ← 2+4, 7 ← 1+2+4
n=4のとき
4個の(四角形)リングに,それぞれ順に 1,3,2,7 を割り当てると,
1 ← そのまま, 2 ← そのまま, 3 ← そのまま, 4 ← 1+3, 5 ← 3+2, 6 ← 1+2+3, 7 ← そのまま, 8 ← 7+1, 9 ← 2+7, 10 ← 2+7+1, 11 ← 7+3+1, 12 ← 3+2+7, 13 ← 1+3+2+7
注)一般に取扱われている,心理学上で有名な「(安い)ネックレス問題」とは異なります。
宮田大輔氏による実験報告(2001.03.28現在)
解の数について
n: 解の数 3: 1 4: 2 5: 1 6: 5 7: 0 8: 6 9: 4 10: 6 11: 0 12: 18 13: 0 14: 20 15: 0 16: 0 17: あり。個数については未確定 18: ?? 解の配置について 注)解の回転・対称については無視 n=3 1 2 4 n=4 1 2 6 4 1 3 2 7 n=5 1 5 2 10 3 n=6 1 2 5 4 6 13 1 2 7 4 12 5 1 3 2 7 8 10 1 3 6 2 5 14 1 7 3 2 4 14 n=8 1 2 10 19 4 7 9 5 1 8 2 3 21 4 12 6 1 12 2 6 3 7 22 4 1 4 2 10 18 3 11 8 1 3 8 2 16 7 15 5 1 3 5 11 2 12 17 6 n=9 1 2 4 8 16 5 18 9 10 1 16 22 2 3 4 6 8 11 1 8 12 2 3 13 24 4 6 1 14 8 2 28 3 6 7 4 n=10 1 2 6 18 22 7 5 16 4 10 1 36 2 12 7 8 3 13 4 5 1 4 2 20 8 9 23 10 3 11 1 18 3 2 8 4 29 11 9 6 1 4 3 10 2 9 14 16 6 26 1 18 28 5 2 8 6 11 9 3 n=12 1 2 14 4 37 7 8 27 5 6 13 9 1 2 9 8 14 4 43 7 6 10 5 24 1 2 12 31 25 4 9 10 7 11 16 5 1 2 14 12 32 19 6 5 4 18 13 7 1 7 2 22 4 16 3 11 29 21 12 5 1 11 2 8 7 25 6 3 27 20 19 4 1 6 2 33 17 14 12 10 15 3 16 4 1 14 3 2 4 7 21 8 25 10 12 26 1 31 10 2 4 3 8 13 5 20 14 22 1 9 48 2 4 18 5 11 3 12 13 7 1 8 5 2 18 11 10 22 6 24 23 3 1 6 28 2 13 16 23 19 5 9 8 3 1 3 12 34 21 2 8 9 5 6 7 25 1 4 7 3 16 2 6 17 20 9 13 35 1 35 26 3 11 2 4 21 7 5 10 8 1 15 5 3 25 2 7 4 6 12 14 39 1 41 8 4 17 2 3 6 7 20 10 14 1 7 6 16 15 2 9 10 40 3 20 4 n=14 1 2 21 17 11 5 9 4 26 6 47 15 12 7 1 2 13 7 5 14 34 6 4 33 18 17 21 8 1 2 28 14 5 6 9 12 48 18 4 13 16 7 1 10 2 16 32 20 3 21 33 5 4 22 8 6 1 5 2 24 15 29 14 21 13 4 33 3 9 10 1 15 34 2 3 17 7 6 8 4 19 9 48 10 1 4 20 2 12 3 6 7 33 11 8 10 35 31 1 12 48 6 2 38 3 22 7 10 11 5 4 14 1 33 14 36 2 16 6 5 8 4 3 25 21 9 1 12 11 6 2 18 16 35 21 4 3 40 5 9 1 9 8 28 2 24 5 6 44 14 20 7 12 3 1 25 23 4 10 2 3 17 11 7 6 45 21 8 1 9 14 26 4 2 11 5 3 12 27 34 7 28 1 19 16 5 8 2 7 55 11 14 12 6 24 3 1 12 22 7 17 2 18 10 23 32 25 6 5 3 1 4 6 31 3 13 2 7 14 12 17 46 8 19 1 17 8 5 24 14 2 4 3 12 27 34 22 10 1 8 16 10 12 19 2 11 4 3 42 27 23 5 1 18 7 17 15 14 2 4 56 5 23 10 3 8 1 4 8 52 3 25 18 2 9 24 6 10 7 14