前週（第４４１回）分の過去ログ

吉川　マサル

またまた会社で更新になってしまいました。終電が迫っているので正解者が出る前に開けてしまいます...。ミスってなければ良いのですが...。というわけで、帰宅は１時少し前になる予定です。m(__)m

MacOS X　　 3月10日（木） 0:05:38　　 MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ　　24653

はなう

おおっ
久々にリアルタイム参加したら１位だ☆

小学生風にやってみます
正六角形の各頂点に１～６の番号をふる
この６点を線で結ぶ

結び方
１．全部の頂点を一筆書き（５！／２＝６０通り）
２．別々の三角形を２個作るように結ぶ（５Ｃ２／２＝１０通り←追記：ミスタイプしてました。５Ｃ２＝１０通りですね）

とーきょ　　 3月10日（木） 23:59:44　　 HomePage:http://hanau.daa.jp/blog2/　　24654

ミキティ

頑張ってリアルタイム参加しましたが、惜しくも２位。
つーか、こんなプログラム書いていちゃダメかな（ぉ

100 p=0
110 for a65=0 to 1
120 for a64=0 to 1
130 for a63=0 to 1
140 for a62=0 to 1
150 for a61=0 to 1
160 for a54=0 to 1
170 for a53=0 to 1
180 for a52=0 to 1
190 for a51=0 to 1
200 for a43=0 to 1
210 for a42=0 to 1
220 for a41=0 to 1
230 for a32=0 to 1
240 for a31=0 to 1
250 for a21=0 to 1
310 b1=0
320 b2=0
330 b3=0
340 b4=0
350 b5=0
360 b6=0
410 if a65=1 then b6=b6+1
420 if a65=1 then b5=b5+1
430 if a64=1 then b6=b6+1
440 if a64=1 then b4=b4+1
450 if a63=1 then b6=b6+1
460 if a63=1 then b3=b3+1
470 if a62=1 then b6=b6+1
480 if a62=1 then b2=b2+1
490 if a61=1 then b6=b6+1
500 if a61=1 then b1=b1+1
510 if a54=1 then b5=b5+1
520 if a54=1 then b4=b4+1
530 if a53=1 then b5=b5+1
540 if a53=1 then b3=b3+1
550 if a52=1 then b5=b5+1
560 if a52=1 then b2=b2+1
570 if a51=1 then b5=b5+1
580 if a51=1 then b1=b1+1
590 if a43=1 then b4=b4+1
600 if a43=1 then b3=b3+1
610 if a42=1 then b4=b4+1
620 if a42=1 then b2=b2+1
630 if a41=1 then b4=b4+1
640 if a41=1 then b1=b1+1
650 if a32=1 then b3=b3+1
660 if a32=1 then b2=b2+1
670 if a31=1 then b3=b3+1
680 if a31=1 then b1=b1+1
690 if a21=1 then b2=b2+1
700 if a21=1 then b1=b1+1
800 if (b1-2)^2+(b2-2)^2+(b3-2)^2+(b4-2)^2+(b5-2)^2+(b6-2)^2=0 then p=p+1
810 next a21
820 next a31
830 next a32
840 next a41
850 next a42
860 next a43
870 next a51
880 next a52
890 next a53
900 next a54
910 next a61
920 next a62
930 next a63
940 next a64
950 next a65
960 print p
970 end

　　 3月10日（木） 0:13:21　　 HomePage:みきこむ　　24655

エルク

ふぅ・・・
ちょっとした勘違いで少し遅れたけど
これだけ上位に入ったの初めてな気がする。

６１と６２を使うと仮定した上で
（５１・５２）と（５３・５４）から一つづつ選ぶと残りが決まり
これで４通り。
（５３と５４）を選ぶと残りの選び方が３通り。
計７通りに対し、６０台の選び方１０通りで７０通り。

魔法の国　　 3月10日（木） 0:15:22　　 HomePage:迷いの森　　24656

Taro

前回は底面を1：4：1の三角錐２つと四角錐という汚い分け方にしたので
大苦戦、計算ミスを連発の末なんとか正解にたどりつけました。

今回は結局プログラム・・・疲れました。

じたく・・・帰宅直後　　 3月10日（木） 0:21:39　　　　24657

みかん

まず、入っているカードは以下の１５枚。
１６・１５・１４・１３・１２
２６・２５・２４・２３
３６・３５・３４
４６・４５
５６

６がつくのは１０通りの選び方があるが、とりあえず
１６と２６を選ぶことにする。
ここから５のつくカードの選び方で場合わけ。
（い）１５と２５を選ぶ→そのあとが行き詰るので不可。
（ろ）１５と３５／１５と４５／２５と３５／２５と４５のいずれかを選ぶ
　　　→それぞれに対して条件に合致するのが１通り。
（は）３５と４５を選ぶ→そのあと１４・２４・３４のどれを選んだ
　　　場合でも条件に合致するのが１通り。

結局１０×４＋１０×１×３＝７０通りが答えとなる。

算数好きの溜まり場　　 3月10日（木） 0:30:47　　　　24658

tomh

