Weekend Mathematics／問題／問題46
４６．数学オリンピックの問題
シドニーオリンピックは私達に多くの感動を与えてくれ、今日閉会式を迎えました。
そこで、今回は数学オリンピックの問題からです。
ｎ２を１２０で割ると１余るような、１２０以下の正整数ｎはいくつあるか。
第３回 日本数学オリンピック予選
数学オリンピック 1991〜1996
(財)数学オリンピック財団編
日本評論社
答えと解説
（ペンネ−ム：佐々木一樹）
答え １６個
やり方
（ペンネ−ム：かつ）
今回のは、なかなかこれといったことがわからなかったので計算してとりあえず求めてみました。
かといって１２０個の整数をすべて確かめるのも大変なのでまずは確認する数を減らす作業から入りました。
今回の問題は
ｎ２を１２０で割ると1余ると言うことから、
ｎ２＝１２０ｋ＋１（ｋは任意の正整数（０を含む））
と言うように出来ます。
つまりｎ２は下一桁が１になると言うことが分かります。
そこでｎになりうる１２０以下の正整数のうち、平方して下一桁が１になるのは、
１の位が１または９のときのみと言うことになります。
あとはひたすら計算してみました。
そうすると
| １２＝１２０・０＋１ |
| １１２＝１２０・１＋１ |
| １９２＝１２０・３＋１ |
| ２９２＝１２０・７＋１ |
| ３１２＝１２０・８＋１ |
| ４１２＝１２０・１４＋１ |
| ４９２＝１２０・２０＋１ |
| ５９２＝１２０・２９＋１ |
| ６１２＝１２０・３１＋１ |
| ７１２＝１２０・４２＋１ |
| ７９２＝１２０・５２＋１ |
| ８９２＝１２０・６６＋１ |
| ９１２＝１２０・６９＋１ |
| １０１２＝１２０・８５＋１ |
| １０９２＝１２０・９９＋１ |
| １１９２＝１２０・１１８＋１ |
（ペンネ−ム：２４６）
答え： １６個
方法：
１２０で割って１が余るとなると、下１桁は必ず１となるということで、
２乗して下１桁が１になる値は、下１桁が １，９となる。
この時点で ２４個に絞られる。
次に１２０の公約数(2,3,4,5,6,8,10,12,15,20,24,30,40,60)で割れない数を取り出す。
ここで振り分けられる数が、9,21,39,51,69,81,99,111 の８個。
これをのぞいた数
1,11,19,29,31,41,49,59,61,71,79,89,91,101,109,119
の１６個が該当する・・・
（ペンネ−ム：マサボー ）
n２ = 120A+ 1とおける。
2乗して1の位が1になるものの1の位は1と9であるから、
n = 10B + 1あるいは10B + 9となる（０≦B≦11)
| n２ | = (10B + 1)２ |
| = 100B２ + 20B + 1 | |
| = 20B(5B+1) + 1 |
| n２ | = (10B + 9)２ |
| = 100B２+180B+81 | |
| = 100B２+180B+80 + 1 | |
| = 20(5B２+9B+4) + 1 | |
| = 20(5B+4)(B+1) + 1 |
（ペンネ−ム：hirai）
問を数式表現すると
ｎ２＝１２０Ａ＋１（但し Ａ≧０の整数） （ｎ≦１２０）・・・(1)
Ａ≧０の整数なので、ｎ２の一の位は常に１である。
整数の２乗数で、一の位が１になる数は０〜９の２乗を調べて、
（１０ｘ＋１）２または、（１０ｙ＋９）２で表せる。・・・(2)
ここで、ｘ、ｙは、０≦ｘ、ｙ＜１２を満たす整数である。
(1)(2)より、
| x | 左辺 | ６を因数に含むもの判定 |
|---|---|---|
| 1 | 1× 6 | ○ |
| 2 | 2×11 | × |
| 3 | 3×16 | ○ |
| 4 | 4×21 | ○ |
| 5 | 5×26 | × |
| 6 | 6×31 | ○ |
| 7 | 7×36 | ○ |
| 8 | 8×41 | × |
| 9 | 9×46 | ○ |
| 10 | 10×51 | ○ |
| 11 | 11×56 | × |
| x | 左辺 | ６を因数に含むもの判定 |
|---|---|---|
| 0 | 1× 4 | × |
| 1 | 2× 9 | ○ |
| 2 | 3×14 | ○ |
| 3 | 4×19 | × |
| 4 | 5×24 | ○ |
| 5 | 6×29 | ○ |
| 6 | 7×34 | × |
| 7 | 8×96 | ○ |
| 8 | 9×44 | ○ |
| 9 | 10×49 | × |
| 10 | 11×54 | ○ |
| 11 | 12×59 | ○ |
1.2.より １＋７＋８＝１６
従って、問の条件を満たす正整数は１６個
（ペンネ−ム：少年Ｈ）
ｎ２＝１２０×ｐ＋１
ｎ２−１＝１２０×ｐ
(ｎ−１)(ｎ＋１)＝２３×３×５×ｐ
ｐはｐ≧０の整数とする。
ｎ＝１は解である。
右辺は偶数であるから左辺も偶数。すなわちｎは奇数である。
また一方、右辺は５の因数が含まれるから、左辺も５の因数が含まれる。
よって、ｎの候補は、
| ｎ＝ | ９， | １１ |
| １９， | ２１ | |
| ２９， | ３１ | |
| ３９， | ４１ | |
| ４９， | ５１ | |
| ５９、 | ６１ | |
| ６９， | ７１ | |
| ７９， | ８１ | |
| ８９， | ９１ | |
| ９９， | １０１ | |
| １０９， | １１１ | |
| １１９ |
| ｎ＝ | ９×， | １１ |
| １９， | ２１× | |
| ２９， | ３１ | |
| ３９×， | ４１ | |
| ４９， | ５１× | |
| ５９、 | ６１ | |
| ６９×， | ７１ | |
| ７９， | ８１× | |
| ８９， | ９１ | |
| ９９×， | １０１ | |
| １０９， | １１１× | |
| １１９ |
（ペンネ−ム：高橋 道広）
答え １６個
文字はすべて自然数とします
n２2=120x+1とおくと n２2-1=120xより(n+1)(n-1)=120x
n+1またはn-1が偶数より、n=2k-1とおけます。
(2k-1-1)(2k-1+1)=120x より k(k-1)=30x
k(k-1)は必ず２の倍数なので、k(k-1)が１５の倍数であれば良いから
まず、５の倍数であることに着目して
k=15m,15m-4,15m-5,15m-9,15m-10,15m-14
このうちkまたはｋ−１が３の倍数であるものは
k=15m,15m-5,15m-9,15m-14
これをn=2k-1に代入して
n=30m-1,30m-11,30m-19,30m-29（m=1,2,3…)
つまり３０の倍数までに４つずつあることになる。
１２０までは4×(120/30)＝１６個となります。
（ペンネ−ム：ウェルテル）
ｎ＝ｍ＋１とおく ｎ・ｎ＝（ｍ＋１）・（ｍ＋１）
ｎの２乗を１２０で割ったときに余りが１になるにはｍの2乗＋２ｍが
１２０の倍数でなくてはならない。
m・m＋２・m＝m・（m＋２）
このときmまたはm＋２を２・３・５の倍数とするとｍ・（ｍ＋２）は１２０の倍数になる。
（なぜならば２つの連続する偶数のどちらか１つは２・２の倍数であるから）
（１２０＝２・２・２・３・５）
よってm＝３０、６０、９０ m＋２＝３０、６０、９０、１２０
m＝２８、３０、５８、６０、８８、９０、１１８
また m が６の倍数であるときm＋２が５の倍数である場合にもm・（m＋２）＝１２０が成り立つ。
m＋２は偶数だから１０の倍数であればよい。
そんなmをみたす数は０以上１１９以下の範囲では１８、４８、７８、１０８（１８＋３０・ｎ）
m が１０の倍数のときm＋２が３の倍数である場合にもm・（m＋2）＝１２０が成り立つ。
同様にm＋２は６の倍数であればよい。
そんな m をみたす数は０以上１１９以下の範囲に１０、４０、７０、１００（１２＋３０・ｎ）
（このときm＋２は１の位が２の数）
ｎ＝１のときもあまりは１になる
ｎ＝１、１１、１９、２９、３１、４１、４９、５９、６１、
７１、７９、８９、９１、１０１、１０９、１１９
（ペンネ−ム：kiyo）
１２０で割り１余る数は、
１＋１２０×（ｍ−１）＝１２０ｍ−１１９ ｍは正整数。
であるから、Ｎの１位の数は１または９でなければならない。 （１）
１≦Ｎ≦１２０。（２）
１２０＝２３×３×５
したがって、２，３，５の素因数を持たないものでなければならない。（３）
（１）、（２）、（３）を満たすものは、
| １ | ○ | １ |
| ９＝３２ | × | |
| １１ 素数 | ○ | ２ |
| １９ 素数 | ○ | ３ |
| ２１＝３×７ | × | |
| ２９ 素数 | ○ | ４ |
| ３１ 素数 | ○ | ５ |
| ３９＝３×１３ | × | |
| ４１ 素数 | ○ | ６ |
| ４９＝７２ | ○ | ７ |
| ５１＝３×１７ | × | |
| ５９ 素数 | ○ | ８ |
| ６１ 素数 | ○ | ９ |
| ６９＝３×１３ | × | |
| ７１ 素数 | ○ | １０ |
| ７９ 素数 | ○ | １１ |
| ８１＝３４ | × | |
| ８９ 素数 | ○ | １２ |
| ９１＝７×１３ | ○ | １３ |
| ９９＝３×１１ | × | |
| １０１ 素数 | ○ | １４ |
| １０９ 素数 | ○ | １５ |
| １１１＝３×３７ | × | |
| １１９＝７×１７ | ○ | １６ |
（ペンネ−ム：ねこ ）
条件より、ｎ２の1の位は１となるのは明らか。
よってｎの１の位は１か９となる。
ｎ＝１０Ｎ±１型のｎについて調べればよい。（以下複号同順）
ｎ２＝１２０ｋ＋１と書いたとき、
が整数となればよい。
そこで、Ｎ＝６ｍ±ｌ(ｌ＝０，１，・・・５)について
Ｎ(５Ｎ±１)を６で割った余りを調べてみる。
| Ｎ(５Ｎ±１) | ＝(６ｍ±ｌ){３０ｍ±(５ｌ＋１)} |
| ＝１８０ｍ２±(６０ｌ＋６)ｍ＋ｌ(５ｌ＋１) | |
| ＝ｌ(５ｌ＋１) (mod ６) (2) |
よって、Ｎ(５Ｎ±１)が６で割り切れるのは
Ｎ＝６ｍ±ｌ(ｌ＝０，１，３，４)のとき。
書きなおして、Ｎ＝３ｍ'±ｌ'(ｌ'＝０，１)のときとなる。
これをｎ＝１０Ｎ±１に代入して、条件を満たすｎの式が得られる。
| ｎ＝１０Ｎ±１ | ＝１０(３ｍ'±ｌ')±１ |
| ＝３０ｍ'±(１０ｌ'＋１) (ｌ'＝０，１) (4) |
（ペンネ−ム：夜ふかしのつらいおじさん ）
答えは16個です。(n=1,11,19,29, 31,41,49,59, 61,71,79,89, 91,101,109,119)
nの2乗を120で割ると1余るのですから商をpとすると、
n2=120×p+1
n22-1=120×p
∴(n-1)(n+1)=2×2×2×3×5×p
上式の右辺は偶数なのでnは奇数です。nを奇数とすると(n-1)と(n+1)とは隣り合う
偶数なので、その積(n-1)(n+1)は、必ず2×2×2の倍数です。
あとは、3と5の倍数になるように考えればよいわけです。
下の表は(n-1)か(n+1)のどちらかが3や5の倍数かどうかを調べたものです。
0はすべての数の倍数としています。
表のように3の倍数は3個ごとの周期で、5の倍数は5個ごとの周期で繰り返します。
ですから15(=3×5)の倍数は15個ごとの周期で繰り返します。
| n | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| n-1 | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 | 28 |
| n+1 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 | 28 | 30 |
| 3 | o | x | o | o | x | o | o | x | o | o | x | o | o | x | o |
| 5 | o | x | x | x | o | o | x | x | x | o | o | x | x | x | o |
| 15 | o | x | x | x | x | o | x | x | x | o | x | x | x | x | o |
（ペンネ−ム：水の流れ）
１２０＝２３×３×５ から、
「１２０で割った余りが１である」を、「8で割っても１余り、３で割っても１余
り、５で割っても１余る」
と言いかえることができる。
ここで、ｎ２を（１≦ｎ≦１２０）を考える。
（１）「ｎ２を８で割ると１余る」ということは、ｎを８で割った余りが１，３，
５，７である。即ち、ｎが奇数であることと同じである。」
（２）「ｎ２を３で割ると１余る」ということは、ｎを３で割った余りが１か２で
ある。」
（３）「ｎ２を５で割ると１余る」ということは、ｎを５で割った余りが１か４で
ある。」
以上（１）〜（３）より、「ｎ２を１２０で割ると１余る」は、
「ｎは奇数で、３で割ると１か２余り、５で割ると１か４余る」と言いかえことがで
きる。
このような数は、２×３×５＝３０を１周期とするので、１〜３０までについて、
具体的に調べると、適しているのが、１、１１，１９，２９ の４つの数だけであ
る。
したがって、１２０÷３０＝４から、４周期分を考えて４×４＝１６（個）・・・（答え）
次に、こんな便利な定理がありますので、紹介します。
【中国剰余定理】
ｋ、ｍ、ｎをどの２数も互いに素な自然数とするとき、
ｋで割るとｐ（０≦ｋ≦ｋ−１）余り、
ｍで割るとｑ（０≦ｑ≦ｍ−１）余り、
ｎで割るとｒ（０≦ｒ≦ｎ−１）余るような自然数は、
１〜ｋｍｎのｋｍｎ個の中にちょうど１つ存在する
『証明』
ｋで割るとｐ余り、ｍで割るとｑ余り、ｎで割るとｒ余る自然数が１〜ｋｍｎ個の中に
２個あったとし、その２つをＭ、Ｎとする。
すると、Ｍ−Ｎはｋでもｍでもｎでも割り切れるから、ｋ、ｍ、ｎのどの２数も互
いに素であることより、ｋｍｎで割り切れることになるが、
Ｍ、Ｎはどちらもｋｍｎ以下の自然数だからＭ−Ｎはｋｍｎより小であることに矛盾する。
よって、題意を満たす自然数は、１〜ｋｍｎに多くても１個しかない。
一方、ｋ、ｍ、ｎで割ったときの余りはそれぞれｋ、ｍ、ｎ通りなので、
余りの組み合わせはｋｍｎしかない。
よって、題意を満たす自然数が１〜ｋｍｎに１つもないとすれば、これも矛盾する。
以上より、題意を満たす自然数は１〜ｋｍｎにちょうど１個存在する。
ここで、今月の問題に適用すると、
８で割った余りが１，３，５，７の４通り、
３で割った余りが１か２の２通り、
５で割った余りが１か４の２通りだから、
「8で割っても１余り、３で割っても１余り、５で割っても１余る」
を満たす自然数は、８、３，５のどの２数の互いに素より、
１〜１２０までに題意を満たす自然数は４×２×２＝１６（通り）・・・（答）
（ペンネ−ム：浜田 明巳）
答は１６個．
今回もエクセルのマクロで作りました．
簡単に表型式で表示出来るのでこのソフトが一番プログラムを組みやすいものです．
|
Sub Macro1()
Dim 答 As Integer
Dim n As Integer
Cells(1, 1).Value = "答"
Cells(1, 2).Value = "n"
Cells(1, 3).Value = "n^2"
Cells(1, 4).Value = "商"
答 = 0
For n = 1 To 120
If (n * n) Mod 120 = 1 Then
答 = 答 + 1
Cells(答 + 1, 1).Value = 答
Cells(答 + 1, 2).Value = n
Cells(答 + 1, 3).Value = n * n
Cells(答 + 1, 4).Value = (n * n) \ 120
End If
Next
End Sub
|
（ペンネ−ム：中数の基本）
ご本人の了解を得て、ソースも掲載します。
<form name="asao"><input type="button" value="ここを押す" onClick="aaa()">
<textarea name="ta1" rows="2" cols="62" wrap="virtual"></textarea>
</form>
<script language="javascript">
gaitounosuu = '';
count = 0;
function aaa()
{for(kk = 1; kk <= 120; kk++)
{if(kk * kk % 120 == 1)
{gaitounosuu += kk + ',';
count++;
}
}
document.asao.ta1.value = gaitounosuu + 'の' + count +'個です．単純計算でごめんね．(Where have Math gone ?)';
}
| kiyo | 夜ふかしのつらいおじさん | 浜田 明巳 |
| 少年Ｈ | 高橋 道広 | 中数の基本 |
| ２４６ | ねこ | 水の流れ |
| 佐々木一樹 | hirai | かつ |
| マサボー | ウェルテル |
この問題を解くときに、ｎ＝１〜１２０まで２乗して１２０で割って余りを出してみるというやり
方があると思います。
プログラムを組むことで解答を出してくださった浜田 明巳さんや
中数の基本さんはこの方式です。
一方、佐々木一樹さんの解き方は、逆に１２０倍数＋１で開法（平方根を求める）してみて
整数になるか調べるということです。
人によってアプローチの仕方が違うけれど、真実は１つというのが数学のおもしろさ
でもあると思います。
人間が計算するときには、なぜこんな遠回りなことをするのだろうと思っても、
コンピューターに相性のいいアルゴリズムというのもあると思います。
少年Ｈさんの解答では、６行目に左辺は偶数とありますが、
単に偶数というだけではなく、２３＝８の倍数であることを一言指摘した方がい
いと思います。（証明するほどのことはないのですけれどね。）
今回はここで【中国剰余定理】を紹介しようかと思っていたのですが、
水の流れさんが説明してくださっていますので、そちらをお読みください。
さて今回初めて、JavaScriptで書かれた解答をいただきました。
中数の基本の了解を得て、ソース表示も表に出させていただきました。
JavaScriptというスクリプト言語はホームページをかく、いわゆるタグの中に表現し、
それをブラウザ側で解釈し、実行します。
裏返せば、JavaScriptに対応していないブラウザをお使いの方は、うまく動作しないかもしれません。
(確認できていません、すいません。)
ホームページの表現力をupする意味でも興味がありますので、私も勉強してみようと思います。
E-mail
戻る
top