17個の数                                  戻る

 当HPがいつもお世話になっているHN「FN」さんからの出題です。
                                       (平成23年1月2日付け)

 連続する17個の自然数の集合Aで、次の条件を満たすものを作って下さい。

  
任意のAの要素 a に対して、a と互いに素でないような a とは異なるAの要素
 が必ず存在する


 ※ 17個は、このような集合Aが存在するための最小の数だそうです。手計算で作るの
   は難しいかもしれません。

































(答え) 当HPの掲示板「出会いの泉」に、中学生のHN「ぽっぽ」さんが、

       27830+30030n 〜 27846+30030n  (nは自然数)

   と、手計算で求められた。(平成23年1月2日付け)

(コメント) 手計算とはスゴイですね!私は、Excel のVBAで解を探索しましたが、下記に
      あるFNさんの解を素通りしてしまいました。再度挑戦したら、確かに「17個の数」
      が発見できました。

        
2184 2x2x2x3x7x13
2185 5x19x23
2186 2x1093
2187 3x3x3x3x3x3x3
2188 2x2x547
2189 11x199
2190 2x3x5x73
2191 7x313
2192 2x2x2x2x137
10 2193 3x17x43
11 2194 2x1097
12 2195 5x439
13 2196 2x2x3x3x61
14 2197 13x13x13
15 2198 2x7x157
16 2199 3x733
17 2200 2x2x2x5x5x11

 この17個の数は、ぽっぽさんの一般解で、n=−1とし、全体を(−1)倍しても得られる。

 FNさんからのコメントです。(平成23年1月2日付け)

 手計算では難しいかと思っていたのですが、手計算で出ましたか。しかも中学生ですか。
びっくりしました。さらに解が1つ出ればいいつもりだったのですが一般解ですね。よかった
らどのようにして出したかを教えてください。

 私は自分では解いてません。プログラムを書けば出るだろうなと思いながら何もしてませ
ん。答えとして書いてあるのは、2184、2185、・・・2200です。
これに、30030(=2・3・5・7・11・13)の倍数を足したものは、すべて答えになります。


 ぽっぽさんによる解説です。(平成23年1月2日付け)・・・・説明を一部補充。

 あてはめただけなので、他の解のことは考えていませんでした。やり方です。

  a1、a2、a3、a4、a5、a6、a7、a8、a9、a10、a11、a12、a13、a14、a15、a16、a17

を考えた時、まず、a1を2の倍数とすると、a1、a3、a5、a7、a9、a11、a13、a15、a17 が条件

を満たす。次に、a2を3の倍数とすると、上記以外の数で、a2、a8、a14 が条件を満たす。

 ここで、残る数は、a4、a6、a10、a12、a16 である。このとき、a6を5の倍数にすると、

6、a16と条件を満たす数が最も多い。ここで、a4、a10、a12が残る。

 a4が13の倍数でなければ、13の倍数が1つしかなくなるから、a4を13の倍数とする。

同じように、a12が11の倍数でなければ、11の倍数が1つしかなくなるから、a12を11の倍

数とする。残ったa10が7の倍数になる。

 このとき、 a1は2の倍数

        a2は3の倍数より、a1を3で割った余りは2

        a6は5の倍数より、a1を5で割った余りは0

        a10は7の倍数より、a1を7で割った余りは5

        a12は11の倍数より、a1を11で割った余りは0

        a4は13の倍数より、a1を13で割った余りは10

である。このとき、Gauss の方法(→参考:「連立合同式」)により、

 m=2・3・5・7・11・13=30030 とおき、

  P=15015、Q=10010、R=6006、S=4290、T=2730、U=2310

とすると、

  15015A≡1 (mod 2) を満たすAは、 A=1

  10010B≡1 (mod 3) を満たすBは、 B=2

   6006C≡1 (mod 5) を満たすCは、 C=1

   4290D≡1 (mod 7) を満たすDは、 D=−1

   2730E≡1 (mod 11) を満たすEは、 E=−5

   2310F≡1 (mod 13) を満たすFは、 F=3