コツコツと数え上げました。
合ってて良かったぁ。 (^。^;)ホッ

新潟市　　 3月10日（木） 0:25:21　　 MAIL:tomh@yahoo.co.jp HomePage:H to M　　24659

あ～く＠初心

対戦表なものを作って（みかんさんのようなの）、とことん場合分けして数え上げました。
ここに書くには見にく過ぎる（醜すぎる）ので割愛・・・・・・

それにしても、はなうさんの解答#24654めっちゃシンプル・・・これぞ算数力！みたいな。

未完成の蜜柑星　　 3月10日（木） 0:28:20　　 MAIL:ishizaki@qa.so-net.ne.jp 　　24660

圭太

Total Access = 3620000　って、黄色くでかく表示されて驚いた＾＾；

米所～♪　　 3月10日（木） 0:30:55　　 HomePage:圭太の研究所＠いれこみくん！＆役満縛り～♪　　24661

schrodin

はなうさん凄すぎ…。

　　 3月10日（木） 0:31:33　　　　24662

圭太

#24558
21
31、32
41、42、43
51、52、53、54
61、62、63、64、65
の１５通りですね。。。。

米所～♪　　 3月10日（木） 0:33:25　　 HomePage:圭太の研究所＠いれこみくん！＆役満縛り～♪　　24663

みかん

#24663（圭太さん）
あ、しまった（汗）。長々と解法書いててこういうミスは恥ずかしい…
問題を解くには影響ないけど。

算数好きの溜まり場　　 3月10日（木） 0:38:51　　　　24664

始受験勉強君

#24654
全く同じ考えです！！！でも僕はこれを思いつくのに1時間もかかってしまいまし
た。さすがですね！！！僕も久しぶりのリアルタイム参加だったので、ちょっぴり
残念です。それと、問題が解けたときに感動しました。よくできた問題ですね！！
ではさようなら。

　　 3月10日（木） 1:13:05　　　　24665

アヒーのおじさん

みかん様とほぼ同じです（＾＾；
最初場合分けを間違えて400通りぐらいのどでかい数字になってしまったなんて内緒です（苦笑
はなう様の解法に感動中だったりします（ぉ

アンドロメダ大星雲　　 3月10日（木） 1:26:39　　 HomePage:正体不明　　24666

Taku-chan

10分で解けるんだ・・・。すごい・・・。
俺は30分くらいかな・・・。
考え方は・・・。
・１の位、１０の位のどちらかに１が含まれるカードは１枚
・１の位、１０の位のどちらかに２が含まれるカードは１枚
・１の位、１０の位のどちらかに３が含まれるカードは１枚
・１の位、１０の位のどちらかに４が含まれるカードは１枚
・１の位、１０の位のどちらかに５が含まれるカードは１枚
・１の位、１０の位のどちらかに６が含まれるカードは１枚
と考えると、
十の位６の選び方が5通り×十の位５（65を選んだときは十の位４）の選び方が3通り×残りで条件に合うのが1通り＝15通り
になりますね。
これを２組作ればいいけど、同じのを含んでるのは使えないから、
15×8÷2＝60　通り。
次に、21　31　32　と　54　64　65　のように、
6つの数字の中から3つの数字で、3つの組み合わせ　を2つで出来ているのが
５Ｐ２＝10　通り。
足して70通り・・・。説明できてない？？

　　 3月10日（木） 1:30:54　　　　24667

はなう

#24666　アヒーのおじさん　さん
#24665　始　受験勉強君　さん
#24662　schrodin さん
#24660　あ～く　さん

(σ￣ー￣)σありがとうございます～☆いつも鮮やかな解法を目指して解いていますが、毎回こんなふうにズバッといけばいいんですけどね。。。算数の道は険しいです(´ヘ｀；)

とーきょ　　 3月10日（木） 1:58:36　　 HomePage:http://hanau.daa.jp/blog2/　　24668

なか

１～６を６角形の頂点に、カードを六角形の辺と対角線に対応させました。
どの数字も２度なので、ループ状の一筆書きを求められていることになります。
はなうさん、ほかのみなさまと同じです。

北海道　　 3月10日（木） 7:46:45　　 MAIL:naka@sansu.org HomePage:naka's Home Page　　24669

鉄道アニマル（マジで）小６

それにしてもはなう様すごすぎ！！！！
思いつけばもっと早かったのになぁ・・・
ちなみに解き方はエルク様と同じです。ぼくもみかん様と同じく、１２，１３，１４・・・って解いてました。

さとすぺ㈱の弟子です。（マジで）　　 3月10日（木） 7:55:31　　　　24670

な

６～７年前にTORAさんが出題した問題と本質的には同じみたい。

　　 3月10日（木） 9:05:56　　　　24671

kasama

おはようございます。よく考えずに、プログラムにやらせました(^_^;)。

