第318問の解答


問題 [整数の性質]

ある10ケタ整数Aがあります。この整数は、次のような性質を持っています。
  • 先頭の数は、で使われた0の個数
  • 2番目の数は、で使われた1の個数
  • 3番目の数は、で使われた2の個数
          ・
          ・
  • 10番目の数は、で使われた9の個数

では、この整数Aを求めて下さい。


解答例1

monさん、ミミズクはくず耳さん、ちば けいすけさん、有無相生さん、M.Hossieさん、ねこやんさん、フランク長いさん、スモークマンさん、ハラギャーテイさん、tomhさん、うっしーさん、大岡 敏幸さん、他 多数

整数A各桁の数字x0x1、・・・、x9とします。

参考図1

xk整数Aで使われたkという数字の個数だから、そのAの桁数である10に等しい。
また、xk>0のとき、kという数字整数Axk個存在するので、xk個の数字k個あることになるので、kxkAの桁数10と等しい。

以上より、次の2式が成り立ちます。

  • Σk=0..9xk=10 ・・・ (1)

  • Σk=0..9k・xk=10 ・・・ (2)

さて、0の個数に着目して考えましょう。

もし0の個数ならば、x0=0となり、0という数字1個はあることになって矛盾します。
また、0の個数10ならば、ての桁の数字となるので、x0=0となって矛盾。

従って、1≦x0≦9となります。 ・・・ (3)

さて、k=1〜9でxk>0となるkの個数Nとします。
もし、N≧4とすると、1≦p<q<r<s≦9でxpxqxrxs>0となる数字p、q、r、sが存在します。
このとき、
 Σk=0..9k・xkp・xpq・xqr・xrs・xs≧1・xp2・xq3・xr4・xs=1+2+3+4=10

ところが、(2)が成り立つので、上式より、p=1、q=2、r=3、s=4、xp=xq=xr=xs=1が成り立つことになります。
これは、1という数字が少なくとも4個存在することとなり、x1=1(p=1のときxp=1)と矛盾します。

よって、N≦3が成り立ちます。 ・・・ (4)

ところで、Nxk>0となるkの個数だったので、これより0という数字が、1 0−(1+3)=6個以上存在することになり、6≦x0≦9となります。 ・・・ (5)

さて、mx0とおきます。(5)より、6≦m≦9が成り立ちます。
すると、mという数字が先頭に存在するので、x>0となります。

もしx≧2とすると、mx≧6・2>12となり、(2)に反しますから、x=1となります。
また、もし6≦k≦9、k≠mxk>0となるものが存在したら、
 mxkxk6・1+6・1>10となって、(2)に反します。
従って、6≦k≦9では、k=m以外はxk=0となります。

参考図1−2

さて、上記からm(6≦m≦9)の桁に1という数字1個以上存在することになります。
従って、x>0となりますが、もしx=1とすると、さきほどの1個と合わせて数字12個は存在することになるので、x=1に反します。よって、x≧2

参考図1−3

そこで、j=xとし、j≧3とすると、1・x+j・xj+m・xm≧1・3+3・x+6・1=12となり(2)に反します。
よって、x=2と決まります。

従って、という数字が存在するのですが、この個数は1個でないと上記同様(2)に反することになるので、
 x2=1
と決まります。

参考図1−4

さて(4)から、これ以上0でない数字は存在しないことになります。
よって(2)より、
 0・m+1・2+2・1+m・1=10
 4+m=10
従って、mと決まります。

以上から、求める整数A6210001000と決まります。
また、この6210001000は題意を満たすので、求める解となり、またこれ以外に解はありません。

答: 621 0001000

以上


解答例2

高橋 道広さん、 他

本問を次のように一般化して解を求めます。

(問題)

(n+1)個の整数の組があり、

  • xkk=0、・・、n)が 、この整数の組の中にあるk個数に等しい

となるものを求む。

(解)

  • n≦2のとき:解なし
  • n=3のとき:20201210の2個
  • n=4のとき:21200
  • n=5のとき:解なし
  • n≧6のとき:(n-3)210・・(n-6個の 0)1000

 

解答例1と同様に、各桁の数字x0x1、・・・、xnとします。

(a) x0nn+1ではない

  • x0n+1とすると、x0x1=、・・・、=xn= 0となり 、x00x0n+1と矛盾。

  • x0nとすると、x0n、x1=、・・・、=xn= 0となり、nという数字1個存在することになり、xn=0と矛盾。

(b) x(1≦kn)のなかで0でない個数X個とすると 、1≦X

まず、x0≠0が成り立つので、x0という数字1個以上存在します。
従って、1≦X。

xのなかで0でないX個Sとします。
解答例1の(1)と同様、x0x1x2+・・・+xnn+1  ・・・ (1)

また、n個ある各xのなかで0でない個数ということは、
 0の個数であるx0n-Xとなります。 ・・・ (2)

(1)より、
 x0
n+1、
 n-Xn+1、
