組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月14日(木)10時10分41秒
  問題
4つの相異なる4桁の正整数がある。
千の位は4つとも全て等しく、一の位も4つとも全て等しい。
また、このうち3つの数は、4つの数の和の約数になっている。
このような4つの数を求めよ。
答え
1080, 1170, 1350, 1800


FOR X=1 TO 9 !千の位　条件1
   FOR Y=0 TO 9 !一の位
      FOR A=0 TO 99-3 !百と十の位
         LET N1=X*1000+A*10+Y !xaay
         FOR B=A+1 TO 99-2
            LET N2=X*1000+B*10+Y !xbby
            FOR C=B+1 TO 99-1
               LET N3=X*1000+C*10+Y !xccy
               FOR D=C+1 TO 99
                  LET N4=X*1000+D*10+Y !xddy
                  LET S=N1+N2+N3+N4

                  IF MOD(S,N1)=0 THEN !条件2
                     IF MOD(S,N2)=0 THEN
                        IF MOD(S,N3)=0 THEN
                           PRINT N1;N2;N3;N4; "タイプ１"
                        ELSE
                           IF MOD(S,N4)=0 THEN PRINT N1;N2;N3;N4; "タイプ２"
                        END IF
                     ELSE
                        IF MOD(S,N3)=0 AND MOD(S,N4)=0 THEN PRINT N1;N2;N3;N4; "タイプ３"
                     END IF
                  ELSE
                     IF MOD(S,N2)=0 AND MOD(S,N3)=0 AND MOD(S,N4)=0 THEN PRINT N1;N2;N3;N4; "タイプ４"
                  END IF

               NEXT D
            NEXT C
         NEXT B
      NEXT A
   NEXT Y
NEXT X
END




問題
A={1,2,3,4,5,6,7,8,9}とするとき、次の条件を満たすAの部分集合Sを求めよ。
(1) Sの要素は5個である。
(2) Sの相異なる2つの要素を取り出して和を作ると、その一位の数が1から9までの数がすべて現れる。
答え
(1,3,4,5,8), (1,5,6,7,8), (2,3,4,5,9), (2,5,6,7,9)


DIM F(0 TO 9) !一の位の数字

DIM S(5) !集合S
FOR A=1 TO 9 !条件1　C(9,5)=126通り
   LET S(1)=A
   FOR B=A+1 TO 9-3
      LET S(2)=B
      FOR C=B+1 TO 9-2
         LET S(3)=C
         FOR D=C+1 TO 9-1
            LET S(4)=D
            FOR E=D+1 TO 9
               LET S(5)=E

               MAT F=ZER !条件2　C(5,2)=10通り
               FOR X=1 TO 5-1
                  FOR Y=X+1 TO 5
                     LET T=MOD(S(X)+S(Y),10)
                     LET F(T)=1
                  NEXT Y
               NEXT X
               FOR i=1 TO 9
                  IF F(i)=0 THEN EXIT FOR
               NEXT i
               IF F(0)=0 AND i>9 THEN MAT PRINT S;

            NEXT E
         NEXT D
      NEXT C
   NEXT B
NEXT A

END


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月16日(土)19時11分46秒
  > No.3691[元記事へ]

問題　2008年灘中学入試
1個66円のかきと1個35円のみかんを、合わせて3890円分買いました。
かきとみかんはそれぞれ何個ずつ買いましたか。

答え
かき 25個、みかん 64個



その１　(つる+かめ)算 - 両方の個数を仮定する

答え
35の倍数の一の位は、35は5の倍数なので、0または5である。
66は偶数なので、66の倍数は一の位が奇数5にはならない。
これより、3890の一の位は0なので、35の倍数の一の位は0でないといけない。
よって、yは0,2,4,6,8,…である。
同様に、
これより、3890の一の位は0なので、66の倍数の一の位は0でないといけない。
よって、xは0,5,10,15,20,…である。
（終り）

答え
かきをx個、みかんをy個買ったとする。
66x+35y=3890より、66x=3890-35y=5(778-7y)、35y=3890-66x=2(1945-33x)
xは5の倍数、yは2の倍数
（終り）


LET A=66
LET B=35
LET C=3890
FOR X=0 TO C/A STEP 5
   FOR Y=0 TO C/B STEP 2
      LET T=A*X+B*Y
      IF T>=C THEN EXIT FOR
   NEXT Y
   IF T=C THEN PRINT X;Y
NEXT X
END




その２　つる算（かめ算） - 一方の個数を仮定すると、他方は残りである

答え
かきをx個、みかんをy個買ったとすると、3890-66x=35y
(3890-66x)は、35=5×7なので、5の倍数となる。これより、一の位は0または5となる。
66は偶数なので、66の倍数は一の位が奇数5にはならない。
0となるのは、0,5,10,15,20,…と5の倍数の数をかけた場合である。
このとき、(3890-66x)が7の倍数となることを確認する。
（終り）


LET A=66
LET B=35
LET C=3890
FOR X=0 TO C/A STEP 5
   LET T=(C-A*X)/5
   IF MOD(T,7)=0 THEN PRINT X;T/7
NEXT X
END




その３　つるかめ算

66が偶数、35が奇数、3890が偶数なので、みかんは偶数個である。
これより、66x+70Y=3890と表される。
すべて安い方（かき）を買ったとすると、3890÷66=58あまり62
すべて高い方（みかん）を買ったとすると、3890÷70=55あまり40
なので、個数の合計は56,57,58個となる。
70-66=4円でかき1個をみかん2個に取り換えられる。
56個の場合、3890=66×56+194より、194÷4=48.5　取り替えられないので、不適である。
57個の場合、3890=66×57+128より、128÷4=32　みかんは32×2=64個　かきは57-32=25個
58個の場合、3890=66×58+62より、62÷4=15.5　取り替えられないので、不適である。


