|
問題1827・・・ひよこさんのブログ http://myhome.cururu.jp/gersdorffite/blog/article/70002841581 より Orz〜
簡単バージョンにしました...^^
次の条件を満たす5つの自然数の組を 1つ求めよ。
「条件」
5つの自然数のうち、どの2つをとっても、その差と 2つの最大公約数が一致する。
解答
上記サイトより Orz〜
・否定する者さんのもの Orz〜
一般の正整数を要素とする有限集合X(#X>1)
に対する条件を以下のように設定しなおす。
「条件」
∀a, b∈X (a≠b) a-b=gcd(a, b) が真である。
次の補題を証明する。
「補題」
ある正整数を要素とする有限集合{a_1, a_2, ... , a_k} (k>1)が条件を満たしていたとする。
このとき、c = lcm{a_1, a_2, ... , a_k} と定めて、
任意の正整数i(1≦i≦k)に対して、b_i = a_i+c と定めるならば、
A = {c, b_1, b_2, ... , b_k} とすることで、Aは条件を満たす。
(証明)
正整数を要素とする有限集合{a_1, a_2, ... , a_k} (k>1)が条件を満たしていたとし、
c = lcm{a_1, a_2, ... , a_k} と定めた上で、
任意の整数i(1≦i≦k)に対して、b_i = a_i+c と定めたとする。
まず、1≦t<s≦kなる任意の整数s, tに対して、
gcd(b_s, b_t) = b_s-b_t が成立していることを確認する。
gcd(b_s, b_t) = gcd(a_s+c, a_t+c) = gcd(a_s+c, a_s-a_t)
ここで、 a_s-a_t = gcd(a_s, a_t) より、 a_s-a_t│a_s│c であるから、
gcd(a_s+c, a_s-a_t) = a_s-a_t が成立する。
さらに a_s-a_t = (b_s-c)-(b_t-c) = b_s-b_t が成立するので、
よって確認できた。
最後に任意の整数i(1≦i≦k)に対して、gcd(b_i, c) = b_i-c の成立を確認する。
gcd(b_i, c) = gcd(a_i+c, c) = gcd(a_i, c) = a_i = (a_i+c)-(c) = b_i-c
よってこれも確認できた。
以上より、補題が示された。
なるほどたしかに♪ つまり、、、
帰納的に次々増やしていけるわけなんですね...^^
たとえば、、、(1,2) から始めたら、(2,3,4)→(12,14,15,16)→(1715,1727,1729,1730,1731)
でいいわけですね...^^
ちなみに、、、
否定する者さんは、、、
まず、 {36 40 42 45 48}とすれば、これは条件を満たす。 (要確認)
lcm{36 40 42 45 48 } = 5040 であるから、 補題より、
{5040, 5076, 5080, 5082, 5085, 5088}は条件を満たす。
lcm{5040, 5076, 5080, 5082, 5085, 5088} = 130804609652640 であるから、
{130804609652640, 130804609657680, 130804609657716,
130804609657720, 130804609657722, 130804609657725, 130804609657728}
とすれば、これは条件を満たす。
これの最小公倍数は以下の通り。
38341823281739089617388162
11341526459493306167372718
6862088355364084182627200 (77桁)
したがって、次の8つからなる自然数の組は本題の1つの解を与える。
(38341823281739089617388162113415264594
933061673727186862088355364084182627200,
383418232817390896173881621134152645949
33061673727186862088355494888792279840,
3834182328173908961738816211341526459
4933061673727186862088355494888792284880,
383418232817390896173881621134152645
94933061673727186862088355494888792284916,
383418232817390896173881621134152645
94933061673727186862088355494888792284920,
383418232817390896173881621134152645
94933061673727186862088355494888792284922,
383418232817390896173881621134152645
94933061673727186862088355494888792284925,
383418232817390896173881621134152645
94933061673727186862088355494888792284928)
ってな8個まで求められてます...^^;
それにしても、、、最初の、、、{36 40 42 45 48}はどうやって見つけられたんでしょうかねえ...
ここのサイトはすごい方々がいっぱいいらっしゃいます♪ ^^v
|