Weekend Mathematics／問題／問題95



９５．７７の倍数

下の表は、１行目には１から１００までの整数を１つずつ、すべて書き並べ、 ２行目以降はある決まりに従って最後の１００行目まで並べたものです。 この表の中に７７で割り切れる数は全部でいくつありますか？







問題の出典


算数オリンピックに挑戦
'00〜'03年度版
算数オリンピック委員会編
2001年第10回算数オリンピックファイナル問題




答えと解説





答えと解説

解答・その1

（ペンネ−ム：kiyo）

62個。

NO.1個1行目77
NO.2個2行目77
NO.3個3行目308
NO.4個4行目308
NO.5個5行目1232
NO.6個6行目1232
NO.7個7行目4928
NO.8個8行目4928
NO.9個9行目19712
NO.10個10行目19712
NO.11個11行目78848
NO.12個12行目78848
NO.13個13行目315392
NO.14個14行目315392
NO.15個15行目1261568
NO.16個16行目1261568
NO.17個17行目5046272
NO.18個18行目5046272
NO.19個19行目20185088
NO.20個20行目20185088
NO.21個21行目80740352
NO.22個22行目80740352
NO.23個23行目322961408
NO.24個24行目322961408
NO.25個25行目1291845632
NO.26個26行目1291845632
NO.27個27行目5167382528
NO.28個28行目5167382528
NO.29個29行目20669530112
NO.30個30行目20669530112
NO.31個31行目82678120448
NO.32個32行目82678120448
NO.33個33行目330712481792
NO.34個34行目330712481792
NO.35個35行目1322849927168
NO.36個36行目1322849927168
NO.37個37行目5291399708672
NO.38個38行目5291399708672
NO.39個39行目21165598834688
NO.40個40行目21165598834688
NO.41個41行目84662395338752
NO.42個42行目84662395338752
NO.43個43行目338649581355008
NO.44個44行目338649581355008
NO.45個45行目1354598325420032
NO.46個46行目1354598325420032
NO.47個47行目5418393301680128
NO.48個48行目5418393301680128
NO.49個50行目21673573206720512
NO.50個52行目86694292826882048
NO.51個54行目346777171307528192
NO.52個56行目1387108685230112768
NO.53個58行目5548434740920451072
NO.54個60行目22193738963681804288
NO.55個62行目88774955854727217152
NO.56個64行目355099823418908868608
NO.57個66行目1420399293675635474432
NO.58個68行目5681597174702541897728
NO.59個70行目22726388698810167590912
NO.60個72行目90905554795240670363648
NO.61個74行目363622219180962681454592
NO.62個76行目1454488876723850725818368




解答・その2

（ペンネ−ム： 浜田　明巳）


　最近愛用のノートパソコンがダウンしてしまいましたので，昔のＤＯＳマシンを引っぱり出して解きました．昔懐かしいＮ８８ＢＡＳＩＣです．シラミつぶしで計算し，答が62個になります．

100 'SAVE "WM0411.BAS",A

110 DIM A(100,100)

120 KOTAE=0

130 FOR GYOU=1 TO 100

140   FOR RETSU=1 TO 100-(GYOU-1)

150     IF GYOU=1 THEN A(RETSU,1)=RETSU ELSE A(RETSU,GYOU)=A(RETSU,GYOU-1)+A(RETSU+1,GYOU-1)

160     A(RETSU,GYOU)=A(RETSU,GYOU) MOD 77

170     PRINT A(RETSU,GYOU);

180     KOTAE=KOTAE-(A(RETSU,GYOU)=0)

190   NEXT RETSU

200   PRINT

210   'PRINT GYOU;"行目までに77の倍数は";KOTAE;"個あります．"

220 NEXT GYOU

230 PRINT "答は";KOTAE;"個です．"

240 OPEN "WM0411.DAT" FOR OUTPUT AS #1

250 WRITE #1,KOTAE

260 CLOSE #1

270 END




解答・その3

（ペンネ−ム：三角定規）