LET A=66
LET B=35
LET C=3890
LET M=CEIL(A/B)*B-A
PRINT M
LET P=MAX(A,2*B)
LET Q=MIN(A,2*B)
FOR T=CEIL(C/P) TO INT(C/Q) !置き換えていく
   LET R=C-Q*T
   !!!PRINT T;R
   IF MOD(R,M)=0 THEN !約数なら
      LET K=R/M
      PRINT T-K; 2*K !x,Y
   END IF
NEXT T
END


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月20日(水)09時37分57秒
  > No.3692[元記事へ]

問題　2008年 名古屋大学（文系）前期
3x+2y≦2008を満たす0以上の整数の組(x,y)の個数を求めよ。


その１
x=0,1,2,3,4,…として、それぞれyの個数を求める。


LET A=3
LET B=2
LET C=2008

LET S=0
FOR X=0 TO C/A
   LET Y=INT((C-A*X)/B)+1
   PRINT X;Y
   LET S=S+Y
NEXT X
PRINT S;"通り"

END




その２
上記で算出したyの値を、数列として考える。
差は、2,1,2,1,2,…となって、等差数列とはならないが、次のように考えるとうまくいく。
この規則性に気づくことで、小学生向けの問題となる。

偶数番目
　1005,1002,999,…,9,6,3
奇数番目
　1003,1000,997,…,7,4,1
それぞれ公差3、項数(669+1)/2=335の等差数列である。
よって、((1005+3)+(1003+1))×335÷2=337010
（終り）


DEF F(X)=INT((C-A*X)/B)+1 !x=Xのとき、yの個数

LET A=3
LET B=2
LET C=2008

LET S=0

LET K=CEIL(C/A) !K=B*Q+R
LET Q=INT(K/B)
LET R=MOD(K,B)
PRINT K;Q;R

FOR i=0 TO B-1 !B種類、共通な項数Qの部分
   LET W=F(i)
   PRINT W
   LET S=S+(2*W+(Q-1)*(-A))*Q/2  !公差d、p項の和は、{a[1]+(a[1]+(p-1)d)}p/2
NEXT i

FOR i=0 TO R !残り
   LET W=F(B*Q+i)
   PRINT W
   LET S=S+W
NEXT i

PRINT S;"通り"

END


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月23日(土)09時25分4秒
  > No.3697[元記事へ]

おつりの硬貨の枚数を減らす


たかしさんは、お姉さんと買い物に行きました。品物の代金は630円でした。
たかしさんは、おつりの硬貨の枚数を少なくするために、
お金の出し方をくふうして、1000円札に30円を加えて出そうとしました。
すると、お姉さんが
　「1030円に、あと100円加えたら、おつりの硬貨の枚数がもっと少なくなるよ。」
と言いました。



LET A=630
PRINT "請求された金額=";A;"円"
PRINT

!ケース１
FOR K=1 TO 4 !1234のとき、1235,1250,1500,5000と払う
   LET W=10^K
   LET B=CEIL(A/W)*W-W/2
   IF B>=A THEN
      PRINT "支払った金額=";B;"円"
      PRINT "おつり=";B-A;"円"
      PRINT F(B)-F(B-A);"枚減る"
   END IF
   IF W>A THEN EXIT FOR !払いすぎた
NEXT K
PRINT


!ケース２
FOR K=1 TO 4 !1234のとき、1240,1300,2000,10000と払う
   LET W=10^K
   LET B=CEIL(A/W)*W
   PRINT "支払った金額=";B;"円"
   PRINT "おつり=";B-A;"円"
   PRINT F(B)-F(B-A);"枚減る"
   IF W>A THEN EXIT FOR !払いすぎた
NEXT K
PRINT


!ケース３
DATA 5,50,500,5000 !5,50,500,5000円がおつりになるようにする
DIM Q(4)
MAT READ Q
FOR P=0 TO 2^4-1 !2^4=16通り
   LET T=P
   LET B=0
   FOR K=1 TO 4
      IF MOD(T,2)=1 THEN LET B=B+Q(K)
      LET T=INT(T/2)
   NEXT K

   IF B>A THEN EXIT FOR !払いすぎた

   PRINT "支払った金額=";A+B;"円"
   PRINT "おつり=";B;"円"
   PRINT F(A+B)-F(B);"枚減る"
NEXT P

END


EXTERNAL FUNCTION F(N) !金額nに対する硬貨の枚数を返す
DATA 10000,5000,1000,500,100,50,10,5,1 !金種　※大きい順
LET C=0
DO WHILE N>0
   READ P
   LET C=C+INT(N/P)
   LET N=MOD(N,P) !次へ
LOOP
LET F=C
END FUNCTION



実行結果

請求された金額= 630 円

支払った金額= 650 円
おつり= 20 円
1 枚減る

支払った金額= 630 円
おつり= 0 円
5 枚減る
支払った金額= 700 円
おつり= 70 円
0 枚減る
支払った金額= 1000 円
おつり= 370 円
-5 枚減る

支払った金額= 630 円
おつり= 0 円
5 枚減る
支払った金額= 635 円
おつり= 5 円
5 枚減る
支払った金額= 680 円
おつり= 50 円
5 枚減る
支払った金額= 685 円
おつり= 55 円
5 枚減る
支払った金額= 1130 円
おつり= 500 円
4 枚減る
支払った金額= 1135 円
おつり= 505 円
4 枚減る
支払った金額= 1180 円
おつり= 550 円
4 枚減る
支払った金額= 1185 円
おつり= 555 円


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月25日(月)10時54分46秒
  > No.3701[元記事へ]