import java.util.*;
public class Question441 {
　public static void main(String[] args) {
　　List numberList = Arrays.asList(new String[]{"12","13","14","15","16","23","24","25","26","34","35","36","45","46","56"});
　　int count = 0;
　　for (int n = 1; n <= numberList.size(); ++n) {
　　　List list = new Combination(numberList, n).getList();//Combinationは#19625参照
　　　for (Iterator iter = list.iterator(); iter.hasNext(); ) {
　　　　List eList = (List) iter.next();
　　　　int[] checkNumber = new int[]{0,0,0,0,0,0};
　　　　for (Iterator eIter = eList.iterator(); eIter.hasNext(); ) {
　　　　　String s = (String) eIter.next();
　　　　　for (int i = 0; i < checkNumber.length; ++i) {
　　　　　　char c = (char)('1' + i);
　　　　　　if ((s.charAt(0) == c && s.charAt(1) != c) ||
　　　　　　　(s.charAt(0) != c && s.charAt(1) == c)) ++checkNumber[i];
　　　　　}
　　　　}
　　　　boolean flag = true;
　　　　for (int i = 0; i < checkNumber.length; ++i) {
　　　　　if (checkNumber[i] != 2) {
　　　　　　flag = false;
　　　　　　break;
　　　　　}
　　　　}
　　　　if (flag) ++count;
　　　}
　　}
　　System.out.println(count);
　}
}

出先　　 3月10日（木） 10:00:20　　　　24672

DrK

昨日の夜は、順位表に出てこないなと思いながらいたのですが、ありました。
70が答えということで、この場合は、3つの数字で回るとおりと6つ全ての順列の総和ということになります。
1を基準に考えて、3つを選ぶ方法は、5つの数字から2つを選べばいいので、5C2=10
6つの数字の順列は、1を基準にして5!=120となるが、常に10の位が1の位より大きくなるので、反対向きの順列も同じものとみなし、2で割る。
120/2=60
10+60=70が答え

今は廃墟　　 3月10日（木） 12:17:43　　 MAIL:satoka@star.odn.ne.jp 　　24673

uchinyan

はい、こんにちは。今回は楽しい問題ですね ^^/
もう少し楽しみたいので、わざと掲示板を読まずに、別解を考えてみようと思っていますが、
現時点での私の解法です。幾つかの具体的な試行錯誤の後に気付きました。
書かれている数の各位の数字は 1, 2, 3, 4, 5, 6 ですが、1 以外を a, b, c, d, e と書くことにします。もちろん、a, b, c, d, e は異なります。
書かれている数は、与えられている条件から、二つの数字を与えると一意に定まります。そこで、これを (a,b) などと書くことにします。
例えば、(1,2) = 21, (6,4) = 64, (1,a) = a1, (d,b) は、d > b ならば db です。
さて、カードの選び方として、数字の表れ方に注目して、(1,a) -> (a,b) -> (b,c) -> ... のように順番に選ぶと考えても題意に矛盾しません。
すると、
１）(1,a) -> (a,1) の場合
これは同じカード a1 を一枚しか選んでいないので題意を満たしません。というか、意味がありません。
２）(1,a) -> (a,b) -> (b,1) の場合
三枚のカードが選ばれ、1, a, b が二回ずつ現れているので、残りの数字も (c,d) -> (d,e) -> (e,c) となれば題意を満たします。
この場合は、六つの数字を二つの組に分けて、二つずつ並べた場合、a が2通り b が一通り、ですが、
(1,a) -> (a,b) -> (b,1) と (1,b) -> (b,a) -> (a,1) は等価なので半分にします。
つまり、6C3/2 * 2!/2 * 2!/2 = 10 通り。
３）(1,a) -> (a,b) -> (b,c) -> (c,1) の場合
残りの数字が (d,e) -> (e,d) となることになりますが、これは１）の場合と同じでカードは一枚しか選ばれず、題意を満たしません。
４）(1,a) -> (a,b) -> (b,c) -> (c,d) -> (d,1) の場合
残りの数字は e だけなので、カードを選べず、明らかにありえません。
５）(1,a) -> (a,b) -> (b,c) -> (c,d) -> (d,e) -> (e,1) の場合
六枚のカードが選ばれ、1, a, b, c, d, e が二回ずつ現れているので、題意を満たします。
この場合は、２）の場合と同様に考えて、5!/2! = 60 通り。
これで、数字は尽くされたので終わりです。
したがって、10 + 60 = 70 通り、が答えになります。、

ネコの住む家　　 3月10日（木） 14:40:50　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24674

uchinyan

