不定方程式の解

 投稿者：山中和義  投稿日：2014年 7月19日(土)09時44分57秒
  問題
水を入れる3つの容器があります。
それぞれ6リットル、10リットル、15リットルずつ入ります。途中に目盛りはありません。
この容器を使って、23リットルの水をはかりなさい。

考察
不定方程式±Ax±By±Cz=Nを考える。

たとえば、10x+15y-6z=23のとき、(x,y,z)=(2,1,2)なので、10,10,15,-6,-6
これより、
　 6 10 15   P
　-------------
　 0  0  0   0
　 0 10  0   0
　 0  0  0  10
　 0 10  0  10
　 0  0  0  20
　 0  0 15  20
　 0  0  0  35
　 6  0  0  29
　 0  6  0  29
　 6  6  0  23
のような単純な操作で実現できる。操作を式で表すと、10+10+15-6-6=23となる。
この場合、10+10+15=35リットルをサーバーからくみ出しているが、
   S   6 10 15   P
　-------------------
　   0   0  0  0   0
　 -10   0 ⑩  0   0
　   0   6  4  0   0
　   0   6  0  0   4
　   0   0  6  0   4
　  -4   0 ⑩  0   4
　   0   6  4  0   4
　   0   6  0  0   8
　   0   0  0  6   8
　  -9   0  0 ⑮   8
　   0   0  0  0  23
　-------------------
　 -23
とすると、ちょうど23リットルのくみ出しになる。

Ax+By-Cz=N≧max(A,B,C)の非負整数解(x,y,z)が、x+y-z＞0なら可能となる。（予想）

その他に、
6x+10y-15z=23のとき、(x,y,z)=(3,2,1)なので、6,6,6,10,10,-15
15x+6y-10z=23のとき、(x,y,z)=(1,3,1)なので、15,6,6,6,-10
6x-10y-15z=23のとき、(x,y,z)=(8,1,1)なので、6,6,6,6,6,6,6,6,-10,-15
10x-15y-6z=23のとき、(x,y,z)=(5,1,2)なので、10,10,10,10,10,-15,-6,-6
15x-6y-10z=23のとき、(x,y,z)=(3,2,1)なので、15,15,15,-6,-6,-10
（終り）


LET A=6
LET B=10
LET C=15
LET N=23
CALL Solve(A,B,C,N)
PRINT
CALL Solve2(A,B,C,N)
CALL Solve2(B,C,A,N)
CALL Solve2(C,A,B,N)
PRINT
CALL Solve3(A,B,C,N)
CALL Solve3(B,C,A,N)
CALL Solve3(C,A,B,N)
END

!A,B,C,Nは非負整数とする。不定方程式Ax+By+Cz=Nの非負整数解は、
!By+Cz=N-Ax≧0なので、A=0,1,2,3,…,[N/A]として、By+Cz=Mに帰着させる。
EXTERNAL SUB Solve(A,B,C,N) !Ax+By+Cz=N
FOR X=0 TO N/A
   CALL SolveEQU(B,C,N-A*X, Y,Z,K)
   IF K=-1 THEN EXIT FOR
NEXT X
PRINT STR$(A);"x+";STR$(B);"y+";STR$(C);"z=";STR$(N)
IF K=-1 THEN PRINT X;Y;Z ELSE PRINT "解なし"
END SUB


!A,B,C,Nは非負整数とする。不定方程式Ax+By-Cz=Nの非負整数解は、
!Ax+By=N+Cz≧0なので、Z=0,1,2,3,…として、Ax+By=Mに帰着させる。
EXTERNAL SUB Solve2(A,B,C,N) !Ax+By-Cz=N
LET Z=0
DO
   CALL SolveEQU(A,B,N+C*Z, X,Y,K)
   IF K=-1 THEN EXIT DO
   LET Z=Z+1
LOOP
PRINT STR$(A);"x+";STR$(B);"y-";STR$(C);"z=";STR$(N)
IF K=-1 THEN PRINT X;Y;Z ELSE PRINT "解なし"
END SUB


!A,B,C,Nは非負整数とする。不定方程式Ax-By-Cz=Nの非負整数解は、
!Ax-N=By+Cz≧0なので、X=0,1,2,3,…として、By+Cz=Mに帰着させる。
EXTERNAL SUB Solve3(A,B,C,N) !Ax-By-Cz=N
LET X=CEIL(N/A) !Ax-N≧0より
DO
   CALL SolveEQU(B,C,A*X-N, Y,Z,K)
   IF K=-1 THEN EXIT DO
   LET X=X+1