なので、30030を法として、

 a1≡0・15015・1+2・10010・2+0・6006・1
                    +5・4290・(−1)+0・2730・(−5)+10・2310・3

  ≡2・10010・2+5・4290・(−1)+10・2310・3

  ≡40040−21450+69300

  ≡87890

  ≡27830

 よって、 a1=27830+30030n (n は整数)

 ※まさに当てはめなのでもっと他の解を考えてみます。


  ぽっぽさんの解説に対して、当HPがいつもお世話になっているHN「攻略法」さんの考
 察です。(平成23年1月5日付け)

  連立合同式で解く場合、合同式を抜けがなくつくるのが大変です。

 ●考察  17個の場合、条件を満たす集合は

   
表 倍数の分布(ぽっぽさんが解説された方法)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
2* 2 2 2 2 2 2 2 2
3* 3 3 3 3 3
5 5* 5 5
13* 13
11 11*
7 7* 7

    の1通りとなる。この表から、連立合同式を組み立てることになる。

     連立合同式

      a1≡0 (mod 2) 、a1≡2 (mod 3) 、a1≡0 (mod 5) 、

      a1≡5 (mod 7) 、a1≡0 (mod 11) 、a1≡10 (mod 13)

    より、

     27830+30030n (n は0以上の整数)から始まる17個の連続する自然数

    また、a17 を先頭とする、逆の並びも有効なので、もう1つは、

     連立合同式

      a17≡0 (mod 2) 、a17≡0 (mod 3) 、a17≡4 (mod 5) 、

      a17≡0 (mod 7) 、a17≡6 (mod 11) 、a17≡0 (mod 13)

    より、

     2184+30030n (n は0以上の整数)から始まる17個の連続する自然数

     ところで、a1(またはa17)の候補は、2・3・5・7・11・13通りある。このことは、上の
    「6つの連立合同式を組み立てて解く」と言うより、

      x≡i (mod 30030) i=0〜30029 の i を探す

    ことを意味する。すなわち、機械的な総当りである。手計算では難しい。手計算では、
    表(合同式)がいくつ作れるかがパズル的要素となる。

      実際に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 '2以上の自然数について
   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

 ぽっぽさんの解説に対して、FNさんからのコメントです。(平成23年1月2日付け)

 なるほど。できそうですね。きちんとやれば、すべてを求めることができるかもしれません。
では、次は逆の方向を考えてみてください。即ち、

  このような集合が存在するのは、16個以下では不可能である

ことの証明です。ある程度似たようなものでしょうから、すべてをするのはやめましょう。次
の2つを証明してください。

 (1) 連続する10個の自然数の集合Aがある。このときAの要素で他のすべてのAの要
   素と互いに素であるようなものが必ず存在する。

 (2) 連続する16個の自然数の集合Aがある。このときAの要素で他のすべてのAの要
   素と互いに素であるようなものが必ず存在する。

(1)は比較的簡単だと思います。(2)はぎりぎりの結果(16を17以上には変えられない)なの
でかなり難しいと思います。


  FNさんの問いかけに対して、ぽっぽさんからの回答です。(平成23年1月2日付け)

 (1)場合は、5+2+1+1<10 ということでよろしいでしょうか?

 (2) 2の倍数、3の倍数を除いたものは次の6通りある。

    a1、a3、a7、a9、a13、a15

    a1、a5、a7、a11、a13

    a3、a5、a9、a11、a15

    a2、a4、a8、a10、a14、a16

    a2、a6、a8、a12、a14

    a4、a6、a10、a12、a16

 残りで使える要素は、5の倍数、7の倍数、11の倍数、13の倍数の4つである。

 a1、a3、a7、a9、a13、a15 のとき、

 まず、必ず5の倍数2つ、7の倍数は2つ、11の倍数は1つ、13の倍数は1つなければな
らないから、a1は7の倍数、a3は5の倍数。従って、このとき、a7かa9は13の倍数でなければ
ならないが、このとき集合Aの中に13の倍数が2つあることはない。
 よって不可能。

 a1、a5、a7、a11、a13 のとき、

 まず、必ず5の倍数は2つ、7の倍数は1つ、11の倍数は1つ、13の倍数は1つなければ
ならないから、a1は5の倍数。従って、このとき、a5かa7かa13は13の倍数でなけらばならな
いが、このとき集合Aの中に13の倍数が2つあることはない。
 よって不可能。

 a3、a5、a9、a11、a15 のとき、

 まず、必ず5の倍数は2つ、7の倍数は1つ、11の倍数は1つ、13の倍数は1つなければ
