面白い問題おしえて～な十七問目

面白い問題おしえて～な十七問目 at MATH

928:１３２人目の素数さん
11/05/29 06:34:43.15
>>925
a個の中からb個(0<=b<=a)を選択する組み合わせだから、その組み合わせの総数は有限

929:１３２人目の素数さん
11/05/29 09:30:45.13
そこかよ。
んじゃ、１だろ。

930:１３２人目の素数さん
11/05/31 21:53:51.62
n個の数字(0～9)を横一列に並べてできる文字列を
全て1つ以上含む文字列を作りたい。
この文字列に必要な数字の個数の最小値とその作り方を求めよ。

931:１３２人目の素数さん
11/05/31 22:03:58.12
>>910
Σ[k=0, a-b](C[a-b, k]/C[a, b+k])
a=115、b=46のとき
Σ[k=0, 69](C[69, k]/C[115, 46+k])
= 590295810358705651712/41023433264885418154367916094212808
= 1.438923472219419558090714758372489854340760324323379... × 10^-14

932:１３２人目の素数さん
11/06/01 02:26:31.49
>>931

　Ｃ[a-b,k]/Ｃ[a,b+k] = Ｃ[b+k,b]/Ｃ[a,b] = {Ｃ[b+k+1,b+1] - Ｃ[b+k,b+1]}/Ｃ[a,b],
k=0,1,･････,a-b の和をとると、
　Ｃ[a+1,b+1]/Ｃ[a,b] = (a+1)/(b+1) = 116/47,
となるんぢゃね？

933:１３２人目の素数さん
11/06/01 03:33:00.30
>>910

すべての組合せ： 2^a
b個の細菌を含む組合せ： 2^(a-b)
なので　(1/2)^b = 1.4210854×10^(-14)
かな？

934:１３２人目の素数さん
11/06/01 07:07:55.83
>>932
間違えた、訂正
(Σ[k=0, a-b]C[a-b, k])/(Σ[k=0, a-b]C[a, b+k])
以下同文

935:あんでぃはアホ ◆AdkZFxa49I
11/06/01 07:13:19.32
>>923
あんでぃ

936:１３２人目の素数さん
11/06/02 01:54:14.18
>>934

Σ[k=0,a-b] Ｃ[a-b,k] = 2^(a-b),

Σ[k=0,a-b] Ｃ[a,b+k] = 2^a - Σ[L=0,b-1] Ｃ[a,L]
　　= 2^a - 5.1494160339320×10^32
　　= 2^a / 1.01255237707844

937:１３２人目の素数さん
11/06/03 23:35:24.15
cosx*tanx=cos2x (-π≦x≦π)

938:１３２人目の素数さん
11/06/04 02:20:55.39
>>930
n=3 のとき最小値 1002, n=4 のとき最小値 10003、一般の n ではたぶん 10^n + n - 1

n=3
・最初の文字列を 12 とする
・12 の後ろに 312 を付け加えて 12312 とすると、この文字列は 123,231,312 を含む
・23 の後ろに 423 を付け加えて 12342312 とすると、この文字列は 234,342,423 を新たに含む
・同様の操作を続けて相異なる3文字から成る長さ3の全ての文字列を含む文字列を構成できる
・一箇所の 12 の後ろに 112 を付け加えると、文字列は 121,211,112 を新た含む
・同様の操作を続けて aab, aba, baa という形の文字列も全て含む文字列を構成できる
・一箇所の 00 の後ろに 0 を付け加えると、文字列は 000 を新たに含む
・同様にして 111～999 も含む文字列を構成できる

以上で構成された文字列は条件を満たす
各段階で付け加えた文字数と新たに含まれる長さ3の文字列の数は同じなので、
文字列全体の長さは 1002、最小性は明らか

n=4
・最初の文字列を 123 とし、abc の後ろに dabc を付け加える操作を続けて、
　相異なる4文字から成る長さ4の全ての文字列を含む文字列を構成する
・abc の後ろに aabc を付け加えて、abca, bcaa, caab, aabc を新たに含む文字列を構成する
・bac の後ろに abac を付け加えて、baca, acab, caba, abac を…
・aba の後ろに ba を付け加えて、abab, baba を…
・aab の後ろに baab を付け加えて、aabb, abba, bbaa, baab を…
・aab の後ろに aaab を付け加えて、aaba, abaa, baaa, aaab を…
・aaa の後ろに a を付け加えて、aaaa を…

939:１３２人目の素数さん
11/06/04 15:59:43.59
>>930
n-1 個の数字の列を頂点とし、頂点 a_1a_2...a_n から a_2...a_na_{n+1} への有向線分を持つ有向グラフを作る．
この有向線分に a_{n+1} という数字を割り振っておく。
各頂点に出入りする有向線分は 10 本づつで、
有向グラフは連結なので、一筆書きが可能である．

940:１３２人目の素数さん
11/06/04 16:04:17.09
（続き）この一筆書きに現れる有向線分に割り振られた数字を順に並べ
その後に最初の n-1 個を追加したものが求める文字列となる。
有向線分の数は 10^n なので 10^n+n-1.

941:１３２人目の素数さん
11/06/05 00:11:38.37
>>930
最小値ｎ
元の文字列を１種類の数字にすればよい

カンタンすぎるねｗ
あるいは出題の不備

942:１３２人目の素数さん
11/06/05 00:18:55.37
>>941
10^n　個の文字列を全て内部に持つような文字列という意味じゃないの。

943:１３２人目の素数さん
11/06/05 00:24:41.42
>>941
例えばn=2だったら
00 01 02 03 04 05 … 99を全て含む文字列を作れってことでしょ
0123だったら01 12 23を含んでいる事になる

944:１３２人目の素数さん
11/06/05 00:27:14.36
>>942
それだと問題文の（0～9）という部分が不備。

＞n個の数字(0～9)を横一列に並べてできる文字列を
こういう言い方はしない。

その10^n通りの文字列全てを内部にもつなら
普通の文字列なら10^n+n-1.、環状の配列なら10^nが最小値だろうな

945:１３２人目の素数さん
11/06/05 00:37:50.00
>>944
数字(0～9)　で意味は取れるが、はて。

946:１３２人目の素数さん
11/06/05 00:46:13.65
>>944
> ＞n個の数字(0～9)を横一列に並べてできる文字列を
> こういう言い方はしない。

そこで切るからだよ。

n個の数字(0～9)を横一列に並べてできる文字列を全て1つ以上含む文字列

意味の通る表現だと思うが。

947:１３２人目の素数さん
11/06/05 00:55:39.11
今まで普通に通じてたんだから通じるってことだろうが。

948:１３２人目の素数さん
11/06/05 12:12:16.56
意味を補えば通じるから普通に解けるけど、数学的厳密さはないってことだと思うよ。
数学の問題として、「○○さんは解けているからこれは意味が通じる問題です」というのはちょっと。
もっとも、問題集や参考書じゃないんだから、「普通に意味が通じる」程度で十分なんだけど。割とどうでもいい議論。