LOOP
PRINT STR$(A);"x-";STR$(B);"y-";STR$(C);"z=";STR$(N)
IF K=-1 THEN PRINT X;Y;Z ELSE PRINT "解なし"
END SUB


EXTERNAL SUB SolveEQU(A,B,N, X,Y,K) !Ax+By=Nの非負整数解
LET K=-1
FOR X=0 TO N/A !Ax+By=N
   LET Y=(N-A*X)/B
   IF Y=INT(Y) THEN EXIT SUB !解
NEXT X
LET K=0 !解なし
END SUB

 		 

Re: 不定方程式の解

 投稿者：山中和義  投稿日：2014年 7月24日(木)20時26分59秒
  > No.3439[元記事へ]

問題
下図のような8×8の格子状の経路を考える。
地点Aから地点Bへ進むとき、交差点を5回曲がる場合の経路は何通りあるか。

　Ａ─・─・─・─・─・─・─・
　│　│　│　│　│　│　│　│
　・─・─・─・─・─・─・─・
　│　│　│　│　│　│　│　│
　・─・─・─・─・─・─・─・
　│　│　│　│　│　│　│　│
　・─・─・─・─・─・─・─・
　│　│　│　│　│　│　│　│
　・─・─・─・─・─・─・─・
　│　│　│　│　│　│　│　│
　・─・─・─・─・─・─・─・
　│　│　│　│　│　│　│　│
　・─・─・─・─・─・─・─・
　│　│　│　│　│　│　│　│
　・─・─・─・─・─・─・─Ｂ

答え
a,b,c,d,e,fは自然数とする。
右にa,下にb,右にc,下にd,右にe,下にf　または　下にa,右にb,下にc,右にd,下にe,右にf
と進むと、曲がる回数は題意を満たす。
これに、a+c+e=7 かつ b+d+f=7
と制限すれば、距離も題意を満たす。
いま、a,c,eを右方向とすると、
(a-1)+(c-1)+(e-1)=4すなわちx+y+z=4の非負整数解を求めると、重複組合せより、H(4+1,2)=15通りである。
下方向b,d,fも同様なので、15×15=225通りとなる。
また、a,c,eを下方向としても、225通りとなる。
よって、225+225=450通り
（終り）


LET S=0 !場合の数
FOR X=0 TO 4 !x+y+z=4より
   FOR Y=0 TO 4-X !y+z=4-xより
      LET Z=4-(X+Y)
      LET S=S+1
      PRINT S; X+1;Y+1;Z+1 !a,c,e
   NEXT Y
NEXT X
END


別解
地点Aから右方向に進むとする。交差点を5回曲がる場合の経路は、
　　　１　２　３　４　５　６
　Ａ→①─・─・─・─・─・─・
　│　↓
１・　②　→　③
　│
２・　　　　　↓
　│
３・　　　　　④　　　→　　　⑤
　│
４・
　│
５・　　　　　　　　　　　　　↓
　│
６・
　│
　・─・─・─・─・─・─・─Ｂ
となる。
上の図の偶数番目の位置を決めれば経路は確定する。
その位置は、横方向と縦方向とも、6箇所から2つ選べばよい。
これより、C(6,2)×C(6,2)=15×15=225通りとなる。
また、地点Aから下方向に進んでも、225通りとなる。
よって、225+225=450通り



---------------------------------------------------

問題
500円、100円、50円、10円、5円、1円の硬貨があります。
この6種類の硬貨をそれぞれ1枚以上使って、あわせて15枚で980円をつくるとき、
何通りつくることができますか。

答え
500円、100円、50円、10円、5円、1円の硬貨の枚数を、a,b,c,d,e,fとする。
500a+100b+50c+10d+5e+f=980から、500(a-1)+100(b-1)+50(c-1)+10(d-1)+5(e-1)+(f-1)=314
a+b+c+d+e+f=15から、(a-1)+(b-1)+(c-1)+(d-1)+(e-1)+(f-1)=9
すなわち、
　500A+100B+50C+10D+5E+F=314、A+B+C+D+E+F=9 の非負整数解を求める
となる。
314の百の位と一の位に注意して、、A=0,F=4　∴a=1,f=5
よって、100B+50C+10D+5E=310より、20B+10C+2D+E=62、B+C+D+E=5
62の一の位に注意して、
E=2,e=3のとき、20B+10C+2D=60、B+C+D=3　∴10B+5C+D=30、B+C+D=3
D=1,d=2のとき、20B+10C+E=60、B+C+E=4
これを解いて、(a,b,c,d,e,f)=(1,4,1,1,3,5)、(1,3,3,2,1,5)
（終り）


