アットランダム≒ブリコラージュ

9909：嘘つき…パズル ^^

問題9909・・・http://jukensansu.cocolog-nifty.com/planet/#_ga=1.140909490.1098583858.1333881279 より 引用 Orz〜

あるクラブにＡ君〜Ｋ君の11人のメンバーがいます。この人たちはいつも本当のことを言う人と、いつもうそを言う人の２つのグループに分かれます。
ある日、先生が『11人のメンバーの中に、いつもうそを言う人は何人いますか？』とたずねました。その日、Ｊ君とＫ君は休んでいました。残りの９人のメンバーは、それぞれ次のようにこたえました。

Ａ君 「10人います」
Ｂ君 「７人います」　
Ｃ君 「11人います」　　　
Ｄ君 「３人います」　　　
Ｅ君 「６人います」　　
Ｆ君 「10人います」
G君 「５人います」
Ｈ君 「６人います」
I 君 「４人います」

さて、このクラブの11人のメンバーの中には、いつもうそを言う人は何人いますか？

（第５回算数オリンピック、トライアル問題より）

解答

・わたしの…

10人という答が2つだと本当のことを言う人は一人になり矛盾…so...少なくとも嘘つきはA,Fの2人

11人と言うCは明らかに嘘つき...これで少なくとも3人

3人だけが嘘つきなら、D以外は嘘つきになるので、Dは嘘つき...これで少なくとも4人

4人だけが嘘つきだとI以外は嘘つきになるので、Iは嘘つき、これで少なくとも5人

以下同様に、6人、7人と言うものはみな嘘つき。

so...この中の９人全員嘘つきね ^^

9908：隣り合う数の差が1の12桁の数...

問題9908・・・やどかりさんのブログ http://blogs.yahoo.co.jp/oka_yadokary/36201353.html ;

より Orz〜

　432123234567 のように、数字の 0 を含まず、隣り合う数字の差が１である 12桁の数の個数は？

解答

上記サイト http://blogs.yahoo.co.jp/oka_yadokary/36217716.html より Orz〜

[解答1]

　隣り合う数字の差が１であるｎ桁の数で末位がｋのものの個数を a(n，k) とし、

　a(n，0)＝a(n，10)＝0 と定義すれば、a(n＋1，k)＝a(n，k−1)＋a(n，k＋1) なので、

　単純に 表を作れば 上記のようになり 9400個です。

　もちろん、a(n，k)＝a(n，10−k) を利用すれば、もう少し能率よくなります。


[解答2]

　首位が偶数で末位が奇数のものと、首位が奇数で末位が偶数のものとがありますが、

　逆に並べることにより１対１に対応しますので、首位が偶数で末位が奇数のものだけを考え、

　２倍すると求める個数が得られます。

　条件に合う 奇数桁で首位が偶数のものは末位も偶数ですが、

　ｎを自然数として、首位が偶数で(2n−1)桁のものの個数を求めます。

　4321232 と 6789878 のように、各位の数字の和が 10 になるように対応させることにより、

　末位が 2 のものと 末位が 8 のものは同数で、末位が 4 のものと 末位が 6 のものは同数です。

　末位が 2，4，6，8 のものの個数をそれぞれ 、a_n，b_n，b_n，a_n とします。

　末位が 2 のものの下３桁は、212，232，432 だから、a_n+1＝2a_n＋b_n ……(1) 、

　末位が 4 のものの下３桁は、234，434，454，654 だから、b_n+1＝a_n＋3b_n ……(2) です。

　(1)より b_n＝a_n+1−2a_n となり、(2)に代入して、a_n+2−2a_n+1＝a_n＋3(a_n+1−2a_n) 、a_n+2＝5a_n+1−5a_n 、

　(2)より a_n＝b_n+1−3b_n となり、(1)に代入して、b_n+2−3b_n+1＝2(b_n+1−3b_n)＋b_n 、b_n+2＝5b_n+1−5b_n 、

　ここで、a_n＋b_n＝c_n とおけば、首位が偶数で(2n−1)桁のものの個数は 2c_n で、c_n+2＝5c_n+1−5c_n です。