上図のように，各行の数字列の作られ方から わかるように，第m行は 公差 2m-1 の等差数列 である。各行の初項は，
　　第3行が　 8＝1･1＋2･2＋1･3
　　第4行が　20＝1･1＋3･2＋3･3＋1･4
　　第5行が　48＝1･1＋4･2＋6･3＋4･4＋1･5
であることから，第m行の初項は



よって，第m行は，初項 (m＋1)2m-2 公差 2m-1 の等差数列で，その第n項 f (m，n) は



(1) m＝1のとき，f (1，n)＝n で，f (1，77)＝77 が77の倍数。
(2) m≧2のとき，f (m，n) が77の倍数 ⇔ m＋2n−1 が77の倍数。
　　　　(※)より，　m＋2n−1 ＝77 or 154
　1°m＝2k＋1 のとき，2k＋2n＝154　∴ k＋n＝77
　　　　(※)より，2k＋1＋n≦101　∴ 2k＋n≦100　∴ 1≦k≦23
　　　　よって，このとき 77の倍数となる f (m，n) の個数は 23個。
　2°m＝2k　のとき， 2k＋2n−1＝77　∴ k＋n＝39　∴ 1≦k≦38
　　　　よって，このとき 77の倍数となる f (m，n) の個数は 38個。

以上より，77の倍数となる f (m，n) の個数は 1＋23＋38＝62個 …［答］

この規則から作られる 77の倍数 f (m，n) で最大のものは，
　　　f (76，1)＝77･274＝1,454,488,876,723,850,725,818,368

f (m，n) の中で最大のものは，
　　　f (100，1)＝101･298＝32,008,177,655,762,792,387,791,755,935,744




解答・その4

（ペンネ−ム：巷の夢）

　ある数字に着目し、その数の下に続く数字をみると必ずある数の倍数となっていることが分かります。例えば、3､12､48となります。このことから77がある行を探せば良いことが分かります。77があるのはまず、1行目の後ろから24番目です。又、2行目の38番目にも77が存在します。更に検討すると以上の2ケースしかないことが判明します。

　ところで1行目後ろから24番目の77に続く数の合計は24個です。同様に2行目の38番目の77に続く数の合計は38個です。これらより求めるものは62個となります。



解答・その5

（ペンネ−ム：杖のおじさん）

　数列７７のある項数初項最終項項数
１行目のｎ７７番目１１００１００
２行目の２ｎ＋１３８番目３１９９９９


１行目は項数が１００、数列ｎなので最終項が１００なので７７で割れる数は１個です
２行目は項数が９９、数列２ｎ＋１なので最終項が１９９なので７７の倍数である ７７と１５４があるか調べます。
２ｎ＋１＝７７を解きｎ＝３８　２ｎ＋１＝１５４を解きｎ＝７６．５　
従って２行目には７７で割れる数字は１つあります。

下に続くある数字は１行目の数列ｎ及び２行目の数列２n+1の４倍の数字の数列であることがわかります。ある数字の倍数である事はその倍数で割ることが出来ます。 従ってその倍数が幾つあるか調べれば答えが出ます。

ある数字が、その数列の項数の半分より左にある時は
（その数字の項数）が個数です。
ある数字が、その数列の項数の半分より右にある時は
（その数列の項数）−（その数字の項数）＋１が個数です。

１行目　１００−７７＋１＝２４
２行目　３８

答えは２４個＋３８個＝６２個あります



解答・その6

（ペンネ−ム：Mr.X）

2n-1行目の数列を{a(n,k)}(1以上k,102-2n以下)
2b行目の数列を{b(n,k)}(1以上k,101-2n以下)
a(n+1,k)=4a(n,k+1) かつ b(n+1,k)=4b(n,k+1)
従って、{a(n,k)}(1以上n,(100-76)以下)の各行に１個ずつ
{b(n,k)}(1以上n,(77-1)/2以下)の各行に１個ずつ
合計62個77の倍数が存在します。




　

解答・その7

（ペンネ−ム：小学名探偵）

答え：６２

解答：