FOR B=0 TO 30/10
   FOR C=0 TO (30-10*B)/5
      LET D=30-(10*B+5*C)
      IF B+C+D=3 THEN PRINT B;C;D
   NEXT C
NEXT B
PRINT

FOR B=0 TO 60/20
   FOR C=0 TO (60-20*B)/10
      LET E=60-(20*B+10*C)
      IF B+C+E=4 THEN PRINT B;C;E
   NEXT C
NEXT B

PRINT 500*1 +100*4 +50*1 +10*1 +5*3 +1*5 !検算
PRINT 500*1 +100*3 +50*3 +10*2 +5*1 +1*5

END


別解
　　：
　　：
よって、100B+50C+10D+5E=310より、20B+10C+2D+E=62、B+C+D+E=5
62の一の位の2に注意して、
E=2,e=3のとき、20B+10C+2D=60、B+C+D=3　∴10B+5C+D=30、B+C+D=3
　D=0,1,2,3に注意して、D=0、9B+4C=27、B+C=3
　連立させて、B=3, C=0　∴b=4, c=1, d=1
D=1,d=2のとき、20B+10C+E=60、B+C+E=4
　E=0,1,2,3,4に注意して、E=0、19B+9C=56、B+C=4
　連立させて、B=2, C=2　∴b=3, c=3, e=1

 		 

Re: 不定方程式の解

 投稿者：山中和義  投稿日：2014年 8月 3日(日)06時58分5秒
  > No.3446[元記事へ]


2004年度　高知大理学部　推薦入試
10000円を100円玉、50円玉、10円玉に両替する方法は、何通りあるか。


OPTION ARITHMETIC RATIONAL !多桁の整数
PRINT G100(10000)
END

EXTERNAL FUNCTION G10(N) !不定方程式10a=Nの解の個数
OPTION ARITHMETIC RATIONAL !多桁の整数
IF MOD(N,10)<>0 THEN
   PRINT "10円未満の金額があります。"
   STOP
END IF
LET G10=1 !すべて10円の1通り
END FUNCTION

EXTERNAL FUNCTION G50(N) !10a+50b=N　∴a=N-50bに帰着させる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/50) !50円の枚数
   LET S=S+G10(N-50*K) !残りは、10円でつくる
NEXT K
LET G50=S
END FUNCTION

EXTERNAL FUNCTION G100(N) !10a+50b+100c=N　∴10a+50b=N-100cに帰着させる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/100) !100円の枚数
   LET S=S+G50(N-100*K) !残りは、50円,10円でつくる
NEXT K
LET G100=S
END FUNCTION



多重FOR文による


OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=10000
LET S=0
FOR C100=0 TO N/100 !100円玉の枚数
   FOR C50=0 TO (N-100*C100)/50 !50円玉の枚数
      LET S=S+1 !10円玉は1通り
   NEXT C50
NEXT C100
PRINT S; "通り"
END



-------------------------------------------------------------------

500円の100円玉、50円玉、10円玉、5円玉、1円玉への両替方法は、19161通りである。


OPTION ARITHMETIC RATIONAL !多桁の整数
PRINT F100(500)
END

!不定方程式 a+5b+10c+50d+100e+500f+1000g+5000h+10000i=N の解の個数

EXTERNAL FUNCTION F1(N) !1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET F1=1 !すべて1円の1通り
END FUNCTION

EXTERNAL FUNCTION F5(N) !5円,1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/5) !5円の枚数
   LET S=S+F1(N-5*K) !残りは、1円でつくる
NEXT K
LET F5=S
END FUNCTION

EXTERNAL FUNCTION F10(N) !10円,5円,1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/10) !10円の枚数
   LET S=S+F5(N-10*K) !残りは、5円,1円でつくる
NEXT K
LET F10=S
END FUNCTION

EXTERNAL FUNCTION F50(N) !50円,10円,5円,1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/50) !50円の枚数
   LET S=S+F10(N-50*K) !残りは、10円,5円,1円でつくる
NEXT K
LET F50=S
END FUNCTION

EXTERNAL FUNCTION F100(N) !100円,50円,10円,5円,1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/100)
   LET S=S+F50(N-100*K)
NEXT K
LET F100=S
END FUNCTION