　また、(a₁，b₁)＝(1，1) より (a₂，b₂)＝(3，4) 、c₁＝a₁＋b₁＝2 ，c₂＝a₂＋b₂＝7 です。

　よって、c₃＝5c₂−5c₁＝25 ，c₄＝5c₃−5c₂＝90 ，c₅＝5c₄−5c₃＝325 ，c₆＝5c₅−5c₄＝1175 です。

　条件に合う12桁の数は、首位も末位も偶数の11桁の 2c₆ 個に対し、

　首位の前に１違いの奇数を付加するか、末位の後に１違いの奇数を付加すると得られるので、

　4･2c₆＝8c₆＝8･1175＝9400 個です。


[参考]

　c₁＝2 ，c₂＝7 ，c_n+2＝5c_n+1−5c_n を解きます。

　a＝(5＋√5)/2 ，b＝(5−√5)/2 とおけば、a＋b＝5 ，ab＝5 ，a−b＝√5 ，

　a³＝25＋10√5＝(5√5)(√5＋2)＝(5√5)(7−2b)＝(5√5)(c₂−bc₁) ，

　b³＝25−10√5＝−(5√5)(−√5＋2)＝−(5√5)(7−2a)＝−(5√5)(c₂−ac₁) になります。

　c_n+2＝(a＋b)c_n+1−abc_n より

　c_n+2−bc_n+1＝a(c_n+1−bc_n) 、c_n+1−bc_n＝a^n-1(c₂−bc₁)＝aⁿ⁺²/(5√5) 、

　c_n+2−ac_n+1＝b(c_n+1−ac_n) 、c_n+1−ac_n＝b^n-1(c₂−ac₁)＝−bⁿ⁺²/(5√5) 、

　差をとって、(a−b)c_n＝(aⁿ⁺²＋bⁿ⁺²)/(5√5) 、(√5)c_n＝(aⁿ⁺²＋bⁿ⁺²)/(5√5) 、c_n＝(aⁿ⁺²＋bⁿ⁺²)/25 です。

　結局、a＝(5＋√5)/2 ，b＝(5−√5)/2 ，c_n＝(aⁿ⁺²＋bⁿ⁺²)/25 として、

　(2n)桁のものは 8c_n 個 ，(2n＋1)桁のものは　2c_n+1＋8c_n 個です。

*[解答2]は上手い発想に思えるけど...わたしには難しすぎて…^^;

とにかく腰を落ち着けて諦めずに地道に数え上げましたわ ^^;;v

f(1,6)=f(9,6)=10
f(2,6)=f(8,6)=20
f(3,6)=f(7,6)=25
f(4,6)=f(6,6)=30
f(5,6)=30

f(1,6)=2*5+4*4+6*1
f(1,7)=5(f(1,6)+f(3,6))+4(f(3,6)+f(5,6))+f(5,6)+f(7,6)
=5(10+25)+4(25+30)+30+25=450

f(2,6)= 1*5+3*9+5*5+7*1=1*5+3*10+5*5
f(2,7)=5(f(2,6))+10(f(2,6)+f(4,6))+5(f(4,6)+f(6,6))
=5(20)+10(20+30)+5(2*30)=900

f(3,6)=2*9+4*10+6*5+8*1=2*10+4*15
f(3,7)=10(f(1,6)+f(3,6))+15(f(3,6)+f(5,6))
=10(10+25)+15(25+30)=1175

f(4,6)=1*4+3*10+5*10+7*5+9*1=1*5+3*15+5*10
f(4,7)=5*f(2,6)+15(f(2,6)+f(4,6))+10(f(4,6)+f(6,6)) 
=5*20+15(20+30)+10(2*30)=1450

f(5,6)= 2*5+4*10+6*10+8*5=2*10+4*20
f(5,7)=10(f(1,6)+f(3,6))+20(f(3,6)+f(5,6))
=10(10+25)+20(25+30)=1450

so…
2(450+900+1175+1450)+1450=9400