１行 　　76      77      78
    　　　　76+77    77+78
３行       　　77*4

上の図からわかるように、奇数行において、７７の倍数の位置は変わりません。 そして、２行下るごとに、数（カードとみてよいです）の並びから端の２枚が消えま す。
１行目において、７７の位置は左端より右端に近く、１００（右端）までに２４ （=100-77+1）枚のカードがあります。 この２４が奇数行に含まれる７７の倍数の個数です。

　　　　38     39
２行        77
同様に、偶数行において、７７の倍数の位置は変わりません。 ２行目において、７７は左端に近く、左端から３８番目のカードです。 この３８が偶数行に含まれる７７の倍数の個数です。 したがって、24+38=62 が答えとなります。



解答・その8

（ペンネ−ム：高橋　道広）

答　62個

解説
１行目　１，２，３，４,...,n,n+1,n+2、n+3,98,99,100となっているときに
２行目　　３　５　７　　　　2n+1,2n+3　2n+5...197,199
３行目　　　８　１２　　　　　　4n+4　4n+8...　396
となっているので　３行目は１行目を４倍して　両端の数を除いたものになっている。
３行目の数列は４でわっても77の倍数であることに影響がないから　
３行目を改めて2,3,4,...99とおいて考えてもよいことになる
すると４行目には２行目の両端の数を除いた数列となり
５行目には２行目の両端の数を除いた数列となっている。

１行目に77の倍数は77のみがある
２行目に77の倍数は　n+(n+1)が奇数であることから
　　　　　　　　　　n+(n+1)=77から　n=38　38番目にあり
　　77×3=231であるから　これだけしかないことがわかる。

　奇数行だけ取り出した数列を考えると
１：　　1,2,3,4,,　　　　　...100
２：　　2,3,4,5,...,99　　　　　　　(実際はその４倍)
３：　　3,4,5,6,7...98　　　　　　　(実際はその16倍)
...
50：　　　　　50,51　　　　　　　　　　(実際はその249倍）

この数列で最後に77がある列は
　　　○，○...77　となるときであるから
101-77=24列目であり　以上から　偶数列には24回出現することがわかる

偶数列をとりだすと
１：　　3,5,7,9,...,199
２：　　5,7,9,...,197
３：　　7,9,11,...,195
...
49：　　　　101

先に書いたように77はこの数列の38項目であるからこの数列には38回出現する
以上から　24+38=62回となります




解答・その9

（ペンネ−ム：Toru）

解答１　奇数行目と偶数行目を分けて考える。

作り方から、３行目は１行目の３つの並んだ数のまん中の数の４倍を並べたものにな り、５行目は３行目の３つの並んだ数のまん中の数の４倍を並べたものになる。４倍 しても、７７の倍数かどうかに影響を与えないから無視すれば結局、１行目から順に 両端を除いて並べればよい

1,2,3,4,-------------------------------------------------------,100
　2,3,4,----------------------------------------------------,99
  　3,4,------------------------------------------------,98

このうち７７の倍数は７７のみでこれは１００―７６＝２４行目までにふくまれる。
偶数行目も同様に４倍を無視すれば
3,5,7,9,--------------------------------------------------,199
  5,7,9,----------------------------------------------,197
    7,9,------------------------------------------,195

ここでも７７の倍数は７７のみで７７=３８×２＋１よりこれは３８行目までに含ま れる。
よって求める答は　２４＋３８＝６２

ということなのですが、実は最初は下のように腕力で解きました。とてもエレガント ではありませんが、せっかくなので、一応書いておきます。

解答２
n行目、左からk番目の数字をA(n,k)　(n=1,2,3,----,100 、 k=1,2,----,(101-n))と すると、題意よりA(1,k)=kでn≧2の時

A(n,k)
=A(n-1,k)+A(n-1,k+1)
=A(n-2,k)+2A(n-2,k+1)+A(n-2,k+2)
=A(n-3,k)+3A(n-3,k+1)+3A(n-3,k+2)+A(n-3,k+3)
= -----------
=A(1,k)+ n-1C1A(1,k+1)+ n-1C2A(1,k+2)+-----+ n-1Cn-1A(1,k+n-1)
=k+(k+1) n-1C1+(k+2) n-1C2+-------+(k+n-1) n-1Cn-1


ここで、

(x+1)n-1= 1+n-1C1x+n-1C2x2+---- +n-1Cn-1 xn-1

の両辺にxkをかけて微分すると

kxk-1･(x+1)n-1+xk･(n-1)(x+1)n-2=kxn-1+(k+1)n-1C1xk+(k+2) n-1C2xk+1+---+(k+n-1)n-1Cn-1xk+n-2

ここでx=1とすると

A(n,k)=k+(k+1)n-1C1+(k+2)n-1C2+------+(k+n-1)n-1Cn-1 =k2n-1+(n-1)2n-2=2n-2･(2k+n-1)　 (n=1でも成立)

よって2k+n-1が７７の倍数の条件を考えることになるが、
2k+n-1≦201-n≦200より　2k+n-1=77 ----1) と2k+n-1=154 ----2)の場合を考えればよい。

