|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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 円
|
|
|
|
投稿者：山中和義
投稿日：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 通り
|
|
|
|
投稿者：山中和義
投稿日：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となる。
（終り）
|
|
|
|
投稿者：山中和義
投稿日：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
（終り）
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
:
:
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
|
投稿者：山中和義
投稿日：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
|
|
|
戻る