EXTERNAL FUNCTION F500(N) !500円,100円,50円,10円,5円,1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/500)
   LET S=S+F100(N-500*K)
NEXT K
LET F500=S
END FUNCTION

EXTERNAL FUNCTION F1000(N) !1000円,500円,100円,50円,10円,5円,1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/1000)
   LET S=S+F500(N-1000*K)
NEXT K
LET F1000=S
END FUNCTION

EXTERNAL FUNCTION F5000(N) !5000円,1000円,500円,100円,50円,10円,5円,1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/5000)
   LET S=S+F1000(N-5000*K)
NEXT K
LET F5000=S
END FUNCTION

EXTERNAL FUNCTION F10000(N) !10000円,5000円,1000円,500円,100円,50円,10円,5円,1円の硬貨で、n円をつくる
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR K=0 TO INT(N/10000)
   LET S=S+F5000(N-10000*K)
NEXT K
LET F10000=S
END FUNCTION



多重FOR文による


OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=500
LET S=0
FOR C100=0 TO N/100 !100円玉の枚数
   LET R50=N-100*C100 !残り
   FOR C50=0 TO R50/50 !50円玉
      LET R10=R50-50*C50
      FOR C10=0 TO R10/10 !10円玉
         LET R5=R10-10*C10
         !!FOR C5=0 TO R5/5 !5円玉
         !!   LET S=S+1 !1円玉は1通り
         !!NEXT C5
         LET S=S+(R5/5+1) !5円玉
      NEXT C10
   NEXT C50
NEXT C100
PRINT S; "通り"
END


 		 

Re: 不定方程式の解

 投稿者：山中和義  投稿日：2014年 8月 4日(月)10時14分29秒
  > No.3449[元記事へ]


つづき

10000円の5000札、1000円札、500円玉、100円玉、50円玉、10円玉、5円玉、1円玉への両替方法は、
18155171408通りある。

関数の呼出し、かけ算・割り算の負荷を避けて、次のように記述しました。


OPTION ARITHMETIC RATIONAL !多桁の整数
LET M=10000 !金額
LET S=0
FOR C5000=0 TO M STEP 5000 !0,5000,10000,15000,…
   LET T5000=M-C5000 !残りの金額に対して
   FOR C1000=0 TO T5000 STEP 1000
      LET T1000=T5000-C1000
      FOR C500=0 TO T1000 STEP 500
         LET T500=T1000-C500
         FOR C100=0 TO T500 STEP 100
            LET T100=T500-C100
            FOR C50=0 TO T100 STEP 50
               LET T50=T100-C50
               FOR C10=0 TO T50 STEP 10
                  LET T10=T50-C10
                  LET S=S+INT(T10/5)+1 ! !0,5,10,15,…　※5n円を5,1円で両替する　n+1通り
               NEXT C10
            NEXT C50
         NEXT C100
      NEXT C500
   NEXT C1000
NEXT C5000
PRINT S;"通り" !18155171408 通り
END



参考サイト
　コロキウム室　http://www2.ocn.ne.jp/~mizuryu/renzoku.html　第196回数学的な応募問題

 		 

Re: 不定方程式の解

 投稿者：山中和義  投稿日：2014年 8月22日(金)19時24分8秒
  > No.3450[元記事へ]

問題
4つの正の整数a,b,c,dを
　a b
　c d
と並べて、たすきに掛けた数が、ad+1=bcを満たすとする。
a=d=1のとき、b,cを求めよ。

答え
ad+1=bcより、2=bc　∴(b,c)=(2,1),(1,2)
（終り）


問題
6つの正の整数a,b,c,d,e,fを
　a b c
　d e f
と並べて、たすきに掛けた数が、ae+1=bd、bf+1=ceを満たすとする。
a=f=1のとき、b,c,d,eを求めよ。

答え
　1        k  (k+1)/A
　(A+1)/k  A  1
と、kを(A+1)の約数とすると、1つの変数Aで表せる。
A=1のとき、
　　1    k  k+1
　　2/k  1  1
　なので、k=1,2
　並びは、
　　1  1  2　　　1  2  3
　　2  1  1　　　1  1  1
A=2のとき、
　　1    k  (k+1)/2
　　3/k  2  1
　なので、k=1,3
　並びは、
　　1  1  1　　　1  3  2
　　3  2  1　　　1  2  1
A=3のとき、
　　1    k  (k+1)/3
　　4/k  3  1
　なので、k=2
　並びは、
　　1  2  1
　　2  3  1
A=4のとき、
　　：
　　：


