[流れ星]
平成１１年１１月２５日更新
[流れ星]
第３７回
数学的な応募問題＜解答募集期間：１１月２１日〜１２月５日＞
［橋を渡る］
太郎さんの勤務している学校に行くには、大きな川（揖斐川）を渡らなければなりません。こんな問題を考えました。
この川にはｎ個の橋が架かっています。太郎さんは自転車で後戻りせず、自転車の轍に交差がないように、すべての橋を一度渡りきってみたくなりました。川上から順に、橋に自然数をつけて、１番から渡り始めて、最後に渡り終える橋は何番でも良いとします。次の問に答えてください。
問題１：ｎ＝２，ｎ＝３，ｎ＝４，ｎ＝５，ｎ＝６のときの轍の数は何通りですか。
（ただし、ｎ＝１のときは、便宜的に１通りとすます。）
参考図のように、数字の順番にて、轍を表現して、何通りか答えてください。
問題２：一般の場合の轍の数をｎで表すことは、現在分かっていないようです。
何か漸化式とか、ここまで発見したとかレポートみたいで結構ですので、知らせてください。
太郎さんは、「数学１００の発見（数学史を彩る発見と挑戦のドラマ）：数学セミナー編集部」＜日本評論社＞を読んでいて、考えました。
＜Ｊｕｎ＞さんからの解答 ２３日受信 ２５日更新
答は
「ここをクリック」。してください。＜ch3cooh＞さんからの解答 ２４日受信 ２５日更新
プログラムで、解析しました。構造を持った解析を行っていないため、相当遅いプログラムです。
-- 構造解析としては･･･橋の上の轍については、縄跳びの問題と全く同じ構造であることが
条件となります。(n= 2*kの場合)
橋の下の轍についても、非接続点が一部あるものの縄跳びの問題とほぼ同じ条件を持っていると考えられます。
非接続点については、縄跳びの問題に対して、途中にブランクを挿入することで、計算できると思います。
ここまでで、上･下のカウントが出てきたので、その積が答えであると楽なのですが、条件の一筆書きというのを満足しない接続が一部分存在します。これは、一筆書きの部分に閉鎖した組を持っているものです。
(例) 上の組合わせ
U-1)1-2, 3-4
U-2)1-4, 2-3
下の組合わせ
D-1)*1, 2-3, *4
D-2)*1, 2-4, *3
D-3)*1, *2, 3-4
上･下の単純な組合わせは6種類
ただし、(U-1,D-3), (U-2,D-1)の組合わせは無効であるため、有効なのは4種類のみ。
無効な組の計算が出来れば、数式で表せる？？
-- 解析結果 --
2 : 1
3 : 1
4 : 2
5 : 4
6 : 10
7 : 24
8 : 66
9 : 174
10 : 504
11 : 1406
12 : 4210
13 : 12198
14 : 37378
15 : 111278
16 : 346846
17 : 1053874
18 : 3328188
-- program start --
#include <stdio.h>
#define N 100
struct link {int l, r ;} ;
int
check( int n, int p1, int p2, struct link *lk )
{ while( n> 3 )
{ int l, r ;
n-= 2 ;
l= lk[n].l ;
r= lk[n].r ;
if ( (p1<l)&&(l<p2) )
{
if ( (p1>r)||(r>p2) )
{
#ifdef DEBUG1
printf( "(%2d %2d)(%2d %2d)::", p1, p2, l, r ) ;
#endif
return 1 ;
}
} else {
if ( (p1<r)&&(r<p2) )
{
#ifdef DEBUG1
printf( "(%2d %2d)(%2d %2d)::", p1, p2, l, r ) ;
#endif
return 1 ;
}
}
}
return 0 ;
}
int
new1( int n, int m, int *list )
{
int i, v, f ;
v= list[m]+1 ;
do {
f= 0 ;
for( i= 0 ; i< m ; i++ )
{
if ( list[i]== v )
{
v++ ;
if ( v!= n ) f= 1 ;
break ;
}
}
} while ( f ) ;
if ( v== n ) return 0 ;
list[m]= v ;
return 1 ;
}
int
gen( int n )
{ int list[N] ;
struct link lk[N] ;
int i, j, f, c ;
list[0]= 0 ;
i= 1 ;
c= 0 ;
do {
f= new1( n, i, list ) ;
// printf( "%2d %2d", i, list[i] ) ;
if ( f )
{
int p1, p2 ;
p1= list[i-1] ;
p2= list[i ] ;
if ( p1> p2 )
{
if ( (i>3)&&(check( i, p2, p1, lk )) )
{
#ifdef DEBUG1
for( j= 0 ; j< i ; j++ )
printf( " %2d", list[j] ) ;
putchar( '\n' ) ;
#endif
continue ;
}
lk[i].l= p2 ;
lk[i].r= p1 ;
} else {
if ( (i>3)&&(check( i, p1, p2, lk )) )
{
#ifdef DEBUG1
for( j= 0 ; j< i ; j++ )
printf( " %2d", list[j] ) ;
putchar( '\n' ) ;
#endif
continue ;
}
lk[i].l= p1 ;
lk[i].r= p2 ;
}
if ( i== n-1 )
{
#ifdef DEBUG2
for( j= 0 ; j< n ; j++ )
printf( " %2d", list[j] ) ;
putchar( '\n' ) ;
for( j= 1 ; j< n ; j++ )
printf( "(%2d %2d)", lk[j].l, lk[j].r ) ;
putchar( '\n' ) ;
#endif
c++ ;
}else {
i++ ;
list[i]= -1 ;
}
} else {
i-- ;
}
} while ( i>= 1 ) ;
// new1( int n, int m, int *list )
// check( int n, int p1, int p2, struct link *lk )
return c ;
}
int
main( void )
{
int i, c ;
for( i= 2; i< 20 ; i++ )
{
c= gen( i ) ;
printf( "%2d : %8d\n", i, c ) ;
}
return 0 ;
}
＜水の流れ：コメント＞２５日記入
＜ch3cooh＞さんが一筆書きの部分に閉鎖した組に着目されましたが、これは良い発想ですね。感心しました。
13 : 12198 になっていますが、私の本は１２１９６ になっていて ２個違っていました。どちらが
正しいか分かりません。誰か教えてください。
＜自宅＞
mizuryu@aqua.ocn.ne.jp
