１７個の数 
当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんからの出題です。
（平成２３年１月２日付け）
連続する１７個の自然数の集合Ａで、次の条件を満たすものを作って下さい。
任意のＡの要素 ａ に対して、ａ と互いに素でないような ａ とは異なるＡの要素
が必ず存在する
※ １７個は、このような集合Ａが存在するための最小の数だそうです。手計算で作るの
は難しいかもしれません。
（答え） 当ＨＰの掲示板「出会いの泉」に、中学生のＨＮ「ぽっぽ」さんが、
２７８３０＋３００３０ｎ 〜 ２７８４６＋３００３０ｎ （ｎは自然数）
と、手計算で求められた。（平成２３年１月２日付け）
（コメント） 手計算とはスゴイですね！私は、Ｅｘｃｅｌ のＶＢＡで解を探索しましたが、下記に
あるＦＮさんの解を素通りしてしまいました。再度挑戦したら、確かに「１７個の数」
が発見できました。
|
この１７個の数は、ぽっぽさんの一般解で、ｎ＝−１とし、全体を（−１）倍しても得られる。
ＦＮさんからのコメントです。（平成２３年１月２日付け）
手計算では難しいかと思っていたのですが、手計算で出ましたか。しかも中学生ですか。
びっくりしました。さらに解が1つ出ればいいつもりだったのですが一般解ですね。よかった
らどのようにして出したかを教えてください。
私は自分では解いてません。プログラムを書けば出るだろうなと思いながら何もしてませ
ん。答えとして書いてあるのは、２１８４、２１８５、・・・２２００です。
これに、３００３０（＝２・３・５・７・１１・１３）の倍数を足したものは、すべて答えになります。
ぽっぽさんによる解説です。（平成２３年１月２日付け）・・・・説明を一部補充。
あてはめただけなので、他の解のことは考えていませんでした。やり方です。
ａ1、ａ2、ａ3、ａ4、ａ5、ａ6、ａ7、ａ8、ａ9、ａ10、ａ11、ａ12、ａ13、ａ14、ａ15、ａ16、ａ17
を考えた時、まず、ａ1を２の倍数とすると、ａ1、ａ3、ａ5、ａ7、ａ9、ａ11、ａ13、ａ15、ａ17 が条件
を満たす。次に、ａ2を３の倍数とすると、上記以外の数で、ａ2、ａ8、ａ14 が条件を満たす。
ここで、残る数は、ａ4、ａ6、ａ10、ａ12、ａ16 である。このとき、ａ6を５の倍数にすると、
ａ6、ａ16と条件を満たす数が最も多い。ここで、ａ4、ａ10、ａ12が残る。
ａ4が１３の倍数でなければ、１３の倍数が１つしかなくなるから、ａ4を１３の倍数とする。
同じように、ａ12が１１の倍数でなければ、１１の倍数が１つしかなくなるから、ａ12を１１の倍
数とする。残ったａ10が７の倍数になる。
このとき、 ａ1は２の倍数
ａ2は３の倍数より、ａ1を３で割った余りは２
ａ6は５の倍数より、ａ1を５で割った余りは０
ａ10は７の倍数より、ａ1を７で割った余りは５
ａ12は１１の倍数より、ａ1を１１で割った余りは０
ａ4は１３の倍数より、ａ1を１３で割った余りは１０
である。このとき、Ｇａｕｓｓ
の方法（→参考：「連立合同式」）により、
ｍ＝２・３・５・７・１１・１３＝３００３０ とおき、
Ｐ＝１５０１５、Ｑ＝１００１０、Ｒ＝６００６、Ｓ＝４２９０、Ｔ＝２７３０、Ｕ＝２３１０
とすると、
１５０１５Ａ≡１ （ｍｏｄ ２） を満たすＡは、 Ａ＝１
１００１０Ｂ≡１ （ｍｏｄ ３） を満たすＢは、 Ｂ＝２
６００６Ｃ≡１ （ｍｏｄ ５） を満たすＣは、 Ｃ＝１
４２９０Ｄ≡１ （ｍｏｄ ７） を満たすＤは、 Ｄ＝−１
２７３０Ｅ≡１ （ｍｏｄ １１） を満たすＥは、 Ｅ＝−５
２３１０Ｆ≡１ （ｍｏｄ １３） を満たすＦは、 Ｆ＝３
なので、３００３０を法として、
ａ1≡０・１５０１５・１＋２・１００１０・２＋０・６００６・１
＋５・４２９０・（−１）＋０・２７３０・（−５）＋１０・２３１０・３
≡２・１００１０・２＋５・４２９０・（−１）＋１０・２３１０・３
≡４００４０−２１４５０＋６９３００
≡８７８９０
≡２７８３０
よって、 ａ1＝２７８３０＋３００３０ｎ （ｎ は整数）
※まさに当てはめなのでもっと他の解を考えてみます。
ぽっぽさんの解説に対して、当ＨＰがいつもお世話になっているＨＮ「攻略法」さんの考
察です。（平成２３年１月５日付け）
連立合同式で解く場合、合同式を抜けがなくつくるのが大変です。
●考察 １７個の場合、条件を満たす集合は
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
の１通りとなる。この表から、連立合同式を組み立てることになる。
連立合同式
ａ1≡０ （ｍｏｄ ２） 、ａ1≡２ （ｍｏｄ ３） 、ａ1≡０ （ｍｏｄ ５） 、
ａ1≡５ （ｍｏｄ ７） 、ａ1≡０ （ｍｏｄ １１） 、ａ1≡１０ （ｍｏｄ １３）
より、
２７８３０＋３００３０ｎ （ｎ は０以上の整数）から始まる１７個の連続する自然数
また、ａ17 を先頭とする、逆の並びも有効なので、もう１つは、
連立合同式
ａ17≡０ （ｍｏｄ ２） 、ａ17≡０ （ｍｏｄ ３） 、ａ17≡４ （ｍｏｄ ５） 、
ａ17≡０ （ｍｏｄ ７） 、ａ17≡６ （ｍｏｄ １１） 、ａ17≡０ （ｍｏｄ １３）
より、
２１８４＋３００３０ｎ （ｎ は０以上の整数）から始まる１７個の連続する自然数
ところで、ａ1(またはａ17)の候補は、２・３・５・７・１１・１３通りある。このことは、上の
「６つの連立合同式を組み立てて解く」と言うより、
ｘ≡ｉ （ｍｏｄ ３００３０） ｉ＝０〜３００２９ の ｉ を探す
ことを意味する。すなわち、機械的な総当りである。手計算では難しい。手計算では、
表（合同式）がいくつ作れるかがパズル的要素となる。
実際にExcelVBAで求めてみた。
|
Sub test() Let K = 17 '連続するK個 Let iter = 30030 'K未満の素数 2 * 3 * 5 * 7 * 11 * 13 Let c = 0 For n = 2 To iter - 1 '２以上の自然数について Let t = n + K - 1 For i = n To t '他の要素と比較する For j = n To t If i = j Then Else If gcd(i, j) <> 1 Then Exit For 'ひとつでも「互いに素でない」があればよい End If Next j If j > t Then Exit For '互いに素のものがある Next i If i > t Then '題意を満たすなら、結果を表示する For i = n To t: Debug.Print i;: Next i: Debug.Print Let c = c + 1 End If Next n If c = 0 Then Debug.Print "解なし" Else Debug.Print c; "組" End Sub Function gcd(ByVal aa, ByVal bb) '最大公約数 While bb <> 0 t = bb bb = aa Mod bb aa = t Wend gcd = aa End Function |
ぽっぽさんの解説に対して、ＦＮさんからのコメントです。（平成２３年１月２日付け）
なるほど。できそうですね。きちんとやれば、すべてを求めることができるかもしれません。
では、次は逆の方向を考えてみてください。即ち、
このような集合が存在するのは、１６個以下では不可能である
ことの証明です。ある程度似たようなものでしょうから、すべてをするのはやめましょう。次
の２つを証明してください。
(１) 連続する１０個の自然数の集合Ａがある。このときＡの要素で他のすべてのＡの要
素と互いに素であるようなものが必ず存在する。
(２) 連続する１６個の自然数の集合Ａがある。このときＡの要素で他のすべてのＡの要
素と互いに素であるようなものが必ず存在する。
(１)は比較的簡単だと思います。(２)はぎりぎりの結果(１６を１７以上には変えられない)なの
でかなり難しいと思います。
ＦＮさんの問いかけに対して、ぽっぽさんからの回答です。（平成２３年１月２日付け）
（１）場合は、５＋２＋１＋１＜１０ ということでよろしいでしょうか？
（２） ２の倍数、３の倍数を除いたものは次の６通りある。
ａ1、ａ3、ａ7、ａ9、ａ13、ａ15
ａ1、ａ5、ａ7、ａ11、ａ13
ａ3、ａ5、ａ9、ａ11、ａ15
ａ2、ａ4、ａ8、ａ10、ａ14、ａ16
ａ2、ａ6、ａ8、ａ12、ａ14
ａ4、ａ6、ａ10、ａ12、ａ16
残りで使える要素は、５の倍数、７の倍数、１１の倍数、１３の倍数の４つである。
ａ1、ａ3、ａ7、ａ9、ａ13、ａ15 のとき、
まず、必ず５の倍数２つ、７の倍数は２つ、１１の倍数は１つ、１３の倍数は１つなければな
らないから、ａ1は７の倍数、ａ3は５の倍数。従って、このとき、ａ7かａ9は13の倍数でなければ
ならないが、このとき集合Ａの中に13の倍数が２つあることはない。
よって不可能。
ａ1、ａ5、ａ7、ａ11、ａ13 のとき、
まず、必ず５の倍数は２つ、７の倍数は１つ、１１の倍数は１つ、１３の倍数は１つなければ
ならないから、ａ1は５の倍数。従って、このとき、ａ5かａ7かａ13は１３の倍数でなけらばならな
いが、このとき集合Ａの中に１３の倍数が２つあることはない。
よって不可能。
ａ3、ａ5、ａ9、ａ11、ａ15 のとき、
まず、必ず５の倍数は２つ、７の倍数は１つ、１１の倍数は１つ、１３の倍数は１つなければ
ならないから、ａ5は５の倍数。このとき、ａ3は１３の倍数になり、ａ9かａ11は１１の倍数でなけ
らばならないが、このとき集合Ａの中に１３の倍数が２つあることはない。
よって不可能。
ａ2、ａ4、ａ8、ａ10、ａ14、ａ16 のとき、
ａ1、ａ5、ａ7、ａ11、ａ13 のときと同じようにして不可能。
ａ2、ａ6、ａ8、ａ12、ａ14 のとき、
ａ1、ａ5、ａ7、ａ11、ａ13 のときと同じようにして不可能。
ａ4、ａ6、ａ10、ａ12、ａ16 のとき、
ａ1、ａ5、ａ7、ａ11、ａ13 のときと同じようにして不可能。
ところで、１７以上のとき、必ず満たすということは示せるのでしょうか？もし、示せたら、
次のようなことが分かりますね。
ｎ以下の素数の積をｍとしたとき、ｍ以下の連続する２素数の差がｎ以上になること
が必ずある
（コメント） ２の倍数、３の倍数を除いたものとして、
ａ1、ａ5、ａ7、ａ11、ａ13 → ａ1、ａ5、ａ7、ａ11、ａ13、ａ17
ａ3、ａ5、ａ9、ａ11、ａ15 → ａ3、ａ5、ａ9、ａ11、ａ15、ａ17
ではないのかな？証明が成立しないような．．．予感？
ぽっぽさんの回答に対して、ＦＮさんからのコメントです。（平成２３年１月２日付け）
（１）について、ある程度この問題を考えた人にはそれでわかるかとは思いますが、証明と
なるともう少し書いた方がいいと思います。例えば次ぐらいに．．．。
Ａの２つの要素の公約数になりうる素数は、９以下だから、２、３、５、７のどれかである。
「他のすべてのＡの要素と互いに素である」を性質Ｐとする。偶数は、性質Ｐを持たない。
以下、奇数５個について考える。そのうち、３の倍数は高々２個である。５の倍数は丁度１個
ある。７の倍数は高々１個ある。従って、３、５、７のどの倍数でもない奇数が存在する。
この数は性質Ｐを満たす。
(２)は、(１)に比べたら相当に難しいので(私もきちんと証明を書いてるわけではない)、上の
ような丁寧な解答は書けないし、書く必要もないでしょう。
上の場合分けですが、初項を５で割った余りがそれぞれ ５、１、３、４、０、２ の場合のよ
うですが、この順に並んでいるのがわかりにくいのではないかと思います。あるいは、別の
考え方をすれば自然な並び方なのでしょうか。
証明はすべて確認したわけではありませんが多分正しいと思います。
「5+2+1+1＜10」の形の式で書けば、「8+3+2+2++1+1+1=17＞16」とと逆向きの不等式です。
「5+2+1+1＜10」の向きの不等式が成り立つのは、ｋ＝１０の他には、ｋ≦7だけです。それ以外
は等号が成り立つのはまだいいほうで、逆向きの不等式になる場合が多いです。従って、すっ
きりした証明にはならないようです。
（参考） 出典： http://projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf
２ページのSolution-O51のところで連続する１６個の自然数の中に、２、３、５、７、１１、１３
のいずれでも割れない数が存在することを証明してしまっているのですが、これは成立しま
せん。前の問題の解答である ２１８４、２１８５、・・・、２２００の前の１６個とかが反例になり
ます。
ぽっぽさんの「１７以上のとき、必ず満たすということは示せるのでしょうか？」については
前に提示した論文にProposition1.2として書いてあります。１９４１年に証明されているよ
うです。
素人に証明できるレベルかどうかはわかりません。ｋ＝17のときの解
±{２１８４、２１８５、・・・、２２００}＋３００３０ｎ
の ｎ をうまくとって前後につけ足して作れればいいのですが、そんなに簡単にはいかない
のかなと思います。
これを問題にしましょう。１７のときは成り立ってるので、１８以上にします。
ｋは１８以上の自然数とする。連続するｋ個の自然数の集合Ａで次の条件を満たす
ものは存在するか。
任意のＡの要素ａに対して、ａと互いに素でないようなａと異なるＡの要素が必ず
存在する。
証明を眺めてみたら、とても手に負えるものではありませんでした。
また、ぽっぽさんの「１７以上のとき、必ず満たすということが示せたら、
ｎ以下の素数の積をｍとしたとき、ｍ以下の連続する２素数の差がｎ以上になること
が必ずある
も分かりますね」について、確かに成り立ちますね。系として
隣り合う２つの素数の差はいくらでも大きくなりうる
が出ますがこれはよく知られています。
以下、工事中