FOR A=1 TO 50
   FOR K=1 TO A+1
      IF MOD(A+1,K)=0 THEN

         IF MOD(K+1,A)=0 THEN
            PRINT 1;K;(K+1)/A
            PRINT (A+1)/K;A;1
            PRINT
         END IF

      END IF
   NEXT K
NEXT A
END


ところで、A≧3のとき、
kは(A+1)の約数なので、1≦k≦A+1　∴2≦k+1≦A+2
右端上(k+1)/A≦(A+2)/A=1+2/A　A≧3から、正の整数になるのは、1のみである。
よって、(k+1)/A=1　∴k=A-1
左端下(A+1)/k=(A+1)/(A-1)=1+2/(A-1)
これが正の整数になるには、A=3のみである。
したがって、
　1  2  1
　2  3  1
のみとなる。
（終り）


対称性
　a b c … d
　e f g … h
が題意を満たすなら、
　h … g f e
　d … c b a
も題意を満たす。



問題
8つの正の整数a,b,c,d,e,f,g,hを
　a b c d
　e f g h
と並べて、たすきに掛けた数が、af+1=be、bg+1=cf、ch+1=dgを満たすとする。
a=h=1のとき、b,c,d,e,f,gを求めよ。

答え
2つの変数A,Bで
　1        k  B  (B+1)/m
　(A+1)/k  A  m  1
として、


FOR A=1 TO 50
   FOR B=1 TO A !対称性

      FOR K=1 TO A+1
         IF MOD(A+1,K)=0 THEN
            FOR M=1 TO B+1
               IF MOD(B+1,M)=0 THEN

                  IF K*M+1=A*B THEN
                     PRINT 1;K;B;(B+1)/M
                     PRINT (A+1)/K;A;M;1
                     PRINT
                  END IF

               END IF
            NEXT M
         END IF
      NEXT K

   NEXT B
NEXT A
END

実行結果

1  1  1  2
3  2  1  1

1  1  2  1  ※1
3  2  3  1

1  3  2  3  ※1
1  2  1  1

1  1  1  1
4  3  2  1

1  2  1  2
2  3  1  1

1  2  3  1  ※2
2  3  4  1

1  4  3  2  ※2
1  3  2  1

1  2  1  1
3  5  2  1

1  3  2  1
2  5  3  1


※は対称となるので、14通り



問題
2n個の正の整数a[1],a[2],…,a[n],b[1],b[2],…,b[n]を
　a[1],a[2],…,a[n]
　b[1],b[2],…,b[n]
と並べて、たすきに掛けた数が、
a[1]b[2]+1=a[2]b[1]、a[2]b[3]+1=a[3]b[2]、…、a[n-1]b[n]+1=a[n]b[n-1]を満たすとする。
a[1]=b[n]=1のとき、a[2],a[3],…,a[n],b[1],b[2],…,b[n-1]を求めよ。

予想
●個数
C(2n,n)/(n+1)、すなわち、カタラン数

●並びの生成方法
n=2のとき
並び
　1 2　　　1 1
　1 1　　　2 1
なので、
　1/1 2/1　　　1/2 1/1
のように、上段を分子、下段を分母とする分数で表すと、
分数列 1/2  1/1  2/1
　　　　└─┘└─┘
から、1/1を含んで連続する2項を選んだと解釈できる。


n=3のとき
　1  1  2　　　　1  2  3
　2  1  1　　　　1  1  1
なので、
　1/2 1/1 2/1　　　1/1 2/1 3/1

　1  1  1　　　　1  3  2
　3  2  1　　　　1  2  1
なので、
　1/3 1/2 1/1　　　1/1 3/2 2/1

　1  2  1
　2  3  1
なので、
　1/2 2/3 1/1

　　　　┌───┐ ┌───┐
分数列 1/3  1/2  1/1  2/1  3/1
　　　　　　└─┘ └─┘
　　　　　　└─────┘
から、1/1を含んで連続する2項または3項を選んだと解釈できる。
2項の場合は、中間分数を考える。

補足　1:1の中間分数（隣り合う分数）
並び
　a  c
　b  d
が、ad+1=bcを満たすとする。
このとき、
　a  a+c  c
　b  b+d  d
を考える。
ad+1=bcの両辺にabをたして、ab+ad+1=ab+bc　∴a(b+d)+1=b(a+c)
ad+1=bcの両辺にcdをたして、ad+1+cd=bc+cd　∴(a+c)d+1=(b+d)c
これより、題意を満たして列を増やすことができる。
（終り）