よって、+1 となります。  ・・・ (3)

(3)より、x1x2、・・・、xnのうちでないX個整数の和+1ということになり、
これらの整数は、1個残り(もしあれば)全て1ということになります。  ・・・ (4)

従って、0でない数字があるとすれば、最も多くて、1、2、n-Xの3個となるので、
 X
≦3となります。

(c) X=1、2、3の各場合に分けて組を求める

参考図2

  • 1のとき

x(k≧1)でないのが1個のみで、その数字はということになります。

ということは、の数字が存在するので、x2>0、従って、x2に他なりません。
よって、x0となり、(2)より、x0n-1、従ってn=3となります。

従って、このケースの解は、2020となります。
 

  • のとき

x(k≧1)でないのが2個で、その数字は
またこの和は+1=だから、考えられるケースは、x1=2、x2またはx1=1、x22通り

  1. x1=2、x2のとき

2個ある数字1のひとつはx0で 、(2)より、x0=1=n-2、よってnとなります。
従って、このケースの解は、1210となります。

  1. x1=1、x2のとき

2個ある数字2のひとつはx0で 、(2)より、x0=2=n-2、よってnとなります。
従って、このケースの解は、21200となります。

  • のとき

x(k≧1)でないのが3個で、その数字はおよびx0n-
このとき、n-3>2となるので、n≧5。

(4)より、x1、x2、xn-3のうち1個、残り2 個となります。
従って、数字12個以上あるので、x1=2、x2=xn-3=1に 他なりません。

従って、このケースの解は、(n-3)210・・(n-6個の 0)1000となります。

とくに、n=9のとき、本問の場合となり、解は6210001 000となります。


解答例3

長野 美光さん、まるケンさん、中村明海さん、kuri、 他

10桁の整数N=N0N1・・・N9に対して、XX0X1・・・X9(XkNkの中でkに等しい数字の個数)を対応させます。
ただし、N0=N1=・・・=N9nのときは、Xn=10、Xk=0(k≠n)となりますが、このときは同様な計算を続けて、X=9 000000001を対応させます。
(なお、この10桁の整数には、0000056789など先頭に0が続く場合を含むことにします。)

参考図3

すると、Xの各桁Xkは0≦Xk≦9となりますので、やはり1 0桁の整数となります。

このとき、ある10桁の整数a1から出発して対応する10桁の整数を次々とつなげていきます。
10桁の整数は有限個ですから、この連鎖はどこかで同じ整数が現れる筈ですので、途中から繰り返しが発生することになります。

この連鎖グループ1と定義します。
また、途中からグループ1に含まれる整数に合流する整数もグループ1に含めることにします。

10桁の整数全てを、このようなグループに分類していくと、必ず有限個のグループに分けられることになります。

参考図3−2

さて、本問では、これらのグループの中に上図グループ3の場合のように、繰り返し周期(対応する整数元の整数と等しいとなるものが存在するので、これを求めなさいということになります。

そこで、適当な整数を出発点に連鎖を計算していけば、どこかで求める整数が見つかる筈です。
では、EXCELを用いて計算してみます。

参考図3−3

すると、上図のように、

  • 63000001007101001000という周期2のものに収束する ・・・ グループ1

  • 6210001000という周期1のものに収束する ・・・ グループ2

2グループに分類できそうです。

従って、グループ2の6210001000が解ということになりそうです。

そこで、本当に上記2グループしかないことを証明してみましょう。

任意10桁の整数に対応する整数は、
 各桁の数字kは、0≦k≦9でかつΣk=0..9k=1 0 ・・・・ (1)
となります。
元の整数この整数同じグループに属するのですから、はじめから(1)の条件が成立する10桁の整数だけを考えても差し支えありません。

さて、もし0でない数字5個以上あったとすると、(1)より、0でない数字合計10になるわけですが、それらの≧1+2+3+4+5=15なので矛盾。

従って、0でない数字4種類以下になります。

参考図3−4

すると、この次に対応する整数6個以上となりますので、最初から6個以上の場合に絞っても差し支えないことになります。

そこで、10桁の整数各桁の合計10となるもので、かつ6個以上の場合について場合分けして調べることにしましょう。
数字を大きい順に並べても次に対応する整数は変わりませんで、便宜上、数字の大きい順に表し、また0を省略することにします。

場合分けをすると、次の11種類になります。また、対応する整数も求めてみます。

  1. 91   → 811  → 721  → 7111 → 631

  2. 82   → 811  → 721  → 7111 → 631

  3. 811  → 721  → 7111 → 631

  4. 73   → 811  → 721  → 7111 → 631

  5. 721  → 7111 → 631

  6. 7111 → 631  → 721  → 7111 → 631

  7. 64   → 811  → 721  → 7111 → 631

  8. 631  → 7111 → 631

  9. 622  → 721  → 7111 → 631

  10. 6211 → 6211

  11. 61111→ 541 → 631   → 7111 → 631

以上から、最初に推測した2グループしかないことが分かります。