ならないから、a5は5の倍数。このとき、a3は13の倍数になり、a9かa11は11の倍数でなけ
らばならないが、このとき集合Aの中に13の倍数が2つあることはない。
 よって不可能。

 a2、a4、a8、a10、a14、a16 のとき、

  a1、a5、a7、a11、a13 のときと同じようにして不可能。

 a2、a6、a8、a12、a14 のとき、

  a1、a5、a7、a11、a13 のときと同じようにして不可能。

 a4、a6、a10、a12、a16 のとき、

  a1、a5、a7、a11、a13 のときと同じようにして不可能。

 ところで、17以上のとき、必ず満たすということは示せるのでしょうか?もし、示せたら、
次のようなことが分かりますね。

 n以下の素数の積をmとしたとき、m以下の連続する2素数の差がn以上になること
が必ずある



(コメント) 2の倍数、3の倍数を除いたものとして、

    a1、a5、a7、a11、a13 → a1、a5、a7、a11、a13、a17

    a3、a5、a9、a11、a15 → a3、a5、a9、a11、a15、a17

  ではないのかな?証明が成立しないような...予感?


 ぽっぽさんの回答に対して、FNさんからのコメントです。(平成23年1月2日付け)

 (1)について、ある程度この問題を考えた人にはそれでわかるかとは思いますが、証明と
なるともう少し書いた方がいいと思います。例えば次ぐらいに...。

 Aの2つの要素の公約数になりうる素数は、9以下だから、2、3、5、7のどれかである。

「他のすべてのAの要素と互いに素である」を性質Pとする。偶数は、性質Pを持たない。
以下、奇数5個について考える。そのうち、3の倍数は高々2個である。5の倍数は丁度1個
ある。7の倍数は高々1個ある。従って、3、5、7のどの倍数でもない奇数が存在する。
この数は性質Pを満たす。

 (2)は、(1)に比べたら相当に難しいので(私もきちんと証明を書いてるわけではない)、上の
ような丁寧な解答は書けないし、書く必要もないでしょう。

 上の場合分けですが、初項を5で割った余りがそれぞれ 5、1、3、4、0、2 の場合のよ
うですが、この順に並んでいるのがわかりにくいのではないかと思います。あるいは、別の
考え方をすれば自然な並び方なのでしょうか。

 証明はすべて確認したわけではありませんが多分正しいと思います。

 「5+2+1+1<10」の形の式で書けば、「8+3+2+2++1+1+1=17>16」とと逆向きの不等式です。
「5+2+1+1<10」の向きの不等式が成り立つのは、k=10の他には、k≦7だけです。それ以外
は等号が成り立つのはまだいいほうで、逆向きの不等式になる場合が多いです。従って、すっ
きりした証明にはならないようです。

(参考) 出典: http://projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf

 2ページのSolution-O51のところで連続する16個の自然数の中に、2、3、5、7、11、13
のいずれでも割れない数が存在することを証明してしまっているのですが、これは成立しま
せん。前の問題の解答である 2184、2185、・・・、2200の前の16個とかが反例になり
ます。

 ぽっぽさんの「17以上のとき、必ず満たすということは示せるのでしょうか?」については
前に提示した論文にProposition1.2として書いてあります。1941年に証明されているよ
うです。

 素人に証明できるレベルかどうかはわかりません。k=17のときの解

   ±{2184、2185、・・・、2200}+30030n

の n をうまくとって前後につけ足して作れればいいのですが、そんなに簡単にはいかない
のかなと思います。

 これを問題にしましょう。17のときは成り立ってるので、18以上にします。

 kは18以上の自然数とする。連続するk個の自然数の集合Aで次の条件を満たす
ものは存在するか。

 任意のAの要素aに対して、aと互いに素でないようなaと異なるAの要素が必ず
存在する。


 証明を眺めてみたら、とても手に負えるものではありませんでした。

 また、ぽっぽさんの「17以上のとき、必ず満たすということが示せたら、

 n以下の素数の積をmとしたとき、m以下の連続する2素数の差がn以上になること
が必ずある


も分かりますね」について、確かに成り立ちますね。系として

 隣り合う2つの素数の差はいくらでも大きくなりうる

が出ますがこれはよく知られています。



   以下、工事中