参考サイト
　　私の備忘録
　　　数学・・・代数学分野

 		 

Re: 不定方程式の解

 投稿者：山中和義  投稿日：2014年 8月24日(日)19時14分13秒
  > No.3464[元記事へ]

> 問題
> 2n個の正の整数a[1],a[2],…,a[n],b[1],b[2],…,b[n]を
> 　a[1],a[2],…,a[n]
> 　b[1],b[2],…,b[n]
> と並べて、たすきに掛けた数が、
> a[1]b[2]+1=a[2]b[1]、a[2]b[3]+1=a[3]b[2]、…、a[n-1]b[n]+1=a[n]b[n-1]を満たすとする。
> a[1]=b[n]=1のとき、a[2],a[3],…,a[n],b[1],b[2],…,b[n-1]を求めよ。

自明な解
その１
1 2 3 … n-1 n
1 1 1 … 1   1

その２
フィボナッチ数列　1,1,2,3,5,8,13,21,34,55,… を、

　          n :  ①   ③   ⑤   ⑦     ⑨　　            ⑧     ⑥    ④   ②
　a[n+1]/a[n] :  1/1, 3/2, 8/5, 21/13, 55/34, …,φ, …, 34/21, 13/8, 5/3, 2/1

のように、φを中心として左右交互に並べる。

 		 

Re: 不定方程式の解

 投稿者：山中和義  投稿日：2014年 8月28日(木)06時30分31秒
  > No.3465[元記事へ]

問題
n個のさいころを投げて、出たn個の目の積が6の倍数である確率を求めよ。

答え
少なくとも1つが偶数 かつ 少なくとも1つが3の倍数 であればよい。
その確率は、余事象から、(1-(1/2)^n)(1-(2/3)^n)
（終り）


その他の解法

●漸化式による
3個のさいころを大,中,小とする。
まず、大,中の積が、
　2の倍数になるのは、27通り
　3の倍数になるのは、20通り
　6の倍数になるのは、15通り
である。
残りの小の目が、
1,5の場合、大,中の積が6の倍数のとき、15×2通り
2,4の場合、大,中の積が3の倍数のとき、20×2通り
3の場合、大,中の積が2の倍数のとき、27通り
6の場合、大,中の積は何でもよいので、6^2=36通り
よって、15×2+20×2+27+36=133通り


FOR N=1 TO 10
   PRINT N; f6(N); f6(N)/6^N; (1-(1/2)^N)*(1-(2/3)^N)
NEXT N
END

EXTERNAL FUNCTION f2(n) !2の倍数
IF N=1 THEN
   LET f2=3 !2,4,6
ELSE
!n番目について、
!1,3,5のとき、(n-1)番までが2の倍数なら、2の倍数になる。
!2,4,6のとき、(n-1)番までは何でも良い。
   LET f2=3*f2(n-1)+3*6^(n-1)
END IF
END FUNCTION

EXTERNAL FUNCTION f3(n) !3の倍数
IF N=1 THEN
   LET f3=2 !3,6
ELSE
!1,2,4,5のとき、(n-1)番までが3の倍数
!3,6のとき、(n-1)番までは何でも良い
   LET f3=4*f3(n-1)+2*6^(n-1)
END IF
END FUNCTION

EXTERNAL FUNCTION f6(n) !6の倍数
IF N=1 THEN
   LET f6=1 !6
ELSE
!1,5のとき、(n-1)番までが6の倍数
!2,4のとき、(n-1)番までが3の倍数
!3のとき、(n-1)番までが2の倍数
!6のとき、(n-1)番までは何でも良い
   LET f6=2*f6(n-1)+2*f3(n-1)+1*f2(n-1)+1*6^(n-1)
END IF
END FUNCTION


●不定方程式 x[1]x[2]x[3]…x[n]=m、1≦x[1]≦x[2]≦x[3]≦…≦x[n]≦6 の解
例　n=3のとき、xyz=6k

LET N=3 !n個の変数
DIM X(0 TO N) !※0番目は番兵
LET X(0)=1
PUBLIC NUMERIC C,S
LET C=0
LET S=0
LET K=1
DO WHILE 6*K<=6^N
   CALL try(1, N,X,6*K)
   LET K=K+1
LOOP
PRINT C;"通り"
PRINT S;"通り" !場合の数
END