1) 2k =78-n よりn偶数でn=2,4,-----,76のすべてが条件を満たし、３８個
2) 2k=155-n よりn奇数、n+k≦101とからn≦47 n=1,3,----,47の２４個
よって合計６２個




解答・その10

（ペンネ−ム：蜘蛛の巣城）

1段目　　１　２　３　４　５････････････････････････98　　99　　100
2段目　　　３　５　７  ９　･････････････････････････  197　 199
3段目　　　　８　12　16　･････････････････････････････　 396
4段目　　　　　････････････････････････････････････････････
・ 　　　　　　　　･･････････････････････････････････････
・　　　　　　　　　　･･･････････････････････････････
・
・　　　　　　　　　　　　　　･･････････････････
・　　　　　　　　　　　　　　　･･････････････
98段目 　　　　　　　　　　　　　＊　＊　＊
99段目　 　　　　　　　　　　　　　＊　＊
100段目　　　　　　　　　　　　　　  ＊

この規則で各段が生起するなら、98段目までは等差数列だと言って構わないと思います、証明は省きますが。それで、任意の隣接3段において最上段の任意の隣接3数から生起する数を以下のように整列させましょう。

　　　　　　　　
Ａ−ｄ　　　　　　Ａ　　　　　　Ａ＋ｄ
　　２Ａ−ｄ　　　２Ａ＋ｄ
　　　　　　 ４Ａ


「数Ａ」と１段とばした真下の（不正確な表現ですが）「数４Ａ」とは、「77」の倍数であるか否かが一致します。

さて、第1段の「77」の倍数は「77」のみ。奇数段の「77」の真下に位置する数はすべて「77」の倍数で、それ以外にはありません。「77」は右から24番目に位置します。奇数段を1段降るごとに右から（謂はば対角線的に）1つずつ項が減りますから、奇数段を24段数えて「77」の倍数は終わりです。その下は項がありません。
また、第2段でも「77」の倍数は「77」のみ。「77」は左から38番目に位置します。（一般項 ２ｎ＋１（ｎ＝１,２,３･･････99）ですね。）奇数段での考察と同様に、偶数段を38段数えて終わりです。
段数の合計62段が、即ち「77」の倍数の個数62個に等しいことになります。




解答・その11

（ペンネ−ム：夜ふかしのつらいおじさん）

答は６２個です。

２行目以降の「ある決まり」とは、「隣りあう２数の和をその２数の間に書く」です。


　１　２　３　４　５　・・・
　　３　５　７　９　・・・
      ・・・・・・・・・

（１）この問題を考えるとき、元の数を７７で割った余りを見ていけば十分です。
余りが３９をこえるときは７７を引いて負の数で表した方が考えやすいと思いま す。（３９を−３８、４０を−３７と表します）
例えば、

９９＋１００
＝(７７×１＋２２)＋(７７×１＋２３)
＝７７×２＋４５