(少し修正しました。)
私の解法 #24674 を言い換えただけですが、変形？一筆書きの問題になるようです。
三つの点が一直線上にない六つの点を用意します。円周上の異なる六つの点を考えればいいでしょう。
各点に 1, 2, 3, 4, 5, 6 の数字を付けます。そして、例えば、点1と点2を結んだときに「21」と書かれたカードが選ばれたと考えます。
この状況で、各点を「一回ずつ通る」一筆書きを考えます。
今、点1から出て行って点1に戻ってくるものとします。ただし、それで到達していない点 x がある場合には、
点 x からの同様の一筆書きを考え、通っていない点がなくなるまでこれを続けます。
この一筆書きでは、必ず各点に入って出て行くので、これを数字が二回出現とみなします。
すると、次の場合が考えられます。
ａ）点1から出てすべての点を通って点1に戻ってくる場合：#24674 の５）に対応。
点1以外の点を並べればいいのですが、点1への出入りの向きは意味がないので半分にして、5!/2 = 60 通り。
ｂ）点1から出て一部の点を通って点1に戻ってくる場合：
残る点の数に従って次の場合があります。
ｂ１）一点が残っている場合：#24674 の４）に対応。題意の一筆書きは成立せず、意味なし。
ｂ２）二点が残っている場合：#24674 の３）に対応。二点に関し、題意の一筆書きは成立しません。
ｂ３）三点が残っている場合：#24674 の２）に対応。
残りの三点と合わせて二組の一筆書きが成立し、三枚ずつのカードが選ばれ、題意を満たします。
一筆書き自体は向きを無視すればそれぞれ一通りで、点1の方に二点を選べばいので、5C2 = 10 通り。
ｂ４）四点が残っている場合：#24674 の１）に対応。ｂ２）と同様で、題意を満たしません。
ｂ５）五点が残っている場合：#24674 には対応なし。点1だけになってしまうので、意味がありません。
以上で終わりです。
したがって、60 + 10 = 70 通り。

ネコの住む家　　 3月12日（土） 11:02:00　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24675

小学名探偵

使える数字が３種類なら、１通り
使える数字が４種類なら、３通り
使える数字が５種類なら、１２通り
使える数字が６種類なら、７０通り
使える数字が７種類なら、４６５通り
使える数字が８種類なら、３８２２通り
1，3，12，70，465，3822,...の数列は例の数列サイトにエントリされていないようです。

　　 3月10日（木） 16:41:30　　　　24676

小学名探偵

　　 3月10日（木） 17:04:56　　　　24677

小学名探偵

訂正
使える数字が８種類なら、3507通り
数列サイトのA001205のようです。

　　 3月10日（木） 17:21:12　　　　24678

uchinyan

