平成20年10月5日
[流れ星]
第213回数学的な応募問題解答
<解答募集期間:9月14日〜10月5日
[最小公倍数]
皆さん、今年の大分大学医学部の入試問題を改題して出題します。
NO1 「uchinyan」 9/15 13時02分受信
更新10/5
第213回数学的な応募問題
[最小公倍数]
一般に,a, b, a < b の最大公約数を g とすると,c, d を互いに素な整数として,
a = gc, b = gd, c < d, A
= gcd, A/g = cd, c^2 <
A/g < d^2, 1 <= c < sqrt(A/g) < d
になります。つまり,a, b の最大公約数 g は,A の約数で,
c = a/g は 1 以上 sqrt(A/g) より小で A/g の約数です。
d はこの c から d = A/gc = A/a, ただし c, d は互いに素,として求まります。
a, b は,これら c, d から a = gc, b = gd として求まります。
そして,N(A) は,この a, b の個数から求められますが,結局は,c の個数に等しくなります。
以下,これらのことを踏まえて考えてみます。
問題1 N(6)
A = 6 = 2 * 3, g = 1, 2, 3, 6
g = 1, A/g = 6 = cd, 1 <= c < sqrt(6) < 3, (c,d) = (1,6),
(2,3), (a,b) = (1,6), (2,3)
g = 2, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (2,6)
g = 3, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (3,6)
g = 6, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(6) = 2 + 1 + 1 + 0 = 4
問題2 N(15)
A = 15 = 3 * 5, g = 1, 3, 5, 15
g = 1, A/g = 15 = cd, 1 <= c < sqrt(15) < 4, (c,d) = (1,15),
(3,5), (a,b) = (1,15), (3,5)
g = 3, A/g = 5 = cd, 1 <= c < sqrt(5) < 3, (c,d) = (1,5), (a,b) = (3,15)
g = 5, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (5,15)
g = 15, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(15) = 2 + 1 + 1 + 0 = 4
問題3 N(35)
A = 35 = 5 * 7, g = 1, 5, 7, 35
g = 1, A/g = 35 = cd, 1 <= c < sqrt(35) < 6, (c,d) = (1,35),
(5,7), (a,b) = (1,35), (5,7)
g = 5, A/g = 7 = cd, 1 <= c < sqrt(7) < 3, (c,d) = (1,7), (a,b) = (5,35)
g = 7, A/g = 5 = cd, 1 <= c < sqrt(5) < 3, (c,d) = (1,5), (a,b) = (7,35)
g = 35, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(35) = 2 + 1 + 1 + 0 = 4
問題4 N(105)
A = 105 = 3 * 5 * 7, g = 1, 5, 7, 35, 3, 15, 21, 105
以下は,A/g が問題3 の 3 倍になっています。
g = 1, A/g = 105 = cd, 1 <= c < sqrt(105) < 11, (c,d) =
(1,105), (3,35), (5,21), (7,15),
(a,b) = (1,15), (3,35), (5,21), (7,15)
g = 5, A/g = 21 = cd, 1 <= c < sqrt(21) < 5, (c,d) = (1,21),
(3,7), (a,b) = (5,105), (15,35)
g = 7, A/g = 15 = cd, 1 <= c < sqrt(15) < 4, (c,d) = (1,15),
(3,5), (a,b) = (7,105), (21,35)
g = 35, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (35,105)
以下は,g が 3 の倍数ですが,A/g = cd は,問題3 と同じになります。
g = 3, A/g = 35 = cd, 1 <= c < sqrt(35) < 6, (c,d) = (1,35),
(5,7), (a,b) = (3,105), (15,21)
g = 15, A/g = 7 = cd, 1 <= c < sqrt(7) < 3, (c,d) = (1,7), (a,b) = (15,105)
g = 21, A/g = 5 = cd, 1 <= c < sqrt(5) < 3, (c,d) = (1,5), (a,b) = (21,105)
g = 105, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(105) = 4 + 2 + 2 + 1 + 4 = 13
問題5 N(210)
A = 210 = 2 * 3 * 5 * 7, g = 1, 3, 5, 7, 15. 21. 35, 105, 2, 6, 10, 14, 30, 42,
70, 210
以下は,A/g が問題4 の 2 倍になっています。
g = 1, A/g = 210 = cd, 1 <= c < sqrt(210) < 15,
(c,d) = (1,210), (2,105), (3,70), (5,42), (6,35),
(7,30), (10,21), (14,15),
(a,b) = (1,210), (2,105), (3,70), (5,42), (6,35),
(7,30), (10,21), (14,15)
g = 3, A/g = 70 = cd, 1 <= c < sqrt(70) < 9, (c,d) = (1,70),
(2,35), (5,14), (7,10),
(a,b) = (3,210), (6,105), (15,42), (21,30)
g = 5, A/g = 42 = cd, 1 <= c < sqrt(42) < 7, (c,d) = (1,42),
(2,21), (3,14), (6,7),
(a,b) = (5,210), (10,105), (15,70), (30,35)
g = 7, A/g = 30 = cd, 1 <= c < sqrt(30) < 6, (c,d) = (1,30),
(2,15), (3,10), (5,6),
(a,b) = (7,210), (14,105), (21,70), (35,42)
g = 15, A/g = 14 = cd, 1 <= c < sqrt(14) < 4, (c,d) = (1,14),
(2,7), (a,b) = (15,210), (30,105)
g = 21, A/g = 10 = cd, 1 <= c < sqrt(10) < 4, (c,d) = (1,10),
(2,5), (a,b) = (21,210), (42,105)
g = 35, A/g = 6 = cd, 1 <= c < sqrt(6) < 3, (c,d) = (1,6),
(2,3), (a,b) = (35,210), (70,105)
g = 105, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (105,210)
以下は,g が 2 の倍数ですが,A/g = cd は,問題4 と同じになります。
g = 2, A/g = 105 = cd, 1 <= c < sqrt(105) < 11, (c,d) =
(1,105), (3,35), (5,21), (7,15),
(a,b) = (2,210), (6,70), (10,42), (14,30)
g = 10, A/g = 21 = cd, 1 <= c < sqrt(21) < 5, (c,d) = (1,21),
(3,7), (a,b) = (10,210), (30,70)
g = 14, A/g = 15 = cd, 1 <= c < sqrt(15) < 4, (c,d) = (1,15),
(3,5), (a,b) = (14,210), (42,70)
g = 70, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (70,210)
g = 6, A/g = 35 = cd, 1 <= c < sqrt(35) < 6, (c,d) = (1,35),
(5,7), (a,b) = (6,210), (30,42)
g = 30, A/g = 7 = cd, 1 <= c < sqrt(7) < 3, (c,d) = (1,7), (a,b) = (30,210)
g = 42, A/g = 5 = cd, 1 <= c < sqrt(5) < 3, (c,d) = (1,5), (a,b) = (42,210)
g = 210, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(210) = 8 + 4 + 4 + 4 + 2 + 2 + 2 + 1 + 13 = 40
問題6 N(2310)
A = 2310 = 2 * 3 * 5 * 7 * 11,
g = 1, 3, 5, 7, 15. 21. 35, 105, 2, 6, 10, 14, 30, 42, 70, 210 及びそれらに 11 を掛けたもの
g = 1, 3, 5, 7, 15. 21. 35, 105, 2, 6, 10, 14, 30, 42, 70, 210 の場合は,A/g が問題5 の 11 倍になっています。
g = 1, A/g = 2310 = cd, 1 <= c < sqrt(2310) < 49,
c は,A/g = 2310 の 49 より小さい約数です。それは,16 個です。そこで,
(c,d) = 16 個, (a,b) = 16 個
以下同様にして,
g = 3, A/g = 770 = cd, 1 <= c < sqrt(770) < 28, (c,d) = 8 個, (a,b) = 8 個
g = 5, A/g = 462 = cd, 1 <= c < sqrt(462) < 22, (c,d) = 8 個, (a,b) = 8 個
g = 7, A/g = 330 = cd, 1 <= c < sqrt(330) < 19, (c,d) = 8 個, (a,b) = 8 個
g = 15, A/g = 154 = cd, 1 <= c < sqrt(154) < 13, (c,d) = 4 個, (a,b) = 4 個
g = 21, A/g = 110 = cd, 1 <= c < sqrt(110) < 11, (c,d) = 4 個, (a,b) = 4 個
g = 35, A/g = 66 = cd, 1 <= c < sqrt(66) < 9, (c,d) = 4 個, (a,b) = 4 個
g = 105, A/g = 22 = cd, 1 <= c < sqrt(22) < 5, (c,d) = 2 個, (a,b) = 2 個
g = 2, A/g = 1155 = cd, 1 <= c < sqrt(1155) < 34, (c,d) = 8 個, (a,b) = 8 個
g = 6, A/g = 385 = cd, 1 <= c < sqrt(385) < 20, (c,d) = 4 個, (a,b) = 4 個
g = 10, A/g = 231 = cd, 1 <= c < sqrt(231) < 16, (c,d) = 4 個, (a,b) = 4 個
g = 14, A/g = 165 = cd, 1 <= c < sqrt(165) < 13, (c,d) = 4 個, (a,b) = 4 個
g = 30, A/g = 77 = cd, 1 <= c < sqrt(77) < 9, (c,d) = 2 個, (a,b) = 2 個
g = 42, A/g = 55 = cd, 1 <= c < sqrt(55) < 8, (c,d) = 2 個, (a,b) = 2 個
g = 70, A/g = 33 = cd, 1 <= c < sqrt(33) < 6, (c,d) = 2 個, (a,b) = 2 個
g = 210, A/g = 11 = cd, 1 <= c < sqrt(11) < 4, (c,d) = 1 個, (a,b) = 1 個
これを見ると,個数は,問題5 の場合の 2 倍 + 1 = 40 * 2 + 1 になっています。
残りは,g が 11 の倍数ですが,A/g = cd は,問題5 と同じになります。
そこで,(c,d) = 40 個, (a,b) = 40 個
N(2310) = 40 * 2 + 1 + 40 = 121
参考 一般の N(A) について
もう少し例をやってみます。
N(2)
A = 2 = 2, g = 1, 2
g = 1, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (1,2)
g = 2, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(2) = 1
N(4)
A = 4 = 2^2, g = 1, 2, 4
g = 1, A/g = 4 = cd, 1 <= c < sqrt(4) = 2, (c,d) = (1,4), (a,b) = (1,4)
g = 2, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (2,4)
g = 4, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(4) = 2
N(12)
A = 12 = 2^2 * 3, g = 1, 2, 4, 3, 6, 12
c, d は互いに素,に注意して,
g = 1, A/g = 12 = cd, 1 <= c < sqrt(12) < 4, (c,d) = (1,12),
(3,4), (a,b) = (1,12), (3,4)
g = 2, A/g = 6 = cd, 1 <= c < sqrt(6) < 3, (c,d) = (1,6),
(2,3), (a,b) = (2,12), (4,6)
g = 4, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (4,12)
g = 3, A/g = 4 = cd, 1 <= c < sqrt(4) = 2, (c,d) = (1,4), (a,b) = (3,12)
g = 6, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (6,12)
g = 12, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(12) = 7
N(36)
A = 36 = 2^2 * 3^2, g = 1, 2, 4, 3, 6, 12, 9, 18, 36
g = 1, A/g = 36 = cd, 1 <= c < sqrt(36) = 6, (c,d) = (1,36),
(4,9), (a,b) = (1,36), (4,9)
g = 2, A/g = 18 = cd, 1 <= c < sqrt(18) < 5, (c,d) = (1,18),
(2,9), (a,b) = (2,36), (4,18)
g = 4, A/g = 9 = cd, 1 <= c < sqrt(9) = 3, (c,d) = (1,9), (a,b) = (4,36)
g = 3, A/g = 12 = cd, 1 <= c < sqrt(12) = 4, (c,d) = (1,12),
(3,4), (a,b) = (3,36), (9,12)
g = 6, A/g = 6 = cd, 1 <= c < sqrt(6) < 3, (c,d) = (1,6),
(2,3), (a,b) = (6,36), (12,18)
g = 12, A/g = 3 = cd, 1 <= c < sqrt(3) = 2, (c,d) = (1,3), (a,b) = (12,36)
g = 9, A/g = 4 = cd, 1 <= c < sqrt(4) = 2, (c,d) = (1,4), (a,b) = (9,36)
g = 18, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (18,36)
g = 36, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(36) = 12
以上を踏まえて考えてみます。
まず,明らかに
命題1 A が素数の場合,N(A) = 1
です。これは,問題1 などと同様にして,
A, g = 1, A
g = 1, A/g = A = cd, 1 <= c < sqrt(A) < A, (c,d) = (1,A), (a,b) = (1,A)
g = A, A/g = 1 = cd, 1 <= c < sqrt(1) < 1, (c,d) = NG, (a,b) = NG
N(A) = 1
です。
次に,
命題2 p は素数で A = p^n の場合,N(A)
= n
がいえます。これは,
A = p^n, g = 1, p, p^2, ..., p^n
c, d は互いに素でないといけないことに注意すると,
g = 1, A/g = p^n = cd, 1
<= c < sqrt(p^n), (c,d) = (1,p^n), (a,b) = (1,p^n)
g = p, A/g = p^(n-1) = cd, 1 <= c < sqrt(p^(n-1)), (c,d) =
(1,p^(n-1)), (a,b) = (p,p^n)
...
g = p^k, A/g = p^(n-k) = cd,
1 <= c < sqrt(p^(n-k)), (c,d)
= (1,p^(n-k)), (a,b) = (p^k,p^n)
...
g = p^(n-1), A/g = p = cd, 1 <= c < sqrt(p), (c,d) = (1,p), (a,b) = (p^(n-1),p^n)
g = p^n, A/g = 1 = cd, 1
<= c < sqrt(1) < 1, (c,d)
= NG, (a,b) = NG
N(A) = N(p^n) = n
だからです。
さらに,
命題3 A = Br, r は素数で B と r は互いに素の場合,
N(A) = 2 * N(B) + 1 + N(B) = 3 * N(B) + 1
がいえそうです。これは,次のように考えられます。
A = Br, g = B の約数,B の約数 * r
・g = B の約数 の場合 A/g = B/g * r です。
B/g = ef,e, f は互いに素とし,
そのような (e,f) のうち 1 <= e < sqrt(B/g) となる e の個数を n(B/g) とすると,
f = B/g * 1/e > B/g * 1/sqrt(B/g) = sqrt(B/g) なので,
全体の互いに素な約数の個数は,e と f とを合わせて 2 * n(B/g) です。
つまり,sqrt(B/g) より小さい場合の個数は,全体の半分になります。
一方,A/g = B/g * r = cd の c は,B/g のものと B/g のものに r を掛けたもので 4 * n(B/g) です。
1 <= c < sqrt(A/g) はこの半分なので,2 * n(B/g) になります。
つまり,c の個数は e の個数の 2 倍です。
ただし,g = B の場合は,B/g = 1, 1 <=
e < sqrt(B/g) = 1 なる e は存在せず特別ですが,
A/g = r, 1 <= c < sqrt(A/g) = sqrt(r) で,c = 1 が新たに存在します。
そこで,この特殊な場合以外は常に 2 倍になるので,個数は 2
* N(B) + 1 になります。
・g = B の約数 * r の場合 g = rg', g' は B の約数,として,A/g = B/g' です。
B/g' = A/g = cd で,B/g' は r が掛かっていない場合と同じなので,個数は N(B) になります。
以上ですべてなので,結局,
N(A) = 2 * N(B) + 1 + N(B) = 3 * N(B) + 1
になります。
そして,これを拡張すると,
命題4 A = B * r^n, r は素数で B と r は互いに素の場合,
N(A) = (2 * N(B) + 1) * n + N(B) = (2n+1) * N(B) + n
がいえます。これは,命題3 とほとんど同じに考えられます。
A = B * r^n, g = B の約数,B の約数 * r,B の約数 * r^2,...,B の約数 * r^n
・g = B の約数 * r^k, k = 0 〜 n-1 の場合 A/g = B/g * r^(n-k) です。
命題3 と同じ記法で同じに考えて,B/g に関し全体の互いに素な約数の個数は,2 * n(B/g) です。
一方,A/g = B/g * r^(n-k) = cd の c は,c, d が互いに素なので,
B/g のものと B/g のものに r^(n-k) を掛けたものしかなく,4 * n(B/g) です。
1 <= c < sqrt(A/g) はこの半分なので,2 * n(B/g) になり,やはり 2 倍です。
ただし,g = B * r^k の場合は,
A/g = r^(n-k), 1 <= c < sqrt(A/g) = sqrt(r^(n-k)) で,c, d は互いに素なので c = 1 だけです。
そこで,この特殊な場合以外は常に 2 倍になるので,個数は 2
* N(B) + 1 になります。
これが,k = 0 〜 n-1 の n 個あることになり,全体で (2 * N(B) + 1) * n です。
・g = B の約数 * r^n の場合 g = r^n
* g' として,A/g = B/g' です。
B/g' = A/g = cd で,B/g' は r が掛かっていない場合と同じなので,個数は N(B) になります。
以上ですべてなので,結局,
N(A) = (2 * N(B) + 1) * n + N(B) = (2n+1) * N(B) + n
になります。
以上で,一般に,p, q, ..., r を素数として,A =
p^n * q^m * ... * r^k の場合は,
・命題2 より,N(p^n)
を求める。
・命題4 より,順次,q^m を掛けた場合,...,r^k を掛けた場合,をそれぞれ求めていく。
で得ることができます。
例えば,
N(2) = 1
N(6) = N(2 * 3) = 3 * N(2) + 1 = 3 * 1 + 1 4
N(3) = 1
N(15) = N(3 * 5) = 3 * N(3) + 1 = 3 * 1 + 1 = 4
N(5) = 1
N(35) = N(5 * 7) = 3 * N(5) + 1 = 3 * 1 + 1 = 4
N(105) = N(3 * 5 * 7) = 3 * N(3 * 5) + 1 = 3 * 4 + 1 = 13
N(210) = N(2 * 3 * 5 * 7) = 3 * N(3 * 5 * 7) + 1 = 3 * 13 + 1 = 40
N(2310) = N(2 * 3 * 5 * 7 * 11) = 3 * N(2 * 3 * 5 * 7) + 1 = 3 * 40 + 1 = 121
N(4) = N(2^2) = 2
N(12) = N(2^2 * 3) = 3 * N(2^2) + 1 = 3 * 2 + 1 = 7
N(12) = N(3 * 2^2) = 5 * N(3) + 2 = 5 * 1 + 2 = 7
N(36) = N(2^2 * 3^2) = 5 * N(2^2) + 2 = 5 * 2 + 2 = 12
となります。
(感想)
今回は久しぶりに少し骨のある問題でした。
一般の場合が正しいことを祈ります (^^;
NO2 「kashiwagi」 9/25 08時02分受信
「kashiwagi」 9/26 08時40分受信 更新10/5
213回解答
ある数は必ず素数の積に分解されるので試みると、今回の問題の数は以下の様になる。
6=2×3
15=3×5
35=5×7
105=3×5×7
210=2×3×5×7
2310=2×3×5×7×11
ここで一般的に考えてみると、題意より最小公倍数が6ということは、6の公約数と6の組み合わせ、および公約数を持たない2数の組み合わせとなる。因って、求めるものは(1,6)(2,6)(3,6)(2,3)という事になる。即ち、N(6)=4となる。
次に105を考えてみると、全く同様な考え方で105と1、3、5、7、15、21、35更に35と3、15、21、21と5、15および15と7になる。即ち、(1,105)(3,105)(5,105)(7,105)(15,105)(21,105)(35,105)(3,35)(15,35)(21,35)(5,21)(15,21)(7,15)
因って、N(105)=13となる。
他も全く同様な考え方でやりまとめると、
問題1.〜3.
N(6)=N(15)=N(35)=4
問題4.
N(105)=13
問題5.
N(210)=40
問題6.
N(2310)=113
問題1〜6を表にまとめ、N(A)を算定する式をじっと眺めて推定すると、約数の種類Nが関係していそうだと分かるので、試行錯誤してみると、
A |
約数の種類(N) |
N(A) |
N(A)の階差 |
6,15,35 |
2 |
4 |
9=32 |
105 |
3 |
13 |
27=33 |
210 |
4 |
40 |
81=34 |
2310 |
5 |
121 |
|
階差からN(A)=(3N+1-1)/2 となることが判明する。
但し、この式は数Aが各々1個ずつの素数の積で表せた場合であり、素数の累乗積の場合は当てはまらない。
「kasama」 9/26 23時31分受信 更新10/31
正の整数の組(a,b)が(a,b)=(p1α1p2α2…pnαn,p1β1p2β2…pnβn)と素因数分解されたします。このとき、組(a,b)の最小公倍数cは |
|||||||||||||||||||||||||||||||||||||||||||||||||||
c=p1γ1p2γ2…pnγn ただし、γi=max(αi,βi)(i=1,2,…,n) |
|||||||||||||||||||||||||||||||||||||||||||||||||||
と表すことができます。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||
逆に、最小公倍数がA=p1γ1p2γ2…pnγnとなるような正数の組(a,b)=(p1α1p2α2…pnαn,p1β1p2β2…pnβn)について考えます。i番目の素因数piの組み合わせは、(αi,βi)=(γi,0),(γi,1)…(γi,γi)…(1,γi),(0,γi)の2(γi+1)-1個だから、すべての素因数で考えると、{2(γ1+1)-1}・{2(γ2+1)-1}…{2(γn+1)-1}個あります。この中には、a=bとなるのが1個、残りはa<bとa>bで半分ずつなので、a<bとなるような組(a,b)の個数は、1引いて2で割った数です。つまり、 |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
と表すことができます。この考察をもとに、問題を解くと下表のようになります。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。