ですが、９９、１００をそれぞれ７７で割った余りの２２と２３だけ見ればよい のです。
１行目には７７で割り切れる数は、７７の１つだけです。
そこで７７の近辺を見てみます。 

・・・　７５　　　　　７６　　　　７７　　　　７８　　　　７９　・・・
・・・・・・　１５１　　　１５３　　　１５５　　　１５７　・・・
・・・・・・・・・　３０４　　　３０８　　　３１２　・・・
・・・・・・・・・・・・・・・・・・・・・・・・・・・・

これを
・・・　−２　　　　−１　　　０　　１　　　２　・・・・・・
・・・・・・　−３　　　−１　　１　　　３　・・・・・・・
・・・　−８　　　  −４　　　０　　４　　　８　・・・・
・・・・・　−１２　　　−４　　４　　１２　・・・・・
・・　−３２　　　−１６　　　０　１６　　３２　・・・
・・・・・・・・・・・・・・・・・・・・・・・・・

と表します。 すると、奇数行目に「０」が現れ、７７で割り切れる数があることが分かりま す。
２行下がると右側の数が１つ少なくなります。
１００−７７＝２３より、２×２３＋１＝４７行目の７７の真下の数が最後の７ ７で割り切れる数です。（２４個あります）

次に３８＋３９＝７７なので、３８と３９の近辺を見てみます。
・・・　３６　　　３７　　　　３８　　　　３９　　　　４０　　　　４１・・・
・・・・・　７３　　　　７５　　　　７７　　　　７９　　　　８１・・・
・・・・・・・　１４８　　　１５２　　　１５６　　　１６０・・・
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

これを
・・・　３６　　　３７　　　　３８　　−３８　　−３７　　−３６・・・・
・・・・・・　−４　　　−２　　　　０　　　　２　　　　４・・・・・
・・・・・・・・　−６　　　　−２　　　　２　　　　６・・・・・・
・・・・・　−１６　　　−８　　　　０　　　　８　　　１６・・・
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

と表します。 すると、偶数行目に「０」が現れ、７７で割り切れる数があることが分かります。
２行下がると左側の数が１つ少なくなります。
２×３８＝７６行目の３８と３９の間の真下の数が最後の７７で割り切れる数で す。（３８個あります）

これで少なくとも２４＋３８＝６２個あることが分かりました。

（２）次は（１）で調べたもの以外にはないことを考えます。

１　　　２　　　３　　　４　　　５　　　６　　　７　　　８　・・・・（公差：１）
　　３　　　５　　　７　　　９　　１１　　１３　　１５　・・・・（公差：２）
　　　　８　　１２　　１６　　２０　　２４　　２８　・・・・（公差：４）
          ２０　　２８　　３６　　４４　　５２　・・・・（公差：８）
              ４８　　６４　　８０　　９６　・・・・（公差：１６）
　　　　　　　   ・・・・・・・・・・・・・・・・

このようにｍ行目の公差は ２m-1です。
ｍ行目に７７で割り切れる数77×ｋがあったとします。（ｋは自然数です）
その数を基準として、ｎ番目の数をｆ(77,ｎ)と表すことにします。
（ｎは整数で、その数自身は０番目と考えます）

　　　　ｆ(77,ｎ)＝77×ｋ＋２m-1×ｎ

一方、７７＝７×１１です。
ですから ｆ(77,ｎ) が７７で割り切れるためには、ｎ自身が７７で割り切れなければなりません。
これは、ｆ(77,ｎ)の前後で７７で割り切れる数は、７７個前か後ろであることを意味します。

（１）の結果から、奇数行目は１行目の７７の位置に、偶数行目は１行目の３８ と３９の間に７７で割り切れる数があることが分かりました。
ｍ行目は、(１０１−ｍ)個の数があります。
どの行も７７で割り切れる数の前後には７７個の数はありません。
どの行も最大で１個しか７７で割り切れる数がないので（１）で数えた数しかな いことが分かります。



解答・その12

（ペンネ−ム：kirkland）

Ａ君「メリークリスマス！」