もう一つ。最初考えていてこんがらがって止めた地道な解法です。もう一度トライしました (^^;
私の解法 #24674 の記法を使います。
1 及び 6 は特殊で、(a,1) = a1, (b,1) = b1, (c,6) = 6c, (d,6) = 6d となります。ただし、a, b, c, d は、すべて異なるとします。
このとき、次の場合分けが可能です。
１）a1, b1, 6c, 6d の場合：
(a,b) and (c,d), (a,c) and (b,d), (a,d) and (b,c) の三通りの選択が可能です。
したがって、a, b, c, d を 1 と 6 に振り分ける場合分けを考えて、4C2 * 3 = 18 通り。
２）a1, b1, 6a, 6d 又は a1, b1, 6c, 6b の場合：
残りの数字を x とすると、前者は (b,x) and (x,d) だけ、後者は (a,x) and (x,c) だけ、が可能です。
したがって、両方合わせて、4 * 3 * 2 = 24 通り。
３）a1, b1, 6a, 6b の場合：
四つの数で閉じてしまっているので、使える残りの数字は二つしかなく、題意を満たす組合せはありません。
４）a1, 61, 6c の場合：
残りの数字を x, y とすると、(a,x) and (x,y) and (y,c), (a,y) and (y,x) and (x,c) が可能です。
そこで、4 * 3 * 2 = 24 通り。
５）a1, 61, 6a の場合：
残りの数字を x, y, z として、(x,y) and (y,z) and (z,x) だけが可能です。
これは、4 通り。
以上ですべてです。したがって、18 + 24 + 24 + 4 = 70 通り。

ネコの住む家　　 3月10日（木） 18:15:53　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24679

uchinyan

掲示板、読みました。
#24675は、はなうさん、なかさん、他の皆さんと同じようです。
その原型の#24674は、着想が若干違うと思いますが、一応、同類とみなしていいのでしょう。
#24679は、さすがに泥臭いだけあって、かぶっていないかな (^^;

ネコの住む家　　 3月10日（木） 18:31:58　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24680

ゴンとも

通りよりも題意を満たす事象を全て書き上げたいと思ったので
カードを直に並べる感じの解法ですが通りは10倍化で答えはでて
疲れてまた今度
先ず、題意で使えるカードは
21,31,32,41,42,43,51,52,53,54,61,62,63,64,65の15枚
それを以下のように分けて
上で1を含むカードは{21,31,41,51,61}
上で2を含むカードは{21,32,42,52,62}
上で3を含むカードは{31,32,43,53,63}
上で4を含むカードは{41,42,43,54,64}
上で5を含むカードは{51,52,53,54,65}
上で6を含むカードは{61,62,63,64,65}
選ぶカードはそれぞれの数字が2個だけで全部
なので上の6集合で
5から2個選んでそれぞれ10通り・・・・・・①
{21,31},{21,41},{21,51},{21,61},{31,41},{31,51},{31,61},{41,51},{41,61},{51,61}1段
{21,32},{21,42},{21,52},{21,62},{32,42},{32,52},{32,62},{42,52},{42,62},{52,62}2段
{31,32},{31,43},{31,53},{31,63},{32,43},{32,53},{32,63},{43,53},{43,63},{53,63}3段
{41,42},{41,43},{41,54},{41,64},{42,43},{42,54},{42,64},{43,54},{43,64},{54,64}4段
{51,52},{51,53},{51,54},{51,65},{52,53},{52,54},{52,65},{53,54},{53,65},{54,65}5段
{61,62},{61,63},{61,64},{61,65},{62,63},{62,64},{62,65},{63,64},{63,65},{64,65}6段
最初はどの段をを選んでも同じなので最初の1段を選びその段の最初を選び
{21,31}を選んで(排反事象{21,41},{21,51},{21,61},{31,41},{31,51},{31,61},{41,51},
{41,61},{51,61}も同じ通り数)・・・(略)
{21,31,42,53,64,65},{21,31,42,54,63,65},{21,31,43,54,62,65}
{21,31,43,52,64,65},{21,31,43,54,62,65},{21,31,52,54,63,64}
{21,31,53,54,62,64}の7通りこれと①とより7*10=70通り・・・・・・(答え

愛知県豊川市　　 3月10日（木） 20:56:12　　 MAIL:ｆｔｔnm528@ybb.ne.jp 　　24681

uchinyan

#24656のエルクさん、#24658のみかんさんの解法と、私の解法#24679とは、場合分けの仕方が少し違いますが、私の方が要領が悪い、
基本的な考え方は近いようです。
#24673のDrKさんの解法は、見逃していましたが、私の解法#24674と、着想も含めて似ているようです。
#24667のTaku-chanさんの解法は、はなうさん他の一筆書きの解法に近いですが、着想が全く違い、非常に興味深いです。

ネコの住む家　　 3月10日（木） 21:39:58　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24682

小学名探偵

はなうさん他のグラフによる方法にしたがって、
数字の種類が１２（ノードの個数１２）のとき、
どのノードも２つの枝をもつ場合の数を求めてみました。
（○内の数字は、一筆書きされるノード数を表します）

⑫　11!/2=19958400
⑨と③　C(12,3)*8!/2=4435200
⑧と④　C(12,4)*7!/2*3=3742200
⑦と⑤　C(12,5)*6!/2*4!/2=3421440
⑥と⑥　1/2!*C(12,6)*(5!/2)^2=1663200
⑤と④と③　C(12,5)*C(7,3)*4!/2*3=997920
⑥と③と③　C(12,6)*1/2!*C(6,3)*5!/2=554400
④と④と④　1/3!*C(12,4)*C(8,4)*(3)^3=155925
③と③と③と③　1/4!*C(12,3)*C(9,3)*C(6,3)=15400
計34944085通り

　　 3月10日（木） 23:08:31　　　　24683

arijune

しゃきーんとひらめいたと思ったら、なんか当然ことのように議論されていてとってもorz（^ ^;)
え？答え知ってるからインチキだって？
いやいや、ちゃんと考えましたよ。
とりあえず1～６がcyclicに並んでるから、１～６を円周上にふる。
１と残りの５点のうちどの２点をとっても一般性はうしなわれないので、1-4,1-5と線を引く。次に4から線を引くが５と結ぶと、あとは2-3-6で三角形を作るしかない。また、4から236のいづれに引いても一般なので4-3を作ると、3-5としたとき2-6が余ってしまって、不適よって3-2or3-6と引くしかない。すると、3-2のとき2-6 6-5のみが題意を満たす。3-6の時も同様。
よって5C2(1+3*2)=70
ヌルポ

　　 3月11日（金） 1:21:56　　　　24684

小学名探偵

A001205からの情報ですが、
数字の種類がｎ個のとき、場合の数をA(n)
と書くと、次の漸化式が成り立つようです。
A(n+1)=C(n,1)*A(n)+C(n,2)*A(n-2)　　　　　式(1)
たとえば、
A(6)=C(5,1)*A(5)+C(5,2)*A(3)
=5*12+10*1=70　　　　　　　　　　　　式(2)

いま、５つのノードがどれも２つの枝をもつグラフの集合をG(5)と書きます。
式(2)が成立する訳は、
新しいノードを付加する：
G(5)に属する各グラフ（５つのノードがどれも２つの枝をもつ各パターン）
について、５つある枝のなかから１つを選び、
その枝の上に６番目のノードを置きます。これにより、G(6)に属するグラフができます。
これによる場合の数は5*A(5)通り。
３角形の分離：
G(5)に属する各グラフ（５つのノードがどれも２つの枝をもつ各パターン）
について、２つのノードを選び、この２つのノードに６番目のノードを加えた
３ノード間で閉ループ（三角形）をつくります（G(3)に属するグラフ)。
この三角形分離のために、G(5)に属するグラフから、
２ノードがなくなってグラフはG(5-2)に属することになります。
グラフ全体は、G(3)に属するグラフとG(5-2)に属するグラフをあわせたものなので、
G(6)に属するグラフになります。
これによる場合の数はC(5,2)*A(3)通り。
合計すると、式(2)になります。
同様の議論で、式(1)が成り立ちます。