電線にすずめが３羽とまってた(^^♪


問題
つがいのすずめがn組います。2n匹が電線に並びました。
オスはやきもち焼きで、つがいのメスが他のオスと（隣に自分がいても）隣り合うのを嫌います。
そうならないような並べ方は何通りありますか。
例
大文字をオス、小文字をメスとして、つがいをAとa、Bとbとする。
ABba、AabBは題意を満たすが、AaBb、AbBaは不適となる。

2組Aa,Bbの場合
　ABba、AabB、abBA、aABb
　BAab、BbaA、baAB、bBAa
の8通り

参考サイト　http://oeis.org/A096121



LET N=3 !つがいの数

DIM A(N),B(N) !オス、メス
MAT A=CON !A,B,C,…
MAT B=CON !a,b,c,…

PUBLIC NUMERIC C !場合の数
LET C=0

DIM P(2*N) !並び

LET P(1)=1 !オス（A）から始まる　※オスは正、メスは負で表す
LET A(1)=0
CALL try(2,N,P,A,B)

PRINT C;"通り"
PRINT 2*N*C;"通り" !Aとa、n組

END

EXTERNAL SUB try(K,N,P(),A(),B()) !バックトラック法で検索する
IF K>2*N THEN !すべて並んだ
   LET C=C+1
   MAT PRINT P;

ELSE
   LET W=P(K-1) !1つ前

   IF W>0 THEN !オス（A）なら
      FOR i=1 TO N !他のオスを並べる
         IF A(i)>0 THEN
            LET P(K)=i !B
            LET A(i)=0
            CALL try(K+1,N,P,A,B) !次へ
            LET A(i)=1 !元に戻す
         END IF
      NEXT i
      IF B(W)>0 THEN !つがいのメスを並べる
         LET P(K)=-W !a
         LET B(W)=0
         CALL try(K+1,N,P,A,B)
         LET B(W)=1
      END IF

   ELSE !メス（a）なら
      FOR i=1 TO N !他のメスを並べる
         IF B(i)>0 THEN
            LET P(K)=-i
            LET B(i)=0 !b
            CALL try(K+1,N,P,A,B)
            LET B(i)=1
         END IF
      NEXT i
      IF A(-W)>0 THEN !つがいのオスを並べる
         LET P(K)=-W !A
         LET A(-W)=0
         CALL try(K+1,N,P,A,B)
         LET A(-W)=1
      END IF

   END IF

END IF
END SUB



実行結果

1  2  3 -3 -1 -2

1  2  3 -3 -2 -1

1  2 -2 -1 -3  3

1  3  2 -2 -1 -3

1  3  2 -2 -3 -1

1  3 -3 -1 -2  2

1 -1 -2 -3  3  2

1 -1 -2  2  3 -3

1 -1 -3 -2  2  3

1 -1 -3  3  2 -2

10 通り
60 通り


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月26日(火)15時34分50秒
  > No.3702[元記事へ]

問題　2010年度灘中学
6桁の整数ABCDEFで、
一番上の位の数字Aを一番下に移した数BCDEFAがもとの数の3倍になるものは、ちょうど2つあります。
このような数ABCDEFのうち大きい方をXとすると、Xはいくらになるでしょうか？
また、X/999999をできる限り約分した分数はいくらでしょうか。


問題　覆面算
　 ABCDEF
×      3
----------
　 BCDEFA


答え 乗算の筆算による

A=1のとき
　　1BCDEF
　×     3
　---------
　　BCDEF1

　一の位は、3×7=21より、
　　1BCDE7
　×     3
　---------
　　BCDE71

　十の位は、一の位から桁上がりに注意して、3×5+2=17より、
　　1BCD57
　×     3
　---------
　　BCD571

　　：

A=2のとき
　　：


DIM P(6) !順にA,B,C,D,E,F
FOR A=1 TO 9
   LET P(1)=A

   LET T=P(1)
   FOR M=6 TO 2 STEP -1 !一の位から順にうめていく
      FOR i=1 TO 9 !九九の3の段
         IF MOD(3*i,10)=T THEN EXIT FOR
      NEXT i
      IF i>9 THEN
         PRINT "解なし"
         STOP
      ELSE
         LET P(M)=i
         LET CY=INT(3*i/10)
         LET T=i-CY
      END IF
   NEXT M
   IF CY=P(1) THEN MAT PRINT P; !すべてうまったなら

NEXT A
END


実行結果

1  4  2  8  5  7

2  8  5  7  1  4




答え　不定方程式
3(100000A+10000B+1000C+100D+10E+F)=100000B+10000C+1000D+100E+10F+A
∴70000B+7000C+700D+70E+7F=299999A
∴10000B+1000C+100D+10E+F=42857A
左辺＜100000だから、A=1,2
大きい方は、A=2なので、X=285714

また、285714/999999=(2×142857)/(7×142857)=2/7
（終り）


答え　循環小数
　ABCDEF0
-  BCDEFA
----------
　A000000-A=(10^6-1)×A=999999×A
また、ABCDEF0-BCDEFA=10×ABCDEF-3×ABCDEF=7×ABCDEF
これより、999999×A=7×ABCDEF　∴A/7=ABCDEF/999999
右辺は循環節がABCDEFの循環小数を分数で表したものである。
左辺は、分母が7の真分数を考えると、
　1/7=0.{142857}
　2/7=0.{285714}
　3/7=0.{428571}
　4/7=0.{571428}
　5/7=0.{714285}
　6/7=0.{857142}
から、3倍しても6桁のものは、分子が1,2のときとなる。
よって、大きい方Xは285714、X/999999は2/7となる。
（終り）


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月27日(水)10時09分16秒
  > No.3703[元記事へ]

問題
5で割ると2余り、7で割ると4余り、11で割ると8余るような自然数nで最小のものを求めよ。

答え
題意より、n=5*Q1+R1=7*Q2+R2=11*Q3+R3
これより、5*Q1=11*Q3+R3-R1、7*Q2=11*Q3+R3-R2
これを満たす整数の組Q1,Q2,Q3を求める。
(終わり)


LET R1=2
LET R2=4
LET R3=8
FOR Q3=0 TO 5*7
   LET N=11*Q3+R3
   LET Q1=(N-R1)/5
   LET Q2=(N-R2)/7
   IF Q1=INT(Q1) AND Q2=INT(Q2) THEN PRINT N
NEXT Q3
END



答え
5で割ると2余るので、3を加えると、5の倍数となる。
7で割ると4余るので、3を加えると、7の倍数となる。
11で割ると8余るので、3を加えると、11の倍数となる。
よって、5×7×11-3=382
（終り）

 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月30日(土)10時21分54秒
  > No.3704[元記事へ]

問題
正多面体の各面に色を塗っていく。
隣接する面が同じ色にならないような塗り方は何通りありますか。
例
正4面体の場合、色数が1,2,3,4のとき、それぞれ0,0,0,1通り
正6面体の場合、色数が1,2,3,4,5,6のとき、それぞれ0,0,1,6,15,30通り

参考サイト　http://izumi-math.jp/thema/nuriwake.htm
参考サイト　http://www004.upp.so-net.ne.jp/s_honma/figure/color.htm



!正6面体
!・─・
!│１│
!・─・─・─・─・
!│２│３│４│５│
!・─・─・─・─・
!　　　　　　│６│
!　　　　　　・─・
DATA 6 !面数
DATA 0,1,1,1,1,0 !面1　隣接行列
DATA 1,0,1,0,1,1 !面2
DATA 1,1,0,1,0,1 !面3
DATA 1,0,1,0,1,1 !面4
DATA 1,1,0,1,0,1 !面5
DATA 0,1,1,1,1,0 !面6


READ N
DIM M(N,N)
MAT READ M

PUBLIC NUMERIC C !場合の数
LET C=0

DIM Q(N) !各色数の場合の数
MAT Q=ZER

DIM P(N) !パターン
LET P(1)=1 !面1を固定する

CALL try(2,P,Q, N,M,N)
MAT PRINT Q;

END


EXTERNAL SUB try(X,P(),Q(), K,M(,),N) !バックトラック法で探索する
FOR i=1 TO K !k色
   FOR J=1 TO X-1 !隣接面を確認する
      IF M(X,J)>0 THEN
         IF i=P(J) THEN EXIT FOR !同じ色なら
      END IF
   NEXT J
   IF J>X-1 THEN !異なる色なら
      LET P(X)=i

      IF X=N THEN !全面塗ったなら
         DIM F(N) !使用された色数（k色中t色）を確認する
         MAT F=ZER
         FOR J=1 TO N
            LET F(P(J))=1
         NEXT J
         LET T=0
         FOR J=1 TO N
            LET T=T+F(J)
         NEXT J
         FOR J=1 TO T
            IF F(J)=0 THEN EXIT FOR
         NEXT J
         IF J>T THEN !1～t色　※1,2,3の3色はOK、1,2,4や1,3,5などはNG

            CALL CF(N,P, OK)
            IF OK=-1 THEN !対称性を考慮する

               LET Q(T)=Q(T)+1 !記録する

               LET C=C+1
               PRINT"No.";C; T;"色" !パターンを表示する
               MAT PRINT P;

            END IF

         END IF
      ELSE
         CALL try(X+1,P,Q, K,M,N) !次の面へ
      END IF
   END IF
NEXT i
END SUB


EXTERNAL SUB CF(N,P(), OK) !6面体　バーンサイドの定理（コーシー・フロベニウスの定理）
!展開図を1つに固定する。　面1の部分が、面1から面nになるように展開する。

!正6面体
!・─・
!│１│
!・─・─・─・─・　　→　1,2,3,4,5,6と表す
!│２│３│４│５│
!・─・─・─・─・
!　　　　　　│６│
!　　　　　　・─・
DATA 24 !対称

DATA 1,2,3,4,5,6 !面1　0°回転
DATA 1,3,4,5,2,6 !    90°
DATA 1,4,5,2,3,6 !   180°
DATA 1,5,2,3,4,6 !   270°

DATA 2,1,5,6,3,4 !面2
DATA 2,5,6,3,1,4
DATA 2,6,3,1,5,4
DATA 2,3,1,5,6,4

DATA 3,4,1,2,6,5 !面3
DATA 3,1,2,6,4,5
DATA 3,2,6,4,1,5
DATA 3,6,4,1,2,5

DATA 4,6,5,1,3,2 !面4
DATA 4,5,1,3,6,2
DATA 4,1,3,6,5,2
DATA 4,3,6,5,1,2

DATA 5,4,6,2,1,3 !面5
DATA 5,6,2,1,4,3
DATA 5,2,1,4,6,3
DATA 5,1,4,6,2,3

DATA 6,5,4,3,2,1 !面6
DATA 6,4,3,2,5,1
DATA 6,3,2,5,4,1
DATA 6,2,5,4,3,1


LET OK=0

READ K

!数字の並びをn進法n桁で表す。
!元の値が最小なら（対称性を排除されるので）、採用する。

LET T=0
FOR i=1 TO N
   READ A
   LET T=T*N+(P(A)-1)
NEXT i

FOR J=1 TO K-1 !対称なもの
   LET W=0
   FOR i=1 TO N
      READ A
      LET W=W*N+(P(A)-1)
   NEXT i
   IF W<T THEN EXIT SUB
NEXT J

LET OK=-1
END SUB


実行結果

No. 1  3 色
1  2  3  2  3  1

No. 2  4 色
1  2  3  2  3  4

No. 3  4 色
1  2  3  2  4  1

No. 4  5 色
1  2  3  2  4  5

No. 5  5 色
1  2  3  2  5  4

No. 6  4 色
1  2  3  4  3  1

No. 7  5 色
1  2  3  4  3  5

No. 8  5 色
1  2  3  4  5  1

No. 9  6 色
1  2  3  4  5  6

No. 10  6 色
1  2  3  4  6  5

No. 11  5 色
1  2  3  5  3  4

No. 12  5 色
1  2  3  5  4  1

No. 13  6 色
1  2  3  5  4  6

No. 14  6 色
1  2  3  5  6  4

No. 15  6 色
1  2  3  6  4  5

No. 16  6 色
1  2  3  6  5  4

No. 17  4 色
1  2  4  2  4  3

No. 18  5 色
1  2  4  2  5  3

No. 19  4 色
1  2  4  3  4  1

No. 20  5 色
1  2  4  3  4  5

No. 21  5 色
1  2  4  3  5  1

No. 22  6 色
1  2  4  3  5  6

No. 23  6 色
1  2  4  3  6  5

No. 24  6 色
1  2  4  5  3  6

No. 25  5 色
1  2  4  5  4  3

No. 26  6 色
1  2  4  5  6  3

No. 27  6 色
1  2  4  6  3  5

No. 28  6 色
1  2  4  6  5  3

No. 29  6 色
1  2  5  3  4  6

No. 30  5 色
1  2  5  3  5  4

No. 31  6 色
1  2  5  3  6  4

No. 32  6 色
1  2  5  4  3  6

No. 33  5 色
1  2  5  4  5  3

No. 34  6 色
1  2  5  4  6  3

No. 35  6 色
1  2  5  6  3  4

No. 36  6 色
1  2  5  6  4  3

No. 37  6 色
1  2  6  3  4  5

No. 38  6 色
1  2  6  3  5  4

No. 39  6 色
1  2  6  4  3  5

No. 40  6 色
1  2  6  4  5  3

No. 41  6 色
1  2  6  5  3  4

No. 42  6 色
1  2  6  5  4  3

No. 43  4 色
1  3  4  3  4  2

No. 44  5 色
1  3  4  3  5  2

No. 45  5 色
1  3  4  5  4  2

No. 46  6 色
1  3  4  5  6  2

No. 47  6 色
1  3  4  6  5  2

No. 48  5 色
1  3  5  4  5  2

No. 49  6 色
1  3  5  4  6  2

No. 50  6 色
1  3  5  6  4  2

No. 51  6 色
1  3  6  4  5  2

No. 52  6 色
1  3  6  5  4  2

0  0  1  6  15  30



 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 5月30日(土)12時22分48秒
  > No.3705[元記事へ]

つづき

2箇所の赤色部分を置き換えます。


正4面体の場合、色数が1,2,3,4のとき、それぞれ0,0,0,1通り


1つ目

!正4面体
!　　　　・
!　　　／２＼
!　　・───・
!　／４＼１／３＼
!・───・───・
DATA 4 !面数
DATA 0,1,1,1 !面1　隣接行列
DATA 1,0,1,1 !面2
DATA 1,1,0,1 !面3
DATA 1,1,1,0 !面4



2つ目

!正4面体
!　　　　・
!　　　／２＼
!　　・───・　　　→　1,2,3,4と表す
!　／４＼１／３＼
!・───・───・
DATA 12 !対称

DATA 1,2,3,4 !面1　0°回転
DATA 1,3,4,2 !   120°
DATA 1,4,2,3 !   240°

DATA 2,1,4,3 !面2
DATA 2,4,3,1
DATA 2,3,1,4

DATA 3,4,1,2 !面3
DATA 3,1,2,4
DATA 3,2,4,1

DATA 4,3,2,1 !面4
DATA 4,2,1,3
DATA 4,1,3,2





正8面体の場合、色数が1,2,3,4,5,6,7,8のとき、それぞれ0,1,12,103,730,2400,3360,1680通り


1つ目

!正8面体
!　　　　・
!　　　／２＼
!　　・───・───・───・
!　／４＼１／３＼７／５＼８／
!・───・───・───・
!　　　　　　　　　＼６／
!　　　　　　　　　　・
DATA 8 !面数
DATA 0,1,1,1,0,0,0,0 !面1　隣接行列
DATA 1,0,0,0,0,0,1,1 !面2
DATA 1,0,0,0,0,1,1,0 !面3
DATA 1,0,0,0,0,1,0,1 !面4
DATA 0,0,0,0,0,1,1,1 !面5
DATA 0,0,1,1,1,0,0,0 !面6
DATA 0,1,1,0,1,0,0,0 !面7
DATA 0,1,0,1,1,0,0,0 !面8



2つ目

!正8面体
!　　　　・
!　　　／２＼
!　　・───・───・───・　　→　1,2,3,4,5,6,7,8と表す
!　／４＼１／３＼７／５＼８／
!・───・───・───・
!　　　　　　　　　＼６／
!　　　　　　　　　　・
DATA 24 !対称

DATA 1,2,3,4, 5,6,7,8 !面1　0°回転
DATA 1,3,4,2, 5,8,6,7 !   120°
DATA 1,4,2,3, 5,7,8,6 !   240°

DATA 2,1,8,7, 6,5,4,3 !面2
DATA 2,8,7,1, 6,3,5,4
DATA 2,7,1,8, 6,4,3,5

DATA 3,6,1,7, 8,2,4,5 !面3
DATA 3,1,7,6, 8,5,2,4
DATA 3,7,6,1, 8,4,5,2

DATA 4,6,8,1, 7,2,5,3 !面4
DATA 4,8,1,6, 7,3,2,5
DATA 4,1,6,8, 7,5,3,2

DATA 5,6,7,8, 1,2,3,4 !面5
DATA 5,7,8,6, 1,4,2,3
DATA 5,8,6,7, 1,3,4,2

DATA 6,5,4,3, 2,1,8,7 !面6
DATA 6,4,3,5, 2,7,1,8
DATA 6,3,5,4, 2,8,7,1

DATA 7,2,5,3, 4,6,8,1 !面7
DATA 7,5,3,2, 4,1,6,8
DATA 7,3,2,5, 4,8,1,6

DATA 8,2,4,5, 3,6,1,7 !面8
DATA 8,4,5,2, 3,7,6,1
DATA 8,5,2,4, 3,1,7,6


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 6月 8日(月)10時40分46秒
  > No.3706[元記事へ]

少年ガウスは、
　1+2+3+4+ … +100
を
　(1+100)×100÷2
として求めた。
これに習って、次の問題を解いてみよう。


問題
1から1998までの整数のなかで、1998と互いに素の整数はいくつあるか。
また、その整数すべて和はいくつか。

答え
　0　1998
　1　1997
　2　1996
　3　1995
　4　1994
　5　1993
　6　1992
　7　1991
　8　1990
　　：
　　：
　1997　1
　1998　0
と組み合わせて、
1998=2×3^3×37なので、2,3,37の倍数で篩い法を適用する。
　　1　1997
　　5　1993
　　7　1991
　　　：
　　1997　1
　の648通り
より、
1998×648=647352
（終り）


OPTION ARITHMETIC RATIONAL

LET F=1998*(1-1/2)*(1-1/3)*(1-1/37) !1998=2×3^3×37より、オイラー関数φ(1998)
PRINT F
PRINT 1998*F/2


!シミュレーション
LET S=0 !場合の数
LET T=0 !和
FOR K=1 TO 1998
   IF GCD(1998,K)=1 THEN !互いに素
      LET S=S+1
      LET T=T+K
      !!!PRINT K !debug
   END IF
NEXT K
PRINT S;"通り"
PRINT "和=";T

END



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

問題
100円硬貨が4枚、10円硬貨が5枚、1円硬貨が6枚ある。
支払える金額が何通りあるか。　また、その合計はいくらか。

答え
7×6×5=210通り、たたし、いずれの硬貨1枚も使わない0円を含む。
その和は、
未使用の硬貨　　　　　　　使用した硬貨（支払える金額）
100円　10円　1円　　　　　100円　10円　1円
　4枚   5枚  6枚=456円      0枚   0枚  0枚=0円
　4枚   5枚  5枚=455円      0枚   0枚  1枚=1円
　4枚   5枚  4枚=454円      0枚   0枚  2枚=2円
　4枚   5枚  3枚=453円      0枚   0枚  3枚=3円
　4枚   5枚  2枚=452円      0枚   0枚  4枚=4円
　4枚   5枚  1枚=451円      0枚   0枚  5枚=5円
　4枚   5枚  0枚=450円      0枚   0枚  6枚=6円
　4枚   4枚  6枚=446円      0枚   1枚  0枚=10円
　4枚   4枚  5枚=445円      0枚   1枚  1枚=11円
　4枚   4枚  4枚=444円      0枚   1枚  1枚=12円
　　　：
　　　：
　0枚   0枚  1枚=1円      4枚   5枚  5枚=455円
　0枚   0枚  0枚=0円      4枚   5枚  6枚=456円
と組み合わせて、456×210÷2=47880円
（終り）


!シミュレーション
LET S=0 !場合の数
LET T=0 !和
FOR A=0 TO 4
   FOR B=0 TO 5
      FOR C=0 TO 6
         LET W=100*A+10*B+C
         PRINT W
         LET S=S+1
         LET T=T+W
      NEXT C
   NEXT B
NEXT A
PRINT S;"通り"
PRINT "和=";T
END



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

問題
数字1,2,3,4,5,6のうち異なる3つの数字を使って、3桁の整数をつくる。
3の倍数はいくつできるか。　また、それらの和はいくつか。

答え
3つの数の組は、
(1,2,3)、(1,2,6)、(1,3,5)、(1,5,6)、(2,3,4)、(2,4,6)、(3,4,5)、(4,5,6)
それぞれ3!通りに並べて、8×3!=48通り。
その和は、
123+654=777
126+651=777
135+642=777
234+543=777
と組み合わせて、777×(8×3!)÷2=18648
（終り）


!シミュレーション
LET S=0 !場合の数
LET T=0 !和
FOR A=1 TO 6 !異なる3つの数A,B,C
   FOR B=1 TO 6
      IF A-B<>0 THEN
         FOR C=1 TO 6
            IF (C-A)*(C-B)<>0 THEN
               LET W=100*A+10*B+C
               IF MOD(W,3)=0 THEN !3の倍数
                  LET S=S+1
                  PRINT W
                  LET T=T+W
               END IF
            END IF
         NEXT C
      END IF
   NEXT B
NEXT A
PRINT S;"通り"
PRINT "和=";T
END



 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 6月10日(水)19時53分23秒
  > No.3742[元記事へ]

問題
さいころを3回振って、順に百,十,一の位の数として3桁の整数をつくる。
このとき、位の数がすべて異なる3桁の整数を足し合わせるといくつになるか。

答え
すべて数が異なる3桁の整数の組は、COMB(6,3)=20通り
具体的に、
　(1,2,3)
　(1,2,4)
　(1,2,5)
　(1,2,6)
　(1,3,4)
　(1,3,5)
　(1,3,6)
　(1,4,5)
　(1,4,6)
　(1,5,6)
　(2,3,4)
　(2,3,5)
　(2,3,6)
　(2,4,5)
　(2,4,6)
　(2,5,6)
　(3,4,5)
　(3,4,6)
　(3,5,6)
　(4,5,6)
である。
次に、この20組それぞれに、3!=6通りの並べ方がある。
具体的に、(1,2,3)の場合、
　123,132,213,231,312,321
である。
このとき、数字1,2,3は各桁に3!÷3=2個ずつ現れる。
これより、和は(1+2+3)×(100+10+1)×2
同様に、(1,2,4)、(1,2,5)、…、(4,5,6)を計算すればよいが、
20組のなかでは、数字1,2,3,4,5,6は10個ずつ現れるので、
(1+2+3+4+5+6)*10*(100+10+1)*2=46620
（終り）



!シミュレーション
LET S=0
FOR A=1 TO 6 !順列P(6,3)
   FOR B=1 TO 6
      IF B-A<>0 THEN
         FOR C=1 TO 6
            IF (C-A)*(C-B)<>0 THEN
               LET S=S+(100*A+10*B+C)
            END IF
         NEXT C
      END IF
   NEXT B
NEXT A
PRINT S


!組み合わせ
LET S=0
FOR A=1 TO 6-2 !組(a,b,c)
   FOR B=A+1 TO 6-1
      FOR C=B+1 TO 6
         LET S=S+(A+B+C)*(100+10+1)*2
      NEXT C
   NEXT B
NEXT A
PRINT S

PRINT (1+2+3+4+5+6)*10*(100+10+1)*2


!出現する確率は均等
PRINT PERM(6,3)*(100+10+1)*(1+2+3+4+5+6)/6

END



 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 6月14日(日)10時09分6秒
  > No.3746[元記事へ]

問題　1991年　日本数学オリンピック
Aを16桁の正整数とする。
Aから連続する何桁かの数字をうまく取り出すと、
それらの数字の積を平方数（0も含む）に出来ることを証明せよ。


答え
バックトラック法で全検索してみよう。

OPTION ARITHMETIC RATIONAL
DIM A(16)
CALL try(1,A)
END
EXTERNAL SUB try(P,A())
OPTION ARITHMETIC RATIONAL
FOR i=2 TO 8 !0,1,4,9を除く
   IF i<>4 THEN
      LET A(P)=i !p番目を数字iとする
      LET S=1
      FOR K=P TO 1 STEP -1 !連続するk桁
         LET S=S*A(K)
         IF INTSQR(S)^2=S THEN EXIT FOR
      NEXT K
      IF K<1 THEN
         IF P>=15 THEN !15桁以上なら
            PRINT P
            MAT PRINT A;
         ELSE
            CALL try(P+1,A) !次へ
         END IF
      END IF
   END IF
NEXT i
END SUB


実行結果
15
2  3  2  5  2  3  2  7  2  3  2  5  2  3  2  0

15
2  3  2  5  2  3  2  7  2  3  2  5  2  3  8  0

15
2  3  2  5  2  3  2  7  2  3  2  5  2  6  2  0

15
2  3  2  5  2  3  2  7  2  3  2  5  2  6  8  0

15
2  3  2  5  2  3  2  7  2  3  2  5  3  2  3  0

15
2  3  2  5  2  3  2  7  2  3  2  5  3  6  3  0

15
2  3  2  5  2  3  2  7  2  3  2  5  3  8  3  0

   :
   :


 		 
 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 6月20日(土)09時37分49秒
  > No.3759[元記事へ]

問題
正の整数a,b,c,nとする。
1辺がa,b,c、体積がn=abcの直方体を考える。
1≦n≦mとなるnに対して、a,b,cがすべて2以上となるnはいくつあるか。
例
m=20の場合、8=2×2×2、12=2×2×3、16=2×2×4、18=2×3×3、20=2×2×5 の5つとなる。

答え
n=(p^a)(q^b)(r^c)…と因数分解する。a+b+c+ … ≧3となるnが題意を満たす。
（終り）


LET M=20 !500000
DIM P(M) !mの最大の素因数
MAT P=ZER
LET P(1)=1 !1は素数でない
FOR N=1 TO M
   IF P(N)=0 THEN !素数なら
      FOR K=N TO M STEP N !倍数を篩う
         LET P(K)=N
      NEXT K
   END IF
NEXT N
!!!MAT PRINT P; !debug
LET C=0
FOR N=1 TO M
   LET X=0 !個数
   LET T=N !素因数分解する
   DO WHILE T>1 !リンクをたどる
      LET T=T/P(T)
      LET X=X+1
   LOOP
   IF X>=3 THEN LET C=C+1
NEXT N
PRINT C
END


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 6月23日(火)19時13分6秒
  > No.3763[元記事へ]

問題
m＜nとなる自然数m,nがある。
√(3mn)が整数となる(m,n)の組のうち、
m+nの値を小さい順に並べたとき、4番目になる組を求めよ。

考察
mn=3×(自然数)^2より、mn=3,12,27,48,…
3のとき、1×3（和は4）
12のとき、3×4（7）、2×6（8）、1×12（13）
27のとき、3×9（12）、1×27（28）
48のとき、6×8（14）、4×12（16）、3×16（19）、2×24（26）、1×48（49）
　：
（終り）

答え
m+n=kとおく。m＜nとなる自然数なので、
最小値は1+2=3より、k=3,4,5,6,…
m+n＞2mより、1≦m＜k/2となる。このとき、n=k-m
（終り）


FOR K=3 TO 20
   FOR M=1 TO K/2
   !!!PRINT K;M !debug
      LET S=3*M*(K-M)
      IF INT(SQR(S))^2=S THEN PRINT M;K-M; K
   NEXT M
NEXT K
END


実行結果

1  3  4
3  4  7
2  6  8
3  9  12
1  12  13
6  8  14
4  12  16
3  16  19
5  15  20




その２　和と差、2次方程式の解
m+n=k（式1）とおく。
mn=3×(自然数)^2より、mn=3p^2とおく。
(m-n)^2=(m+n)^2-4mn=k^2-12p^2　∴m-n=√(k^2-12p^2)（式2）
平方根のなかは正なので、1≦p≦√(k^2/12)
式2が整数になることに注意して、式1と式2を連立させる。


FOR K=3 TO 20
   FOR P=1 TO SQR(K^2/12)
   !!!PRINT K;P !debug
      LET R=SQR(K^2-12*P^2)
      IF INT(R)=R THEN !整数なら
         LET M=(K-R)/2 !m＜n
         LET S=3*M*(K-M)
         IF INT(SQR(S))^2=S THEN PRINT M;K-M; K
      END IF
   NEXT P
NEXT K
END


 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 6月24日(水)12時26分43秒
  > No.3767[元記事へ]

問題
3人で50m走をしました。
同着を含めて、何通りの順位付けがありますか。



答え
3人をA,B,Cとする。
全員が1位になる場合、ABCと表すことにする。　1通り
Aが1位、B,Cが2位の場合、A｜BC
このパターンの場合の数は、A,B,Cの並べ方を考慮すればよい。3!/(1!2!)=3通り
A,Bが1位、Cが3位の場合、AB｜C　　A,B,Cの並べ方を考慮して、3!/(2!1!)=3通り
Aが1位、Bが2位、Cが3位の場合、A｜B｜C　　A,B,Cの並べ方を考慮して、3!=6通り
よって、1+3+3+6=13通り
（終り）

答え
分割数を考える。3=2+1=1+2=1+1+1
3の場合、3!/3!=1
2+1の場合、3!/(2!1!)=3
1+2の場合、3!/(1!2!)=3
1+1+1の場合、3!/(1!1!1!)=6
よって、1+3+3+6=13通り
（終り）


OPTION ARITHMETIC RATIONAL
LET N=3
PUBLIC NUMERIC C !場合の数
LET C=0
DIM A(N) !分割パターン　3=2+1=1+2=1+1+1
CALL try(1,A,N)
PRINT C;"通り"
END
EXTERNAL SUB try(P,A(),N) !バックトラック法
OPTION ARITHMETIC RATIONAL
FOR K=N TO 1 STEP -1
   LET A(P)=K !p番目をkとする
   IF N-K=0 THEN !終わったなら
      MAT PRINT A; !debug
      LET T=0 !分子
      FOR J=1 TO P
         LET T=T+A(J)
      NEXT J
      LET S=FACT(T)
      FOR J=1 TO P !分母
         LET S=S/FACT(A(J))
      NEXT J
      PRINT S !debug
      LET C=C+S
   ELSE
      CALL try(P+1,A,N-K) !次へ
   END IF
   LET A(P)=0
NEXT K
END SUB


実行結果

3  0  0

1
2  1  0

3
1  2  0

3
1  1  1

6
13 通り



答え　漸化式
1人のとき、1通り
2人のとき、
　2人をA,Bとする。
　Aが1位、Bが2位
　Bが1位、Aが2位
　A,B共に1位
これを、
　1人が1位になるのは、C(2,1)=2通り　このとき、残り1人の順位付けは前出の1通り
　2人が1位になるのは、C(2,2)=1通り
　よって、2×1+1=3通り
と考える。
3人のとき、
1人が1位になるのは、C(3,1)=3通り　このとき、残り2人の順位付けは前出の3通り
2人が1位になるのは、C(3,2)=3通り　このとき、残り1人の順位付けは前出の1通り
3人が1位になるのは、C(3,3)=1通り
よって、3×3+3×1+1=13通り
一般に、P[n]=C(n,1)P[n-1]+C(n,2)P[n-2]++C(n,3)P[n-3]+ … +C(n,n)P[0]、P[0]=1
（終り）


OPTION ARITHMETIC RATIONAL
LET N=3
PRINT P(N);"通り"
END
EXTERNAL FUNCTION P(N) !漸化式
OPTION ARITHMETIC RATIONAL
IF N=0 THEN
   LET P=1
ELSE
   LET S=0
   FOR K=1 TO N
      LET S=S+COMB(N,K)*P(N-K)
   NEXT K
   LET P=S
END IF
END FUNCTION


または

OPTION ARITHMETIC RATIONAL
LET N=3
DIM F(0 TO N) !漸化式
LET F(0)=1
FOR K=1 TO N
   LET S=0 !F[k]を求める
   FOR J=1 TO K
      LET S=S+COMB(K,J)*F(K-J)
   NEXT J
   LET F(K)=S
NEXT K
PRINT F(N);"通り"
END



 		 

Re: 組み合わせを考える

 投稿者：山中和義  投稿日：2015年 6月25日(木)10時34分25秒
  > No.3768[元記事へ]

問題　多項定理
(a+b+c)^4を展開したとき、a^2bcの項はいくつありますか。

答え
a,a,b,cの並べ方から、4!/(2!1!1!)=12通り
（終り）

4!/(2!1!1!)の計算方法
4!/(2!1!1!)
=(4×3×2×1)/{(2×1)(1)(1)}
={(2×1)/(1×2)}{3/1}{4/1}
=C(0+2,2)×C(2+1,1)×C(3+1,1)
と変形して、オーバーフローを避ける。

C(n,k)の計算方法
{n/1}×{(n-1)/2}×{(n-2)/3}× … ×{(n-k+1)/k}
とする。



PRINT FACT(4)/(FACT(2)*FACT(1)*FACT(1)) !式通りに計算する

DATA 3 !m種類
DATA 2,1,1 !p,q,…,r個
READ M
DIM A(M)
MAT READ A
LET T=A(1) !C(p,p)
LET S=1
FOR K=2 TO M !C(p+q,q)、…、C(p+q+ … +r, r)
   LET T=T+A(K)
   LET S=S*COMB(T,A(K))
NEXT K
PRINT S

END

 		 

戻る