EXTERNAL SUB try(P, N,X(),M) !x[1]x[2]x[3]…x[n]=m の解
IF P=N THEN !最後の変数のとき
   IF X(P-1)<=M AND M<=6 THEN
      LET X(P)=M
      LET C=C+1
      MAT PRINT X;

      DIM B(6) !n!/(p!q!…r!)通りに並べる
      MAT B=ZER
      FOR i=1 TO N
         LET B(X(i))=B(X(i))+1
      NEXT i
      LET S=S+PermFactorialM(B,6)
   END IF
ELSE
   FOR K=X(P-1) TO 6 !昇順
      IF MOD(M,K)=0 THEN !約数なら
         LET X(P)=K
         CALL try(P+1, N,X,M/K) !次へ
      END IF
   NEXT K
END IF
END SUB


!COMB.LIB 抜粋

EXTERNAL FUNCTION PermFactorialM(B(),M) !同じものを含む順列の「場合の数」
LET s=B(M) !総数 r, … ,q+ … +r,p+q+ … +r
LET t=1 !組合せ comb(r,r), … ,comb(q+ … +r,q),comb(p+q+ … +r,p)
FOR i=M-1 TO 1 STEP -1
   LET s=s+B(i)
   LET t=t*COMB(s,B(i)) !組合せ順列
NEXT i
LET PermFactorialM=t
END FUNCTION



-----------------------------------------

発展問題
n個のさいころを投げて、出たn個の目の積が立方数となる場合の数を求めよ。

答え
不定方程式版のプログラムを

　：
LET S=0
LET K=1
DO WHILE K^3<=6^N
   CALL try(1, N,X,K^3)
   LET K=K+1
LOOP
PRINT C;"通り"
　：

と変更して、実行する。


類題
大中小3個のさいころを投げるとき、目の積が60になるのは何通りあるか。
答え
　：
LET S=0
CALL try(1, N,X,60)
PRINT C;"通り"
　：
（終り）


別解
(1+x+y+x^2+z+xy)^n を展開したとき、
　x^(3a) y^(3b) z^(3c)
という形にかける項の係数をすべて足し合わせたものになる。
（終り）


OPTION ARITHMETIC COMPLEX !複素数を扱う
LET N=2 !さいころの個数
LET K=3 !k乗
LET w=EXP(2*PI*COMPLEX(0,1)/K) !w^k-1=0
LET S=0
FOR A=0 TO K-1
   FOR B=0 TO K-1
      FOR C=0 TO K-1
         LET S=S+(1+w^A+w^B+w^(2*A)+w^C+w^(A+B))^N
      NEXT C
   NEXT B
NEXT A
S=S/K^3 !場合の数
PRINT S
END


 		 

Re: 不定方程式の解

 投稿者：山中和義  投稿日：2014年 9月13日(土)13時28分42秒
  > No.3474[元記事へ]

問題
a,b,c,dは、整数とする。

行列式
| a  b | = 1
| c  d |

| a^2  b^2 | = 1
| c^2  d^2 |

を満たすものを探しなさい。

答え
ad-bc=1
a^2d^2-b^2c^2=(ad-bc)(ad+bc)=ad+bc=1
連立方程式を解いて、ad=1、bc=0　∴a=d=±1 かつ（ b=0 または c=0 ）
よって、
| ±1    0 | = | 1    0 | = 1
|   c  ±1 |   | c^2  1 |
または、
| ±1    b | = | 1  b^2 | = 1
|   0  ±1 |   | 0  1   |
ただし、複号同順とする。
（終り）


--------------------------------------------------------------

問題
a,b,c,d,e,f,g,h,iは、2以上10以下の整数とする。

行列式
| a  b  c | = 1
| d  e  f |
| g  h  i |

| a^2  b^2  c^2 | = 1
| d^2  e^2  f^2 |
| g^2  h^2  i^2 |

を満たすものを探しなさい。

答え
9^9=387420489通りの検索になるが、工夫して計算量を減らす。

　a b c　　転置　　a d g
　d e f　　→　　　b e h
　g h i　　　　　　c f i

　　↓180°回転　　　↓180°回転

　i h g　　転置　　i f c
　f e d　　→　　　h e b
　c b a　　　　　　g d a

式で表すと、
　aei+bfg+cdh-ceg-bdi-afh　→　aei+dhc+gbf-gec-dbi-ahf
　　　　　　↓　　　　　　　　　　　　　　↓
　iea+hdc+gfb-gec-hfa-idb　→　iea+fbg+chd-ceg-fha-ibd

