数字を作ってください

質問

0と1のみを使って全ての数を比べた時に5桁で4つ以上異なるような数字を4つ作ってください！
例えば3桁で2つ異なるものの4つは
000
110
101
011
となります。これら4つはどれを比べても２つ異なっています。同様に5桁の異なるものを作ってください。それとも5桁では作れませんか？
5桁で作るとしたら最低何桁必要でしょうか？

回答No.3

tmpname

今度は、「N桁の数字4つで、互いに少なくとも5桁以上ビットが異なるもの」を作ろうとすると、先程と同様に、あるN桁の数字と少なくとも5桁以上ビットがことなるもの同士は、少なくともN - 2 * (N-5) = 10 - N桁はビットが同じだから、
(10 - N) + 5 ≦ N → N ≧ 7.5
で、少なくとも8桁ないといけないことが分ります。

実際、
00000000
00011111
11100011
11111100
はその一つの例になっています。

お礼

ありがとうございました！

回答No.2

tmpname

最初の質問について：

例えば5桁のビット列A, B, Cを考え、AとB、AとCが少なくとも4桁ビットが異なるとします。この時BとCを比べるとどうなるでしょう？結果は、『少なくとも3桁はビットが同じ』。

というのが、Aのビットを反転させたものをA'とおくと、AとBとで少なくとも4桁ビットが異なる、ということは、逆に言うとA'とBとは少なくとも4桁ビットが同じ、つまり、A'とBとでは異なるビットの桁が多くて1つしかない、という事です。A'とCも同様です。よって、BとCとでは、異なるビットの桁は多くて2つしかありません。つまり、BとC とでは少なくとも3桁はビットが一致することになるため、不可能です。

同様に、「M桁で少なくとも互いに(M-1)ビット以上異なるような数字を4つ作る」というのを考えると、
＊あるM桁のビット列Aと少なくとも(M-1)ビット異なるM桁のビット列同士は、少なくとも(M-2)桁ビット列が同じ
＊この2つが、(M-1)ビット以上桁が異なるということだから、この2つのビット列は、少なくとも(M-2)桁共通するビット列と、(M-1)桁異なるビット列をもつ
ということなので、

(M-2) + (M-1) ≦ M → M≦3

ということになり、3桁以下でないとできない事が分ります。

お礼

ありがとうございました！

回答No.1

f272

> それとも5桁では作れませんか？

無理です。

> 5桁で作るとしたら最低何桁必要でしょうか？

意味がわかりません。