先生「おいおい、ちょっと気が早いよ！」

Ａ君「だって、次に登場するのは１月ですよ。」

先生「時間がないから、とっととやんなさい。」

Ａ君「１行目は１，２，３，…，99，100なので77の１個だけです。」

先生「２行目は奇数の列３，５，７，…，197，199になるので77の１個だけだね。」

Ａ君「３行目は４の倍数で８，12，16，…，392，396なので308(＝77×４)の１個だけです。」

先生「４行目も４の倍数の列20，28，36，…，780，788になるので308の１個だけだね。」

Ａ君「５行目は16の倍数で48，64，…，1568なので1232(＝77×16)の１個だけです。」

先生「６行目も16の倍数で…って、いつまでやるつもりだよ！そのまま足していったら数が馬鹿デカくなって大変だぞ。２と77は互いに素なんだから、２で割れるだけ割っていったら？」

Ａ君「なるほど。こんな感じですね。 
１行目　１　２　３　４　５　……………96　97　98　99　100
２行目　　３　５　７　９　11……………　193 195 197 199
３行目　　　２　３　４　５　……………96　97　98　99　　　　←４で割った商
４行目　　　　５　７　９　11……………　193 195 197 　　　　←４で割った商
５行目　　　　　３　４　５　……………96　97　98　　　　　　←16で割った商
６行目　　　　　　７　９　11……………　193 195　　　　　　 ←16で割った商
７行目　　　　　　　４　５　……………96　97　　　　　　　　←64で割った商
　　　　　　　　　　　　　　……………
これなら数が小さくて分かりやすいですね。」

先生「奇数番目は連続する整数の列になるし、偶数番目は連続する奇数の列になるわけだ。あとはそれぞれ別々に考えるだけだ。」

Ａ君「まずは、奇数番目の列なんですが、この調子でいくと 
45行目　23　24　25……76　77　78
47行目　　　24　25……76　77
49行目　　　　　25……76
こんな感じですかね。」

先生「えらく簡単に見つけたね。どうやったの？」

Ａ君「またまた〜。時間がないのに。列のアタマの数は１ずつ増えていくし、ケツの数は１ずつ減っていくんだから、その和は常に101で一定なんですよ。１行目は１＋100＝101、３行目は２＋99＝101…でしょ。それで、アタマの数を２倍して１引くと、何行目かを表す数になることを発見したんですよ！例えば、アタマの数が３になるのは３×２−１＝５行目とか。」

先生「アタマとかケツとか言わずに初項、末項とか言いなさい。」

Ａ君「まあそういうわけで、奇数番目の列では、１行目、３行目、…、47行目の24個の行に77が含まれます。ついでに、偶数番目もやっちゃいますね。偶数番目の列もこの調子でいくと 
74行目　75　77　79……123　125　127
76行目　　　77　79……123　125
78行目　　　　　79……123
全部、初項と末項の和が202です。 偶数番目の列では、２行目、４行目、…、76行目の38個の行に77が含まれます。 というわけで、全部で24＋38＝62個で〜す！」

先生「まぁ、そんな感じでいいんじゃない」

Ａ君「では、みなさんよいお年を。」

先生「だから〜、気が早いってば」






正解者

小学名探偵 kiyo Mr.X
三角定規 巷の夢 Toru
杖のおじさん 浜田　明巳 高橋　道広
夜ふかしのつらいおじさん kirkland 蜘蛛の巣城





まとめ

実は、１段ぬかしで縦に見ていくと、４倍の数が並んでいくことがわかります。 三角定規さんが示してくださった一般項でも確認できます。

　　　f(m+2,n-1)/f(m,n)=2m/2m-2=22=4

４倍を無視して表示するというToruさんや高橋道広さん、Ａ君の解答はすっきりしていますね。夜ふかしのつらいおじさんのように、７７の剰余で考えるという手もあります。いずれも大きい数を扱わなくていいというメリットがあります。そして、７７の倍数が縦に並んでいるということに気付けば、数えるのは そうむずかしいことではありませんね。





E-mail top