基本情報の問題です。 2種類の文字AとBを一個以上、最大n個並べた符号を作る。60通りの符号を作る時

基本情報の問題です。


2種類の文字AとBを一個以上、最大n個並べた符号を作る。60通りの符号を作る時のnの最小値はいくらか？

答えが5です。

教えて下さい

No.2 回答者： yuji3690 回答日時： 2017/03/12 23:36

1個だとAとBの2通り

2個だとAAとABとBAとBBの4通り+1個でできる2通り、
3個だと（略）8通り+4+2
これを式で表すと、
n個だと2^n通りで、n-1個までに2^n-2通りできているので、
2^n+2^n-2=2^(n+1)-2通りと表現できる。
2^(n+1)-2≧60となる最小のnを求めればよいので、
2^(n+1)≧62
nは整数なので、
2^5=32,2^6=64より
求めるn+1=6なので、
n=5となる。

No.1 回答者： fine_day 回答日時： 2017/03/12 23:34

１文字目がＡまたはＢの２通り。

２文字目もＡまたはＢの２通りなので、２文字並べたときの組み合わせは2^2＝４通りあります。
（ＡＡ、ＡＢ、ＢＡ、ＢＢの４つです）

同じように考えるとn文字並べたときの組み合わせは2^nとなります。
60<2^nとなるnを求めるとn＝5。
よって答えは５です。
なお５文字並べたときは64通りの符号ができます。