は同値なので、
　2≦c≦g≦9、2≦a≦i≦9
とする。


また、
| a  b  c | = a| e f |- b| d f | +c| d e |
| d  e  f |    | h i |   | g i |   | g h |
| g  h  i |
P1=ei-fh、P2=di-fg、P3=dh-egとすると、
=aP1-bP2+cP3
X=aP1, Y=bP2, Z=cP3 とすると、
=X-Y+Z

| a^2  b^2  c^2 | = a^2| e^2 f^2 | - b^2| d^2 f^2 | +c^2| d^2 e^2 |
| d^2  e^2  f^2 |      | h^2 i^2 |      | g^2 i^2 |     | g^2 h^2 |
| g^2  h^2  i^2 |
Q1=ei+fh、Q2=di+fg、Q3=dh+egとすると、e^2i^2-f^2h^2=(ei-fh)(ei+fh)など より、
=aP1aQ1-bP1bQ2+cP3cQ3
X'=aQ1, Y'=bQ2, Z'=cQ3 とすると、
=XX'-YY'+ZZ'

よって、不定方程式
　X-Y+Z=1
　XX'-YY'+ZZ'=1
を得る。


LET S=0
FOR E=2 TO 10
   FOR i=2 TO 10
      FOR F=2 TO 10
         FOR H=2 TO 10
            LET P1=E*i-F*H
            LET Q1=E*i+F*H
            FOR D=2 TO 10
               FOR G=2 TO 10
                  LET P2=D*i-F*G
                  LET Q2=D*i+F*G
                  LET P3=D*H-E*G
                  LET Q3=D*H+E*G

                  FOR A=2 TO i !対称性（180°回転）
                     LET X=A*P1
                     LET XX=A*Q1
                     FOR C=2 TO G !対称性（転置）
                        LET Z=C*P3
                        LET ZZ=C*Q3
                        FOR B=2 TO 10
                           LET Y=B*P2
                           LET YY=B*Q2
                           IF X-Y+Z=1 AND X*XX-Y*YY+Z*ZZ=1 THEN !題意を満たすもの

                              IF A=i AND C=G THEN !対称性（転置、180°回転）
                                 IF D>=B AND H>=B THEN
                                    PRINT A;B;C
                                    PRINT D;E;F
                                    PRINT G;H;i
                                    PRINT
                                    LET S=S+1
                                 END IF
                              ELSE
                                 PRINT A;B;C
                                 PRINT D;E;F
                                 PRINT G;H;i
                                 PRINT
                                 LET S=S+1
                              END IF

                           END IF
                        NEXT B
                     NEXT C
                  NEXT A

               NEXT G
            NEXT D
         NEXT H
      NEXT F
   NEXT i
NEXT E
PRINT S; "通り"
END


実行結果

4  3  2
2  2  3
9  7  6

4  2  3
9  2  5
10  3  6

2  4  3
3  2  2
6  9  7

2  3  5
3  2  3
9  5  7

2  3  2
4  2  3
9  6  7

2  3  3
3  2  5
5  9  7

5  3  6
2  2  3
9  4  10

4  3  4
5  3  3
9  5  4

5  2  3
9  3  2
7  3  5

5  2  3
3  3  2
7  9  5

3  2  3
5  3  2
7  5  9

3  2  4
2  3  2
7  6  9

3  5  2
2  3  3
5  7  9

3  2  2
2  3  4
6  7  9

3  4  4
3  3  5
5  4  9

3  2  2
6  3  5
10  4  9

3  2  4
6  3  10
5  2  9

3  5  3
3  4  4
5  9  4

5  3  3
4  4  3
9  4  5

2  2  3
3  4  2
7  9  6

2  2  3
9  4  10
5  3  6

3  9  2
2  5  3
3  7  5

3  3  2
2  5  3
9  7  5

4  4  3
3  5  3
4  9  5

2  2  3
3  5  6
4  9  10

2  3  2
5  6  3
9  10  4

2  3  2
7  6  9
3  2  4

2  6  3
3  7  2
4  9  2

2  2  3
9  7  6
4  3  2

2  3  3
5  7  9
3  5  2

3  4  2
5  9  2
6  10  3

3  5  2
2  9  3
5  7  3

3  2  2
10  9  4
6  5  3

3  3  2
7  9  5
5  2  3

3  5  3
4  9  5
4  4  3

3  2  2
6  9  7
2  4  3

2  3  2
4  10  9
3  6  5

37 通り


 		 

戻る