　　 3月11日（金） 9:08:23　　　　24685

武田浩紀

#24685
A(n+1)=C(n,1)*A(n)+C(n,2)*A(n-2)
の漸化式について。

各数字がいくつかのグループに分かれて円を作って並んでいると考えましょう。
例えばn=10のとき
1→ 2→ 3
↑　　　↓
6← 5← 4
7→ 8
↑　↓
10← 9

ここに11番目の数字がやってきてこの列にいれてもらうことにします・・・（＊）
入り方は10通りありますね。これを表しているのがC(n,1)*A(n)

じゃあC(n,2)*A(n-2)は何を表しているかというと（＊）では作れないパターン、
11番目の数字と他の数字2つで三角形をつくり、残りで円を作って並んでる場合の数です。
(#24685の表現変更しただけですが)

　　 3月11日（金） 14:19:15　　　　24686

さいと散

巡回経路で 6!/2+6C3/2 でやりました。

　　 3月11日（金） 12:20:52　　　　24687

uchinyan

#24685：
なるほど。興味深く読ませて頂きました。
実は、似たようなことを考えようとしていたのですが、グラフの分割で行き詰っていました (^^;
提示されている漸化式には、グラフの分割が自然に含まれており、見事だなぁ、と感心です。
なお、今のところ掲示板で提示されている解法は、私の泥臭い #24679 以外はすべて、
表現は違いますが、一筆書きの解法と等価、変換可能、なようですね。

ネコの住む家　　 3月11日（金） 12:52:54　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24688

小学名探偵

#24685 訂正します。

A001205からの情報ですが、
数字の種類がｎ個のとき、場合の数をA(n)
と書くと、次の漸化式が成り立つようです。
A(n+1)=C(n,1)*A(n)+C(n,2)*A(n-2)　　　　　式(1)

式(1)が成立する訳は、
いま、Ｎ個のノードがどれも２つの枝をもつグラフの集合をG(n)と書きます。
G(n+1)に属するグラフにおいて、(n+1)番目のノード
（G(n)に属するグラフはないノード）は、
（１）一筆書きされる４以上のノードのひとつであるか、
（２）一筆書きされる３つのノードのひとつであるか
のいずれかです。
（１）については、つぎの方法で得られます。
新しいノードを付加する：
G(n)に属する各グラフ（n個のノードがどれも２つの枝をもつ各パターン）
について、n本ある枝のなかから１つを選び、
その枝の上に(n+1)番目のノードを置きます。
これによる場合の数はn*A(n)通り。
（２）については次に方法で得られます。
３角形の分離：
ｎ個のノードののなかから、２個のノードを選び、この２個のノードに
(n+1)番目のノードを加えた３ノード間で閉ループ（三角形）をつくります。
そして、残りｎ－２個のノードでG(n-2)に属するグラフをすべてつくります。
これによる場合の数はC(n,2)*A(n-2)通り。
したがって、式(1)が成り立ちます。

　　 3月11日（金） 12:47:12　　　　24689

uchinyan

結局は同じなのですが、こんな考え方もありますね。掲示板に書き込みがないようなので、念のため。
着想は、#24667のTaku-chanさんに近く、一筆書きにも近いのかな、
具体的な計算は、#24656のエルクさん、#24658のみかんさん、#24681のゴンともさんに近い、
という感じの解法です。

カードには条件を満たす2桁の数が書いてあるのですが、
これを分解して、1 ～ 6 までの数字が一つずつそれぞれに書かれたカード6枚があるとします。
すると、与えられた条件から、このカードの組から異なる2枚を選ぶと元のカードの数字を一意に決定でき、逆もいえて、
元のカードに書かれた数と新しいカードの異なる数字二つの組合せは、一対一に対応します。
そこで、以降は、1 ～ 6 までの数字が書かれたカードの組があると考えます。
この場合、題意の状況は簡単になって、このカードの組が2組、1 ～ 6 までの数字が書かれたカードが2枚ずつあることを意味します。
すると、これら12枚から条件を満たす数字の組合せを作る場合の数を求めれば、それが答えになります。
1 と組み合わせる数字は、片方の 1 に対して5通り、もう一方に対して4通り、ですが、
重複するので半分にして、5 * 4 / 2 = 10 通り。
これで、a1, b1, a > b ができたとすると、後の数字を c, d, e (ただし2組あることに注意)として、
ab 及び c, d, e の組合せの場合：c に対して2通りですが、c は二つあるので半分になって、結局 2/2 = 1通り。
ab を作らず c, d, e と混ぜて組み合わせる場合：
a と c, d, e との組合せで3通り。b と c, d, e との組合せは、a と同じものを組み合わせると後ができないので2通り。
残りの組合せは2通り。しかし、c, d, e が2組あることから半分になって、結局、3 * 2 * 2 / 2 = 6通り。
したがって、全体で、10 * (1 + 6) = 70通り。

ネコの住む家　　 3月11日（金） 14:54:39　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24690

水田X

ふう、ずいぶんいろいろ誤解して苦労したけど計算は１０＊（１＋２＊３）＝７０でした。むずかしく細かく分類して考えすぎました。

　　 3月11日（金） 16:16:26　　　　24691

uchinyan

2005/03/12：ごめんなさい。最初の証明は間違っていました。訂正します。

#24690の解法は、実は、#24688で失敗したと言った漸化式へのトライの副産物です。
考え直して、漸化式、A(n+1) = C(n,1) * A(n) + C(n,2) * A(n-2) を#24690流に証明しておきます。

#24690を一般化すると、1 ～ (n+1) までの数字が一つずつそれぞれに書かれたカード (n+1) 枚の組が2組あることになります。
1 以外を、a, b, c, d, e, ..., ただし a > b、a > c とします。
A(n+1) は、(n+1) 個の 1, a, b, c, d, e, ... の数字の組の2組から、条件を満たす (n+1) 個の数を作る場合の数になります。
基本的には a, b, c, d, e, ... に 1 を追加すればいいのですが、以下では、#24690を少し改良して、次のように考えます。
１）a1, b1, ab 及び c, d, e, ... の組合せの場合
まず、1 と a, b との組合せは、n(n-1)/2 = C(n,2) 通りになるので、a1, b1, ab で C(n,2) 通り。残りの (n-2) 個で A(n-2) 通り。
したがって、C(n,2) * A(n-2) 通り。
２）a1, b1 だが ab を作らず c, d, e, ... と混ぜて組み合わせる場合
1 を除いた部分が A(n) 程度なのですが、ab を作らないので、これを除く必要があります。
今、A(n) において、作られている n 個の数のうちから一つを取り出し、これを ab とします。
これを取り去って、代わりに、a1, b1 を追加すればいいわけです。これが求める数の組になります。
ただ、このときの場合の数の数え方が難しく失敗していました (^^;
これは、ちょっと複雑ですが、次のような「トリック」を行えばいいようです。
a は、A(n) で、他の数字と ab 以外の数を一つ作っています。この数字を c とし、作っている数を ac とします。
ここで場合の数を数えるために、ac に対して c1 という数を1:1に対応させます。
すると、この1:1対応によって、a1 以外は、1, b, c, d, e ... の n 個の数字で構成されていることになります。
このときの場合の数は、a1 以外が A(n) 通り、a1 は a の選択で C(n,1) 通り、結局 C(n,1) * A(n) 通りになります。
（なお、実際に構成される数は、c1 を ac に置き換えたものなので要注意。）
１)及び２）から、結局、両方を合わせて、A(n+1) = C(n,1) * A(n) + C(n,2) * A(n-2) になります。

正直言って、ちょっとややこしいですが、小学名探偵さんの#24689と比較すると、
１）は（２）の「３角形の分離」の部分、２）は（１）のノードを付加する部分に対応します。

ネコの住む家　　 3月12日（土） 14:12:04　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24692

n厨

今までにやってきたことから常套手段として一筋書きに帰着
一般化を書こうと思ったらもうすでに出てますね

　　 3月11日（金） 21:13:06　　　　24693

ほげ

はなう　さんたちの解法に気がつきませんでした。すばらしいです。

私は次のように考えました
1,1,2,2,3,3,4,4,5,5,6,6のカードを用意　このカードを組み合わせます
3と6なら　63にするわけです

2枚の1とくっつくのは　2,3,4,5,6のうちから２種類で　4C2=10通り
今たとえば　1が２枚　2,3　とくっついたとして
のこりのカード2,3,4,4,5,5,6,6のくっつき方を考えます　

2と3がくっついた時
　残りのカードのくっつき方は4-5　4-6　5-6の１通り
2と3がそれぞれ異なる数とくっついた時
　2とくっつく数は3通り　3とくっつく数は２通り　で　6通り
　たとえば　2と4　3と5がくっついたとすると
　残りの数は　4566となり　残りのくっつき方は　4-6　5-6しかない

以上から　10C2 ×(1+3×2)=70　通り　となりました。

北の隠れ家　　 3月12日（土） 16:12:15　　 MAIL:micci@sansu.org HomePage:みっちの隠れ家　　24694

水田X

わたしはそれぞれのカードが一枚づつ、３枚づつ、４，５枚づつの時どうなるのか週末あれこれ考えてます。がまだ考え中です。４枚の時は1-2-3-4-5-6-1の一筆書きの場合はもう一周一筆書きを1-3-5-2-6-4-1てななんて続かせるんだろうなあ。で何通りだろうってあれこれ考えてます。

　　 3月13日（日） 0:05:25　　　　24695

uchinyan

#24695：
実は似たようなことを少し思ったのですが、まずは、どのように拡張するのが面白いか、意味がありそうか、
それを見極める必要があるかなぁ、と思っていました。
ただ、カードに書かれている数を2桁に限り、使える数字を 1 ～ 6 に限るならば、次のようなことがすぐに分かります。
今、使える数字を、一応、1, ..., n とします。ただし、カードに書かれている数は、2桁に限るとします。
この場合、書かれている数は、21, 31, ,,., n1, 32, 42, ..., n2, ..., n(n-1) となります。
したがって、題意を満たす何らかの数字が含まれるカードの枚数を k 枚とすると、1 <= k <= n-1 です。
k 枚のときの場合の数を A(n,k) とします。
明らかに、k = n-1 の場合は、すべてのカードを選んだ場合で A(n,n-1) = 1 通り。
また、k >= n ならば、A(n,k) = 0 です。
一般の A(n,k) の場合は、面倒そうだったのでちゃんと考えていませんが、
少なくとも、k 枚の場合に選んだカードを、すべてのカードから取り去った残りのカードを考えると、
すべてのカードがあれば n-1 枚なので、これから k 枚の場合を除くことになり、(n-1-k) 枚の場合に対応します。
もちろん、逆もいえます。
例えば、今回の問題の解である 21, 31, 42, 53, 64, 65 に対して、41, 51, 61, 32, 52, 62, 43, 63, 54 を考えれば、k = 3 を満たします。
#24695＞４枚の時は1-2-3-4-5-6-1の一筆書きの場合はもう一周一筆書きを1-3-5-2-6-4-1
これは、k = 1 で 51, 42, 63 <---> k = 4 で 21, 32, 43, 54, 65, 61, 31, 53, 52, 62, 64, 41 です。
つまり、k 枚の場合と (n-1-k) 枚の場合は１：１に対応しており、A(n,k) = A(n,n-1-k) です。
今回の場合 n = 6 に限ると、
* k = 1 : A(6,1) = 15 通り。#24667のTaku-chanさんの結果の一部。
* k = 2 : A(6,2) = 70 通り。今回の問題です。
* k = 3 : A(6,3) = A(6,5-3) = A(6,2) = 70 通り。
* k = 4 : A(6,4) = A(6,5-4) = A(6,1) = 15 通り。
* k = 5 : A(6,5) = 1 通り。
* k >= 6 : A(6,k) = 0 通り。
となります。
グラフの一筆書きに対応させるのは、k が偶数の場合は、各点を k/2 回通ると考えるのでしょうが、
k が奇数のときは難しそう(そのままでは不可能？)な気がします。
なお、A(n.k) の一般の場合、多分、漸化式、は、まだ考えていません。
また、問題の拡張も、カードに書かれた数が2桁に限らないというものもありそうです。
一般の場合は難し過ぎそうですが、k 桁の場合は、何か分かるかもしれないな、と思います。
ただ、こればかりも考えていられないので．．．

ネコの住む家　　 3月13日（日） 14:11:42　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24696

uchinyan

#24692：
＞２）a1, b1 だが ab を作らず c, d, e, ... と混ぜて組み合わせる場合
今のままでも間違ってはいないのですが、次のようにすれば十分でした (^^;
＜今、A(n) において、作られている n 個の数のうちから一つを取り出し、これを ab とします。
＜これを取り去って、代わりに、a1, b1 を追加すればいいわけです。この操作によって、A(n) は変わりません。
＜そこで、ab を選ぶのに C(n,1) 通りなので、C(n,1) * A(n) 通り。
ずいぶんと簡単になりました。

#24696：
その後、時間がなくて考えていないのですが、例えば、2桁で、n, k が奇数の場合には、解がないですね。

ネコの住む家　　 3月15日（火） 13:42:53　　 MAIL:uchi@sco.bekkoame.ne.jp 　　24697

姉小路

場合分けして考えました。
ⅰ）６Ｘ、６Ｙ、Ｘ１、Ｚ１　のとき
　　Ｘ、Ｙ、Ｚを決めると、残りの２つは決まり、4*3*2=24　とおり
ⅱ）６Ｘ、６Ｙ、Ｚ１、Ｗ１　のとき
　　Ｘ、Ｙ、Ｚを決めると、残りの２つはそれぞれに対して３通りある。
　　従って、4*3/2*3=18　とおり
ⅲ）６１、６Ｘ、Ｘ１　のとき
　　Ｘを決めると残りも決まるので、4　とおり。
ⅳ）６１，６Ｘ、Ｙ１　のとき
　　Ｘ、Ｙを決めると残りの３つはそれぞれに対して２通りある。
　　従って、4*3*2=24　とおり。
∴24+18+4+24=70　とおり

ⅱ）が36通りだと思いこんでいて六日間悩んでました（汗

算数の街　　 3月15日（火） 17:53:48　　 MAIL:pctakada@mail.goo.ne.jp HomePage:高田の呟き　　24698

Revin

(i)a-b-c-d-e-f　で一周するパターン
6つの数珠順列なので5!/2=60通り

(ii)a-b-c d-e-f　の2つで一周するパターン
3すくみを2つ作るので6C3/2=10通り

足して70通り
で解きましたあ

　　 3月15日（火） 20:23:21　　　　24699

トトロ＠Ｎ

やっとでけた～
#24698　姉小路さんと全く同じ解き方ですが、ⅲ）ⅳ）を見落としてました。

兵庫県明石市　　 3月15日（火） 23:47:47　　 MAIL:h-sakai@zb3.so-net.ne.jp 　　24700