😊出会いの泉😊

10人いたら簡単だとして、9人解ができそうでできない……
必要な最少人数って何人なんでしょうね？

DD++さんにとっては 10人は簡単……　うお。

9人解の探索をしようと思い、ファノ平面は使えないかと思いつきまして。

"000 000 000 ", 0,0,0,
"110 011 101 ", 6,3,5,
"111 110 001 ", 7,6,1,
"010 100 110 ", 2,4,6,
"011 001 010 ", 3,1,2,
"100 111 011 ", 4,7,3,
"001 101 100 ", 1,5,4,
"101 010 111 ", 5,2,7

これ、使えませんし、ここになにか1ビットを追加してもどうにもならないのでした。
たとえば
"010 100 110 ", 2,4,6,
"011 001 010 ", 3,1,2,
"001 101 100 ", 1,5,4,
の部分だけでも、1ビットを増やしたくらいでは、2人の嘘つきを確定できません。

はい、10人なら簡単です。
9人の場合も嘘つきが「確定2人」なら可能なんですけどねえ……

「確定２人」というお言葉に驚きました。
探したのですが、見つからず、です。

副産物として、以下の通りの変なものを見つけました。

3 ビットの 7 つの数を数珠つなぎにします。
" 100 111 010 110 001 011 101 "
数珠ですので、最後尾の 101 の次には 先頭の 100 につながることとします。

この数珠の、三連続する数の組みは　七通りあるわけですが、それぞれの組のなかの3つの数を XOR 演算すると、被らずに 001 から 111 までが漏れなく勢揃いします。(下記に一覧します)

onst codes = [
"100 111 010 ", // XOR結果 001
"111 010 110 ", // XOR結果 011
"010 110 001 ", // XOR結果 101
"110 001 011 ", // XOR結果 100
"001 011 101 ", // XOR結果 111
"011 101 100 ", // XOR結果 010
"101 100 111 ", // XOR結果 110
];

この結果は、よくわかりませんが、いわゆる魔円陣のバリエーションですね。

さて、上の一覧を、「放射能検査のために9人それぞれに割り当てる金貨の一覧(但し、0をガイガーカウンターではかる印とし、一覧にはないが全員がはかる金貨も１枚ある)」と見立てると……
ほんとに惜しいんです。
残りのひとりの10番目の技術者が検査すれば偽造金貨は見つかるのですけれど。

うーん残念。あとひとりをどうしても省力化したいのですが。

9人で嘘つきが確定2人の場合の手順は、以下です。

まず、
1人目と2人目：1,2,3,4
3人目と4人目：1,2,5,6
5人目と6人目：1,3,5,7
と測定します。

うち1回でも2人から不一致な報告された場合は、7人目と8人目にそれ（のうちの1つ）と同じ測定してもらいます。
不一致な報告が一度でもあったなら、2人が一致した報告は全て信頼できるので、これで
・上記3パターンの信頼できる結果が出揃っている
・上記3パターンのうち2パターンの信頼できる結果があり、9人目が正直者確定
のいずれかになっています。
前者はすでに偽物確定、後者は結果が得られていないものを9人目に頼めばいいです。

3組全てで一致する結果が報告された場合、例えば全て放射線検出されたと報告された場合は以下の4つの可能性があります。（他のパターンも番号が変わるだけで論理は同じ実質同じ）
・1が偽物で、残り3人に「確定で2人」嘘つきがいる
・2が偽物で、残り3人に嘘つきはいない
・3が偽物で、残り3人に嘘つきはいない
・5が偽物で、残り3人に嘘つきはいない
この場合、残り3人に、2と3と5をそれぞれ単体で調べてもらいます。
1人だけが放射線検出を報告した場合、その人の調べたコインが偽物です。（※）
2人が放射線検出を報告した場合、その2人が嘘つきで、1が偽物です。


嘘つきが「最大で2人」の場合、※のところで1が偽物で嘘つきが1人しかいなかった可能性が消し切れません。

DD++ さん、
すごいですね！！！

てっきりパリティビットが何らかの理由で不要になってしまった 9 ビットの符号なのかと予想しておりました。全符号の、符号全体のパリティが同一ならば、その 1 ビットは不要となりますので、それで稼いだのかと……

まさかの、頭の固い私には無理な発想です。
ご教示をありがとうございます。

数珠つなぎの件、中途半端な記述でしたので
精いっぱいきちんと投稿させていただきたく
文を練りました。以下です。

3 ビットのビット列が 7 つあり、それぞれを a, b, c, d, e, f, g と名付けます。この他に、3ビットのビット列が 1 つあり、これを z とします。
z = 000
とします。また、
a = 100
b = 111
c = 010
d = 110
e = 001
f = 011
g = 101
とします。

このとき以下の性質があります。(ここでは⊕を排他的論理和とします。)
e = a⊕b⊕c
f = b⊕c⊕d
g = c⊕d⊕e
a = d⊕e⊕f
b = e⊕f⊕g
c = f⊕g⊕a
d = g⊕a⊕b
《※サイクリックとなっています。》

3ビットのビット列 x のパリティをここでは p(x) と書くこととします。
ビット列の結合を∥で表します。たとえば
x = 011, y = 101 のとき
x∥y = 011101 となります。

e, f, g, a, b, c, d, z をエンコードして 10 ビットにしたものをそれぞれ、E, F, G, A, B, C, D, Z と名付けます。

さきほどのサイクリックな表をみながら、

E = a∥b∥c∥p(c)
F = b∥c∥d∥p(d)
G = c∥d∥e∥p(e)
A = d∥e∥f∥p(f)
B = e∥f∥g∥p(g)
C = f∥g∥a∥p(a)
D = g∥a∥b∥p(b)
Z = z∥z∥z∥p(z)
とします。

具体的には

E=100∥111∥010∥1 ←e=001
F=111∥010∥110∥0 ←f=011
G=010∥110∥001∥1 ←g=101
A=110∥001∥011∥0 ←a=100
B=001∥011∥101∥0 ←b=111
C=011∥101∥100∥1 ←c=010
D=101∥100∥111∥1 ←d=110
Z=000∥000∥000∥0 ←z=000
となります。

このようにサイクリックに作成した符号は、
最小ハミング距離が 5 となっています。

これで、不正確なガイガーカウンター報告の数が 0 から 2 までの間ならば、その誤りビットを訂正可能です。

他にも色々な作り方をしてはみたのですが、一番不思議な踊りを踊っているのが上記のものです。なぜうまくいくのかわからないので。タマタマなのかも？　しれません。

他の作り方のものも、近々、ご紹介させてください。

情報ビットが3ビットでコード長が10ビットのコードで、最小ハミング距離が5のコードであれば、2ビットまでの誤りを検出して訂正することができますが、そのようなコードとして、

0,0,0,0,0,0,0,0,0,0
1,0,0,1,1,0,0,1,1,1
0,1,0,1,0,1,0,1,1,0
1,1,0,0,1,1,0,0,0,1
0,0,1,1,0,0,1,1,0,1
1,0,1,0,1,0,1,0,1,0
0,1,1,0,0,1,1,0,1,1
1,1,1,1,1,1,1,1,0,0

というコードが考えられます。10人の技術者をA～Jとして、
技術者AとEは、1,3,5,7番の金貨を選択して測定、
技術者BとFは、2,3,6,7番の金貨を選択して測定、
技術者CとGは、4,5,6,7番の金貨を選択して測定、
技術者DとHは、1,2,4,7番の金貨を検出して測定、
技術者Iは1,2,5,6番の金貨を選択して測定、
技術者Jは1,3,4,6番の金貨を選択して測定することにして、
各技術者の陽性の報告を「1」、陰性の報告を「0」で表すと、
すべての報告が正しかったとすると、以下の8通りの組み合わせ
があって、それぞれが1～8番のいずれかが偽造品である場合
と対応します。

-|A,B,C,D,E,F,G,H,I,J
0|0,0,0,0,0,0,0,0,0,0 →8番が偽造品
1|1,0,0,1,1,0,0,1,1,1 →1番が偽造品
2|0,1,0,1,0,1,0,1,1,0 →2番が偽造品
3|1,1,0,0,1,1,0,0,0,1 →3番が偽造品
4|0,0,1,1,0,0,1,1,0,1 →4番が偽造品
5|1,0,1,0,1,0,1,0,1,0 →5番が偽造品
6|0,1,1,0,0,1,1,0,1,1 →6番が偽造品
7|1,1,1,1,1,1,1,1,0,0 →7番が偽造品

10人の技術者の報告のうち2人の報告が誤りである場合は、
10ビットのうち2ビットが誤りである場合に相当しますが、
上記の8状態は最小ハミング距離が5なのでいずれも5ビット
以上の差があり、2ビットの誤り、すなわち、2人の報告が
誤りである場合までは訂正することができます。

技術者が 10 → 21 人に増員されたときに、最大 5人 までの範囲で誤った報告をしてきても偽金貨を突き止めることができると判明しました。

"100 111 010 110 001 011 101",
"111 010 110 001 011 101 100",
"010 110 001 011 101 100 111",
"110 001 011 101 100 111 010",
"001 011 101 100 111 010 110",
"011 101 100 111 010 110 001",
"101 100 111 010 110 001 011",
"000 000 000 000 000 000 000",

Minimum Hamming Distance: 12

なお、上記では 21 中に、誤らない技術者が1人報告をロストしても大丈夫です。
1人ロストかつ２人誤り報告でも。
対称性が高いので。

別の言い方をすれば
技術者が 10 → 20 人に増員されたときに、最大 5人 までの範囲で誤った報告をしてきても偽金貨を突き止めることができます。
Minimum Hamming Distance: 11
となりますので。

元の問題からみると、
技術者が2倍に増えて
許容できる誤り報告数が2.5倍です。

こんなのをみるとやはり
9人の技術者(うち最大2名は嘘つき)
でもできるのでは？と変な予想をたててしまいたくなります。

情報ビットが3ビット、最小ハミング距離が7のコードで、最短なのはコード長が13ビットのコードで、以下のようなものでした。

A,B,C,D,E,F,G,H,I,J,K,L,M
-------------------------
0,0,0,0,0,0,0,0,0,0,0,0,0
1,0,0,1,1,0,1,0,0,1,1,0,1
0,1,0,1,0,1,0,1,0,1,0,1,1
1,1,0,0,1,1,1,1,0,0,1,1,0
0,0,1,0,1,1,0,0,1,0,1,1,1
1,0,1,1,0,1,1,0,1,1,0,1,0
0,1,1,1,1,0,0,1,1,1,1,0,0
1,1,1,0,0,0,1,1,1,0,0,0,1

13人の技術者をA～Mとして、
技術者AとGは、1,3,5,7番の金貨を選択して測定、
技術者BとHは、2,3,6,7番の金貨を選択して測定、
技術者CとIは、4,5,6,7番の金貨を選択して測定、
技術者DとJは、1,2,5,6番の金貨を選択して測定、
技術者EとKは、1,3,4,6番の金貨を選択して測定、
技術者FとLは、2,3,4,5番の金貨を選択して測定、
技術者Mは、1,2,4,7番の金貨を検出して測定することにすれば、
最大で3人までが誤りの報告をしても8枚の金貨から1枚の偽造品を特定できます。

また、情報ビットが3ビット、最小ハミング距離が9のコードで、最短なのはコード長が17ビットのコードで、以下のようなものでした。

A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q
---------------------------------
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
1,0,0,1,0,0,1,0,0,1,1,1,0,1,1,1,0
0,1,0,0,1,0,0,1,0,1,1,0,1,1,1,0,1
1,1,0,1,1,0,1,1,0,0,0,1,1,0,0,1,1
0,0,1,0,0,1,0,0,1,1,0,1,1,1,0,1,1
1,0,1,1,0,1,1,0,1,0,1,0,1,0,1,0,1
0,1,1,0,1,1,0,1,1,0,1,1,0,0,1,1,0
1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0

17人の技術者をA～Qとして、
技術者AとDとGは、1,3,5,7番の金貨を選択して測定、
技術者BとEとHは、2,3,6,7番の金貨を選択して測定、
技術者CとFとIは、4,5,6,7番の金貨を選択して測定、
技術者JとNは、1,2,4,7番の金貨を検出して測定、
技術者KとOは、1,2,5,6番の金貨を選択して測定、
技術者LとPは、1,3,4,6番の金貨を選択して測定、
技術者MとQは、2,3,4,5番の金貨を選択して測定することにすれば、
最大で4人までが誤りの報告をしても8枚の金貨から1枚の偽造品を特定できます。

なお、情報ビットが3ビット、最小ハミング距離が3のコードで、最短なのはコード長が6ビットのコードで、以下のようなものでした。

A,B,C,D,E,F
-----------
0,0,0,0,0,0
1,0,0,1,1,0
0,1,0,1,0,1
1,1,0,0,1,1
0,0,1,0,1,1
1,0,1,1,0,1
0,1,1,1,1,0
1,1,1,0,0,0

6人の技術者をA～Fとして、
技術者Aは、1,3,5,7番の金貨を選択して測定、
技術者Bは、2,3,6,7番の金貨を選択して測定、
技術者Cは、4,5,6,7番の金貨を選択して測定、
技術者Dは、1,2,5,6番の金貨を選択して測定、
技術者Eは、1,3,4,6番の金貨を選択して測定、
技術者Fは、2,3,4,5番の金貨を選択して測定することにすれば、
1人までが誤りの報告をしても8枚の金貨から1枚の偽造品を特定できます。

DD++ さんがおっしゃっていた、
《10人ではなく9 人、うち2名は《必ず》嘘をつく》場合に解があることを私も確認しました。別解ですね。

9人の技術者を前半組6人、後半組3人にわけます。
前半では①と②と③とのどれかが発生します。どれが発生したかは我々にはわかります。
後半では、①②③ごとに、対処策があります。

・前半部
8枚の金貨を２枚づつペアにして計4ペアとします。(A,a), (B,b),(C ,c ),(D,d)と名付けます。あるいは(X,x)のようにまとめて書くこともあります。

６名の技術者に以下のように測定の指示を出します。1 のマークがついた金貨を測ります。

[
"0 0 0 0 0 0" ,//(A,a)
"0 0 1 1 1 1" ,//(B,b)
"1 1 0 0 1 1" ,//(C,c)
"1 1 1 1 0 0" ,//(D,d)
]

上はハミング距離が 4 なので
以下の3つのケースが結果として判明します。


①
陽性判定は偶数個である。
が、そのものズバリの判定結果が得られない。
すなわち、前半6人組に２人嘘つきがいる。
偽物の入った(X,x)はこの時点ではまったく不明。

②
陽性判定は偶数個である、かつ、
上の4ケースそれぞれのうちどれかひとつが
そのものズバリの結果となる。

このとき前半6人組に嘘つきがいない。
偽物の入った(X,x)が確定する。

③
陽性判定は奇数個である。
が、そのものズバリの判定結果が得られない。
すなわち、前半6人組に１人の嘘つきがいる。
この場合には嘘つきが特定できて、
偽物の入った(X,x)が確定する。

以上が前半部です。

次は後半部での対処。

①:
後半部3名の技術者が正直者なので、
８枚の金貨から１枚の偽金貨を見付けるには
二分木で捜索すればよい。
《目的終了》

②
偽物の入った(X,x)が確定している。
残りの３名の技術者のうち２名が嘘つきである。
３名にXが偽造か調べさせ、得られた結果を２対１で多数決をとり、その結果の判定を反転させたものが真の測定結果となる。
《目的終了》

③
偽物の入った(X,x)が確定している。
残りの３名の技術者のうち１名が嘘つきである。
３名にXが偽造か調べさせ、得られた結果を２対１で多数決をとり、その結果が真の測定結果となる。
《目的終了》

※以上が別解です.
後半部の多数決が効いてくるためにも、嘘つき２名は必ず嘘をつくことが必要となります。

=====

なお、揃って嘘をつくとは限らない場合に
9名で足りるかというお話しについては、
私は、かなり否定的に捉えるようになりました。
個人的には探索はおわります。

技術者を1人増やして11人にすると、偽造品1枚を含む16枚の金貨から、最大2人の誤りを含む報告を用いて特定することができます。

情報ビットが4ビット、最小ハミング距離が5のコードで、最短なのはコード長が11ビットの以下のコードで、これを用いると、

-|A,B,C,D,E,F,G,H,I,J,K
-----------------------
0|0,0,0,0,0,0,0,0,0,0,0→16番が偽造品
1|1,0,0,0,1,1,1,0,0,1,0→1番が偽造品
2|0,1,0,0,1,1,0,1,1,0,1→2番が偽造品
3|1,1,0,0,0,0,1,1,1,1,1→3番が偽造品
4|0,0,1,0,1,0,1,1,1,0,0→4番が偽造品
5|1,0,1,0,0,1,0,1,1,1,0→5番が偽造品
6|0,1,1,0,0,1,1,0,0,0,1→6番が偽造品
7|1,1,1,0,1,0,0,0,0,1,1→7番が偽造品
8|0,0,0,1,0,1,1,0,1,1,1→8番が偽造品
9|1,0,0,1,1,0,0,0,1,0,1→9番が偽造品
a|0,1,0,1,1,0,1,1,0,1,0→10番が偽造品
b|1,1,0,1,0,1,0,1,0,0,0→11番が偽造品
c|0,0,1,1,1,1,0,1,0,1,1→12番が偽造品
d|1,0,1,1,0,0,1,1,0,0,1→13番が偽造品
e|0,1,1,1,0,0,0,0,1,1,0→14番が偽造品
f|1,1,1,1,1,1,1,0,1,0,0→15番が偽造品

11人の技術者をA～Kとして、
技術者Aは、1,3,5,7,9,11,13,15番の金貨を選択して測定、
技術者Bは、2,3,6,7,10,11,14,15番の金貨を選択して測定、
技術者Cは、4,5,6,7,12,13,14,15番の金貨を選択して測定、
技術者Dは、8,9,10,11,12,13,14,15番の金貨を選択して測定、
技術者Eは、1,2,4,7,9,10,12,15番の金貨を検出して測定、
技術者Fは、1,2,5,6,8,11,12,15番の金貨を選択して測定、
技術者Gは、1,3,4,6,8,10,13,15番の金貨を選択して測定、
技術者Hは、2,3,4,5,10,11,12,13番の金貨を選択して測定、
技術者Iは、2,3,4,5,8,9,14,15番の金貨を選択して測定、
技術者Jは、1,3,5,7,8,10,12,14番の金貨を選択して測定、
技術者Kは、2,3,6,7,8,9,12,13番の金貨を検出して測定することにすれば、
最大で2人までが誤りの報告をしても16枚の金貨から1枚の偽造品を特定できます。

kuiperbeltさんによる[2151]のご投稿へのコメントです。
8 番から 15 番までは本物、という情報があらかじめ与えられていれば
技術者Dによる計測は不要となり、技術者の総人数は 10 人でよいこととなります。

すなわち
0番(=16番)から7番までの8枚の金貨から技術者10名で１枚の偽造金貨をみつける方法にもなっています。(最大2人まで嘘をつくこととして)

私の[2140]の投稿の続きです。
別解でして、恐ろしく形が憶えやすいものです。

情報ビットは 3 ビットとします。これを w と記します。
w について全てのビットを反転したものを W とします。
3 ビット分のデータのパリティ(1ビット)を求める関数を p(・)と書きます。
ビット列 x とビット列 y とを結合する記号を∥とします。

w をエンコードして 10 ビットのビット列を次のように作ります。

w∥w∥p(w)∥w ……ただしp(w)=0 のとき。
w∥w∥p(w)∥W ……ただしp(w)=1 のとき。

これが目的を果たします。
みつけたときには物凄くビックリしました。
なぜコレでうまくいくかというとゴニョゴニョです。

> なぜコレでうまくいくかというとゴニョゴニョです。

3ビットの w を１ビットづつに分解すると
w=w1∥w2∥w3
さきのエンコードは
w1∥w2∥w3∥w1∥w2∥w3∥w1+w2+w3∥w2+w3∥w1+w3∥w2+w3
トなっています。

※ただし加算記号は ビット毎の排他的論理和にて。。

このスレッドの趣旨からは脱線中です。

本日考えた[2154]への個人的な気づきです。

「コレ」でうまく行く？　という観察から実験数学的にあれこれやっておりました。

符号語の数が 16 で情報ビットが 4 、検査ビットが 3 、符号長が 7 、最小ハミング距離が 3 ゆえにビット反転誤りを 1 ビットまで訂正可能な、(7,4,3)ハミング符号は、よく知られていて世の中に実際に応用されている枯れた技術のようです。

これに対抗して！？

符号語の数が 16 で情報ビットが 4 、検査ビットが 10 、符号長が 14 、最小ハミング距離が 7 ゆえにビット反転誤りを 3 ビットまで訂正可能な、そのような符号をたった今みつけました。(車輪の再発明かも？)

情報ビットをそのままに、符号長が 7 から 14 と2倍になるのを生贄にして、
ビット反転誤りへの訂正能力を 1 ビットから 3 ビットへと、 3 倍にできるという。

通信路の状況が悪いときにはかなり有効なのでは？　と。

"0000 000000 0000",
"0001 001011 0111",
"0011 011110 1100",
"0010 010101 1011",
"0110 110011 0110",
"0111 111000 0001",
"0101 101101 1010",
"0100 100110 1101",
"1100 011110 0011",
"1101 010101 0100",
"1111 000000 1111",
"1110 001011 1000",
"1010 101101 0101",
"1011 100110 0010",
"1001 110011 1001",
"1000 111000 1110",

　16ビットめへの追加、末尾に全体へのパリティをつけるのも乙なものですが。

とにかく各ビットを怠けさせない、他のビットと相関させる、そんな作戦が良いのかもしれません。

DD++ さんが提起なさった
《技術者が 9 人でも大丈夫？》という問い
について何度も諦めようと努めたのですが
なかなか頭を離れず、もう思い切ってとことん考えてみようと試みました。

結果として、もしもひとつの【予想】が正しければ、 9 人の技術者(うち、嘘つきは 0 人から 2 人の可能性がある)でも、8枚中１枚の偽金貨を突き止められそうと考えつきました。

偽金貨をつきとめる段階として、第一段階と第二段階とに分けます。
第二段階では第一段階までの中間結果をみてから測定方法を都度考えることにします。
(なお二段階にわけずに一発でやろうとするならば技術者は10人必要だろうことはほぼ間違いないという感触を得ています。)

第一段階では、７人の技術者を使い
第二段階では、２人の技術者を使います。

第一段階終了時点で既に偽造金貨が確定済みならば第二段階は実行しません。この場合の発生条件は、７人中嘘つきが１人以下であることです。(必要十分条件)

第一段階終了時点で７名中嘘つきが２名いたと確定できれば、かつ、8枚中少なくとも4枚が本物であると確定できれば、残りの４枚について第二段階で正直者のみで構成された２名の技術者がうち１枚の偽金貨を確定できることでしょう。

第一段階のアルゴリズムになにが必要かをまとめなおします。
以下の３パターンのどれかが必ず発生するものとします。

①嘘つきがちょうど１人発生したことの検知確定と、同時に一枚の偽金貨の確定。
[第二段階不要]

②嘘つきがちょうど０人であることの検知確定と、同時に一枚の偽金貨の確定。
[第二段階不要]

③嘘つきがちょうど２人であることの検知確定と、同時に、本物の金貨(少なくとも)４枚の確定。偽金貨は残りもののなかにあると絞れる。
[第二段階では２人の正直者が残りものから偽金貨をつきとめることになりますがそれは十分に可能であることでしょう。]

上のようなアルゴリズムがみつかれば、10人ならず9人でも偽金貨を確定できることとなります。

①〜③までで、もっとも難解なのが③が発生するケースです。

私は次のようなものをとりあえず考えてみました。

(長くなったので次に投稿します。)

第一段階の設計について。

８枚の硬貨にたいして７名の技術者が以下のリストにあるように測定します。
(1 )はガイガーカウンターで測ります。

"0 0 0 0 0 0 0",
"0 0 1 0 1 1 1",
"1 0 0 1 0 1 1",
"1 1 0 0 1 0 1",
"1 1 1 0 0 1 0",
"0 1 1 1 0 0 1",
"1 0 1 1 1 0 0",
"0 1 0 1 1 1 0",

ケース①
７つの測定結果が得られた時
陽性(1)が、奇数個、得られたケースです。
このとき、７名中に嘘つきは必ず１名です。
上のテーブルでは最小ハミング距離が４なので嘘つきも確定し偽金貨も確定します。
第二段階は不要です。

ケース②
７つの測定結果が得られた時　
陽性(1)が、偶数個、得られ、かつ、
上のテーブルと一致したケースです。
このとき、７名中に嘘つきはいません。
偽金貨も確定します。
第二段階は不要です。

ケース③
７つの測定結果が得られた時　
陽性(1)が、偶数個、得られ、かつ、
上のテーブルと【一致しない】ケースです。
このとき、７名中の嘘つきは必ず２名です。

偽金貨は確定しません。
２名の正直者が待っている第二段階が必要です。

=====

ここで実験的にかなりやり込んでみたのですが (手動)
偽測定値を２個含む７個のデータを得られたときに、
偽金貨の候補は《いつも》３枚なのです。
ということは第二段階で偽金貨が確定できることとなります。

以下が私の【予想】です。

偽測定値を２個含む７個のデータを得られたときに、
偽金貨の候補は《いつも》３枚です。

============

上記の予想に反例があったり、証明があるようでしたならば、是非とも、ご教示をください。

気になって気になって仕方がありません。
ぽんつくな私のことですから
ボーンヘッドがあるかも(恥ずかしい)ですけれども。

皆様、何卒ご教示を賜りたく、宜しくお願い申し上げます。

※証明の見通しがよくなるかどうかわかりませんが上記のテーブルは巡回的に作ってあります。

なるほど、カークマンの組分け問題の解を利用すれば確かにいけますね。

証明は、陽性報告の人数ごとに場合分けをすれば容易かと思います。

いかがでしょう？

DD++ さん。
早速のコメントおよびヒントを有難うございます。

陽性報告の人数で場合分け……ですか……
やってみます。

ご指摘どおりカークマンでしたね……
自分としてはファノ平面を使ったつもりでした。(0のポジション)

AI と BC の交点を D とすると、
BD : CD = BA : AC = √50 : √80 = √5 : 2√2 = (-5+2√10) : (8-2√10)

よって、
D ( (38-2√10)/3, (43-10√10)/3 )
より
AI : ID = AB : BD = √50 : (-5+8√10)√26/3

あとはこれを内分点の公式につっこんで整理すればいいはず……ですが、数字が大きくなりすぎるのでギブアップ。

A(a,b),B(c,d),C(e,f)とすると
直線ABは (d-b)x-(c-a)y-(ad-bc)=0
直線BCは (f-d)x-(e-c)y-(cf-de)=0
直線CAは (b-f)x-(a-e)y-(eb-fa)=0
直線ABからk離れた直線は (d-b)x-(c-a)y-(ad-bc)-k√{(d-b)^2+(c-a)^2}=0 … (1)
直線BCからk離れた直線は (f-d)x-(e-c)y-(cf-de)-k√{(f-d)^2+(e-c)^2}=0 … (2)
直線CAからk離れた直線は (b-f)x-(a-e)y-(eb-fa)-k√{(b-f)^2+(a-e)^2}=0 … (3)
(1)(2)からkを消去して
{(f-d)√{(d-b)^2+(c-a)^2}-(d-b)√{(f-d)^2+(e-c)^2}}x
-{(e-c)√{(d-b)^2+(c-a)^2}-(c-a)√{(f-d)^2+(e-c)^2}}y
=(cf-de)√{(d-b)^2+(c-a)^2}-(ad-bc)√{(f-d)^2+(e-c)^2} … (4)
(2)(3)からkを消去して
{(b-f)√{(f-d)^2+(e-c)^2}-(f-d)√{(b-f)^2+(a-e)^2}}x
-{(a-e)√{(f-d)^2+(e-c)^2}-(e-c)√{(b-f)^2+(a-e)^2}}y
=(eb-fa)√{(f-d)^2+(e-c)^2}-(cf-de)√{(b-f)^2+(a-e)^2} … (5)
(4)(5)からyを消去して整理すると
x={a√{(f-d)^2+(e-c)^2}+c√{(b-f)^2+(a-e)^2}+e√{(d-b)^2+(c-a)^2}}
/{√{(f-d)^2+(e-c)^2}+√{(b-f)^2+(a-e)^2}+√{(d-b)^2+(c-a)^2}}
(4)(5)からxを消去して整理すると
y={b√{(f-d)^2+(e-c)^2}+d√{(b-f)^2+(a-e)^2}+f√{(d-b)^2+(c-a)^2}}
/{√{(f-d)^2+(e-c)^2}+√{(b-f)^2+(a-e)^2}+√{(d-b)^2+(c-a)^2}}}
よってA(a,b),B(c,d),C(e,f)を頂点とする内心の座標は
(
{a√{(f-d)^2+(e-c)^2}+c√{(b-f)^2+(a-e)^2}+e√{(d-b)^2+(c-a)^2}}
/{√{(f-d)^2+(e-c)^2}+√{(b-f)^2+(a-e)^2}+√{(d-b)^2+(c-a)^2}}
,
{b√{(f-d)^2+(e-c)^2}+d√{(b-f)^2+(a-e)^2}+f√{(d-b)^2+(c-a)^2}}
/{√{(f-d)^2+(e-c)^2}+√{(b-f)^2+(a-e)^2}+√{(d-b)^2+(c-a)^2}}}
)
見やすいように
√{(f-d)^2+(e-c)^2}=BC, √{(b-f)^2+(a-e)^2}=CA, √{(d-b)^2+(c-a)^2}=AB
と書けば、内心の座標は
((aBC+cCA+eAB)/(BC+CA+AB),(bBC+dCA+fAB)/(BC+CA+AB))

A(3,2),B(10,1),C(11,6)の場合は
BC=√{(6-1)^2+(11-10)^2}=√26
CA=√{(2-6)^2+(3-11)^2}=4√5
AB=√{(1-2)^2+(10-3)^2}=5√2
なので、内心の座標は
((3√26+40√5+55√2)/(√26+4√5+5√2),(2√26+4√5+30√2)/(√26+4√5+5√2))
=
((124+25√10-10√13-√130)/18,(76-5√10+20√13-7√130)/18)
※有理化にはWolframAlphaを使いました。

D ( (38-2√10)/3, (43-10√10)/3 )
は
D( (25+2√10)/3.(10√10-22)/3 )
に
AI : ID = AB : BD = √50 : (-5+8√10)√26/3
は
AI : ID = AB : BD = √50 : (-5+2√10)√26/3
となりませんか？

> ((124+25√10-10√13-√130)/18,(76-5√10+20√13-7√130)/18)
> ※有理化にはWolframAlphaを使いました。

方法は異なりますが最終結果は同じになっています。
(コンピュータで数値だけ求めたい時はこの式を利用していました。)
有理化もコツコツ進めて行きました。（すごく面倒でした。)

> D( (25+2√10)/3.(10√10-22)/3 )
> AI : ID = AB : BD = √50 : (-5+2√10)√26/3
> となりませんか？

そうかもしれません。
内分比をうっかり逆にしてたかも？
なんにせよ、この計算は暗算でやるもんじゃないですね……。

(b*i+c*j+d*k)^2=-(b^2+c^2+d^2)+(b*c-c*b)*k+(c*d-d*c)*i+(d*b-b*d)*j=-(b^2+c^2+d^2)
なので、b^2+c^2+d^2=1となるb*i+c*j+d*kがx^2+1=0の解になります。

ありがとうございます。
a+bi+cj+dk の中で、a=0 ならば、任意のb,c,dに対して
ｘ＝（bi+cj+dk）/√（b^2+c^2+d^2）x^2=-1
a＝０でない場合は、無いみたいですね。

あ、時計がずれてたのか9時9分投稿に失敗した……。


一応、例示も置いときます。

例1：602214076 は、1 未満の数字が 2 回、2 未満の数字が 3 回、3 未満の数字が 5 回、4 未満の数字が 5 回、5 未満の数字が 6 回、6 未満の数字が 6 回、7 未満の数字が 8 回、8 未満の数字が 9 回、9 未満の数字が 9 回、登場するので条件を満たす。

例2：299792458 は、1 未満の数字が 0 回だったり、7 未満の数字が 4 回だったり、偽になる命題が存在するので条件を満たさない。

例3：101325 は、9 桁表示の 000101325 で個数をカウントするので、条件を満たす。

99,999,999(個)でしょうか？

1～10 では9(個)
1～10^2 では80
1～10^3 では700
1～10^4 では6,000
1～10^5 では50,000
1～10^6 では400,000
1～10^7 では3,000,000
1～10^8 では20,000,000
1*10^8+1～2*10^8では 15,217,031
2*10^8+1～3*10^8では 13,119,879
3*18^8+1～4*10^8では 11,708,091
4*10^8+1～5*10^8では 10,546,875
5*10^8+1～6*10^8では 9,453,125
6*10^8+1～7*10^8では 8,291,909
7*10^8+1～8*10^8では 6,880,121
8*10^8+1～9*10^8では 4,782,968
9*10^8+1～10^9-1では 0
よって
10^8+1～10^9-1では79,999,999
以上から
1～999,999,999で条件を満たすものは20,000,000+79,999,999=99,999,999(個)
の模様です。

正しく9に纏わるDD++さんらしい問題でした。

正解です、お見事！
問題も正解も投稿日時もキューだらけの問題でした。

きっとスマートな解法があるのでしょうが、思いつかないので力技です。



n ≧ m ≧ 1 とする。
0, 1, ..., m の m+1 種類の数を重複を許して一列に n 個並べるとき、
1 ≦ q ≦ m となる任意の整数 q について q 未満の数を q 個以上含むような並べ方の数を f(m,n) とおく。

[1] m = 1 のとき
条件を満たさないものは並べる数のすべてが "1" となる場合の 1 通りなので、
f(1,n) = 2^n - 1
となる。

[2] m ≧ 2 のとき
並べる数のなかの "m" の個数を k 個として k で場合分けする。
k > n-m の場合は m 未満の数が m 個未満となってしまうため、条件を満たさない。
0 ≦ k ≦ n-m の場合、数 "m" の配置方法が nCk 通りあり、その各々に対して残りの数の並べ方が f(m-1,n-k) 通りある。
よって、
f(m,n) = Σ[k=0,...,n-m] nCk * f(m-1,n-k)
となる。

[1],[2]を用いて順次計算していくと次のようになる。

f(1,1) = 1
f(1,2) = 3
f(1,3) = 7
f(1,4) = 15
f(1,5) = 31
f(1,6) = 63
f(1,7) = 127
f(1,8) = 255
f(1,9) = 511

f(2,2) = 3
f(2,3) = 16
f(2,4) = 61
f(2,5) = 206
f(2,6) = 659
f(2,7) = 2052
f(2,8) = 6297
f(2,9) = 19162

f(3,3) = 16
f(3,4) = 125
f(3,5) = 671
f(3,6) = 3130
f(3,7) = 13686
f(3,8) = 57867
f(3,9) = 240049

f(4,4) = 125
f(4,5) = 1296
f(4,6) = 9031
f(4,7) = 54062
f(4,8) = 301321
f(4,9) = 1616764

f(5,5) = 1296
f(5,6) = 16807
f(5,7) = 144495
f(5,8) = 1059261
f(5,9) = 7196785

f(6,6) = 16807
f(6,7) = 262144
f(6,8) = 2685817
f(6,9) = 23343742

f(7,7) = 262144
f(7,8) = 4782969
f(7,9) = 56953279

f(8,8) = 4782969
f(8,9) = 100000000

f(9,9) = 100000000


求めるものは、 m = 9, n = 9 の場合の数から並べる数のすべてが "0" となる 1 通りを除いたものなので、
f(9,9)-1 = 99999999
通りとなる。



計算結果を見ると、
f(m,m) = (m+1)^(m-1)
になるみたいですね。

なるほど、そういうこともできるんですね。
結論にスパッと切り込む方法としては、
(314159265, 425260376, 536371487, ……, 203048154)
のように数字を 1 つずつずらした数からなる 10 個組を作ると、9 個の命題のうち何個満たされるかが全て異なることを証明することでしょうか。

そうすれば 999,999,999 個のうちゾロ目を除いた 999,999,990 個中 10 個に 1 個が条件を満たすことから 99,999,999 個であるとすぐにわかります。

まあ、満たされる命題数が全て異なることの証明が手間になるわけですけども。

りらひいさんの漸化式が面白かったので、これでいろいろ遊んでいたら
OEISでA373086がたまたまヒットした。
ここにリンクで張られた論文が関連するように思われるんですが、自分にはわからない部分が
多くて手ごわくて、りらひいさんならよく理解されるのではないかと思いました。

確かに、そうやってもよかったですね。

Dengan kesaktian Indukmuさん
ご返信ありがとうございます。
>P を 4 で割ったときの余りが 3 のときは大丈夫ですか？
Pを４で割った余りが１でないと、今のところ計算出来ません。

あっすみません、
勘違いして自明な質問をしてしまっていたため削除したところなのでした。
お詫びいたします。

Dengan kesaktian Indukmuさん
了解いたしました
また、ご質問等あればお待ちしております。^v^

お試しですが。

条件【※ただしaは3以上の奇数、bは(2×(aの桁数)＋1)桁以上の偶数】での、桁数の縛りについては確かめておりませんけれども、奇数^2 +偶数^2 であることを個人的には確かめた気持ちになっている以下のPをお願いします。下記のPについては素因数分解の結果を知っております。

P = 10^110 +1
桁数のオーダーが甘くてすみません。

Dengan kesaktian Indukmuさん
>P = 10^110 +1
P=(10^55)^2+1^2
= 89 × 101 × 661 × 3541 × 18041 × 27961 × 148721 × 1052788969 × 1056689261 × 1121407321 × 1395900370 916327245555441901 × 36380545029953205956377406702261
ですかね（素因数分解は他力で行いましたw）

aがn桁、bが2n+1桁以上ならば
10^(n-1)≦a＜10^n, b≧10^(2n)
となり
(b+1)^2-(b^2+a^2)=2b+1-a^2＞2・10^(2n)+1-10^(2n)=10^(2n)+1＞0
から
(b+1)^2＞a^2+b^2＞b^2
なので
b=[√P]　（[　]はガウス記号）
でbが求まりますね。
上記はa,bの偶奇と関係ありませんので、
「bが(2×(aの桁数)+1)桁以上」という条件さえあれば、
a,bの偶奇にかかわらず求められると思います。

らすかるさん
ご返信ありがとうございます
さすらすです！
（流石らすかるさんの略w）

私の場合aから求める方法を試していたので
ご指摘には目から鱗です
ありがとうございます。

[2114] で私が依拠したのは以下の定理なのでした。


合成数が高々二個の平方数の和で表されるための必要十分条件は、4を法として3に合同な素因数が全て平方（冪指数が偶数）になっていることである。


素因数分解して上を確認できる大きな数を探したのです。
そうしたら自明なものになってしまっていました。申し訳ないことです。

Dengan kesaktian Indukmuさん
了解いたしました。

らすかるさんの方法を応用して
桁数差を減らす事は可能でしょうか
例えば
「bが(2×(aの桁数))桁以上」
「bが(2×(aの桁数)-1)桁以上」
等a,bの桁数差を減らす事は可能でしょうか。

なぜ十進数で桁数を？
と初見で感じました。
私も期待しています。

上に書いた方法は要は(b+1)^2-(b^2+a^2)=2b+1-a^2＞0であれば良いので
a^2＜2b+1すなわちa^2≦2bであればb=[√P]が成り立ちます。
bが2n桁でも良いようにするためには、例えばb+1をb+5に変えると
(b+5)^2-(b^2+a^2)=10b+25-a^2＞0すなわちa^2＜10b+25
→b＜√P＜b+5すなわち[√P]-5＜b≦[√P]
つまりbは[√P],[√P]-1,[√P]-2,[√P]-3,[√P]-4のどれかなので
この5個で計算してみればbが2n桁の場合も対応できるようになります。
同様に[√P]～[√P]-49の50個で計算すればbが2n-1桁でもOK、
[√P]～[√P]-499の500個で計算すればbが2n-2桁でもOKのようになりますが、
巨大数でbを(定数)桁縮めたところであまり意味はないような気がします。

らすかるさん
詳しい解説有難うございます
やはり難しい事を再確認いたしました
自分なりにまた考えてみたいと思います
ありがとうございました。

2544通りですか？

正解です。

X,Y,Z,Wの銘柄を1回ずつ飲むと100+200+300+400=1000円で、残りの500円を分配する方法は、
XW,YZ,XXZ,XYY,XXXY,XXXXXの6つの場合があり、
XYZWとXWの場合、6!/(2!*1!*1!*2!)=180通り
XYZWとYZの場合、6!/(1!*2!*2!*1!)=180通り
XYZWとXXZの場合、7!/(3!*1!*2!*1!)=420通り
XYZWとXYYの場合、7!/(2!*3!*1!*1!)=420通り
XYZWとXXXYの場合、8!/(4!*2!*1!*1!)=840通り
XYZWとXXXXXの場合、9!/(6!*1!*1!*1!)=504通り
より、合計180+180+420+420+840+504=2544通り

これを一般化して
n(円)の資金をもって
毎日単価が1,2,3,･･･,k (円) ただしk<n
の各ビールの銘柄をどれか一つずつ毎日飲んでいき
資金を使い果たしたとき、少なくとも全銘柄のビールは飲んだことが起こる
お金の使い方の方法は総計どれだけ？
これを明示式で示せるか？
またはこれを読み取れる母関数は作れるのか？
ちなみに
k=2のとき
gf=1+1/(1-x-x^2)-1/(1-x)-1/(1-x^2)
k=3のとき
gf= x^6/(1-x-x^2-x^3)*(1/((1-x)*(1-x-x^2))+1/((1-x^2)*(1-x-x^2))+1/((1-x)*(1-x-x^3))+1/((1-x^3)*(1-x-x^3))+1/((1-x^2)*(1-x^2-x^3))+1/((1-x^3)*(1-x^2-x^3)))

k=4のときの母関数は如何に？
どなたかヒントを

>n(円)の資金をもって
>毎日単価が1,2,3,･･･,k (円) ただしk<n
>の各ビールの銘柄をどれか一つずつ毎日飲んでいき
>資金を使い果たしたとき、少なくとも全銘柄のビールは飲んだことが起こる
>お金の使い方の方法は総計どれだけ？
>これを明示式で示せるか？

お金の使い方の総数をa(n)とすると、a(n)は次の式で計算できます。
a(n)=[x^n](∫_[z=0,∞]exp(-z)*Π[j=1～k](exp(x^j*z)-1)dz)．

例えばk=4の場合：
exp(-z)*Π[j=1～4](exp(x^j*z)-1)を展開すると、次のようになります。
exp(-z)*Π[j=1～4](exp(x^j*z)-1)
=exp(-z)*(exp(x*z)-1)*(exp(x^2*z)-1)*(exp(x^3*z)-1)*(exp(x^4*z)-1)
=exp((-1+x+x^2+x^3+x^4)*z)
-exp((-1+x+x^2+x^3)*z)-exp(-1+x+x^2+x^4)-exp(-1+x+x^3+x^4)-exp(-1x^2+x^3+x^4)
+exp((-1+x+x^2)*z)+exp((-1+x+x^3)*z)+exp((-1+x+x^4)*z)+exp((-1+x^2+x^3)*z)+exp((-1+x^2+x^4)*z)+exp((-1+x^3+x^4)*z)
-exp((-1+x)*z)-exp((-1+x^2)*z)-exp((-1+x^3)*z)-exp((-1+4)*z)
+exp((-1)*z).

この展開式をz=0～∞の範囲で積分すればxの有理関数が得られます。
その有理関数をマクローリン展開したときのx^nの係数がa(n)です。
a(n)
=[x^n](-1/(-1+x+x^2+x^3+x^4)
+1/(-1+x+x^2+x^3)+1/(-1+x+x^2+x^4)+1/(-1+x+x^3+x^4)+1/(-1+x^2+x^3+x^4)
-1/(-1+x+x^2)-1/(-1+x+x^3)-1/(-1+x+x^4)-1/(-1+x^2+x^3)-1/(-1+x^2+x^4)-1/(-1+x^3+x^4)
+1/(-1+x)+1/(-1+x^2)+1/(-1+x^3)+1/(-1+x^4)
-1/(-1)).

atさん凄いです。
仕方なくn=10から20までの数値をひとつずつ算出して（御蔭で結果的に１ヵ所計算ミスを起こしていることを発見)
k=3での母関数を真似して色々試していたんですがそのすべてが弾かれてしまい、途方に暮れていました。
最初の項だけが一致しているが後は無駄な努力でした。
積分の力で解決されるとは思ってもない道筋でした。
最終型は集合の要素の個数を求める式に類似していますね。（結構覚え易い)
ということはk=3での母関数gfはよりスッキリした
1/(1-x-x^2-x^3)-1/(1-x-x^2)-1/(1-x-x^3)-1/(1-x^2-x^3)+1/(1-x)+1/(1-x^2)+1/(1-x^3)-1
でも可能というわけですね。

世の中には物事の本質を見事に掴んでしまう人がいることに感激です。
目から鱗でこんな一般式まで分かってしまうことが驚異でうれしいです。
大変ありがとうございました。
母関数の形にしなくてもコンピュータで数値だけ求めたいなら直接積分型から
gp > F(k)=intnum(z=0,[oo,1],exp(-z)*prod(j=1,k,exp(x^j*z)-1))
で定義しておけばk=9での値は
gp > for(n=45,60,print(n";"round(polcoeff(F(9),n))))
45;362880
46;1814400
47;8467200
48;31752000
49;110255040
50;352416960
51;1073580480
52;3125969280
53;8808347520
54;24105906720
55;64431521280
56;168662148480
57;433730626560
58;1097903933280
59;2740858737120
60;6757827995520
等で一発で求まっていくのですね。（あのめんどくさい作業が夢のようです。)

毎日単価が1円か2円の各ビールの銘柄をどれか一つずつ毎日飲むときの場合の数の生成関数については、

1+(x+x^2)+(x+x^2)^2+…=1/(1-x-x^2)

で表され、少なくとも両銘柄のビールを飲んだときの場合の数の生成関数については、

(1+(x+x^2)+(x+x^2)^2+…)-(1+x+x^2+…)-(1+x^2+x^4+…)+1
=1/(1-x-x^2)-1/(1-x)-1/(1-x^2)+1

で表されます。

(x+x^2)^m=C(m,0)x^m+C(m,1)x^(m+1)+...+C(m,j)x^(m+j)+...+C(m,m)x^(2m)

なので、n(円)の資金をもって毎日単価が1円か2円の各ビールの銘柄をどれか一つずつ毎日飲んでいき
資金を使い果たしたときのお金の使い方の方法の数は、

Σ_{k=0～floor(n/2)}C(n-k,k)

で表され、少なくとも両銘柄のビールを飲んだときの場合の数については、

n=2q+1のとき
Σ_{k=0～floor(n/2)}C(n-k,k) - C(n,0)

n=2qのとき
Σ_{k=0～floor(n/2)}C(n-k,k) - C(n,0) -C(q,q)

となります。F(n)=Σ_{k=0～floor(n/2)}C(n-k,k)とすると、
F(1)=1,F(2)=2,F(n)=F(n-1)+F(n-2)
となって、F(n)はフィボナッチ数列となります。少なくとも両銘柄のビールを飲んだときの場合の数については、
n=2q+1のときF(n)-1、n=2qのときF(n)-2となります。

毎日単価が1円,2円,3円の各ビールの銘柄をどれか一つずつ毎日飲むときの場合の数の生成関数については、

1+(x+x^2+x^3)+(x+x^2+x^3)^2+…=1/(1-x-x^2-x^3)

で表され、少なくとも全銘柄のビールを飲んだときの場合の数の生成関数については、

(1+(x+x^2+x^3)+(x+x^2+x^3)^2+…)
-(1+(x+x^2)+(x+x^2)^2+…)-(1+(x+x^3)+(x+x^3)^2+…)-(1+(x^2+x^3)+(x^2+x^3)^2+…)
+(1+x+x^2+…)+(1+x^2+x^4+…)+(1+x^3+x^6+…)-1
=1/(1-x-x^2-x^3)-1/(1-x-x^2)-1/(1-x-x^3)-1/(1-x^2-x^3)+1/(1-x)+1/(1-x^2)+1/(1-x^3)-1

で表されます。

2項係数C(n,k)に倣って3項係数C(n,k1,k2)=n!/(k1!k2!(n-k1-k2)!)を用いると、

(x+x^2+x^3)^m=Σ_{k1≧0,k2≧0,k1+k2≦m}C(m,k1,k2)[x^(m-k1-k2)*x^(2*k1)*x^(3*k2)]

なので、n(円)の資金をもって毎日単価が1円,2円,3円の各ビールの銘柄をどれか一つずつ毎日飲んでいき
資金を使い果たしたときのお金の使い方の方法の数は、

T(n)=Σ_{i=0～floor(n/2),j=0～floor(n/3),i+j≦n}C(n-i-j,i,j)

で表され、T(1)=1,T(2)=2,T(3)=4,T(n)=T(n-1)+T(n-2)+T(n-3)というトリボナッチ数列となります。

n(円)の資金をもって毎日単価が1円か3円の各ビールの銘柄をどれか一つずつ毎日飲んでいき
資金を使い果たしたときのお金の使い方の方法の数については、

(x+x^3)^m=C(m,0)x^m+C(m,1)x^(m+2)+...+C(m,j)x^(m+2*j)+...+C(m,m)x^(3m)

より、

n=1のときC(1,0)
n=2のときC(2,0)
n=3のときC(3,0)+C(1,1)
n=4のときC(4,0)+C(2,1)
n=5のときC(5,0)+C(3,1)
n=6のときC(6,0)+C(4,1)+C(2,2)
n=7のときC(7,0)+C(5,1)+C(3,2)
n=8のときC(8,0)+C(6,1)+C(4,2)

となって、一般には、

Σ_{k=0～floor(n/3)}C(n-2*k,k)

で表され、Σ_{k=0～floor(n/3)}C(n-2*k,k)=G(n+1)とすると、
G(1)=1,G(2)=1,G(3)=2,G(n)=G(n-1)+G(n-3)となって、これはナラヤナ数列(Narayana sequence)といいます。

n(円)の資金をもって毎日単価が2円か3円の各ビールの銘柄をどれか一つずつ毎日飲んでいき
資金を使い果たしたときのお金の使い方の方法の数については、

(x^2+x^3)^m=C(m,0)x^2m+C(m,1)x^(2m+1)+...+C(m,j)x^(1m+j)+...+C(m,m)x^(3m)

より、

n=2のときC(1,0)
n=3のときC(1,1)
n=4のときC(2,0)
n=5のときC(2,1)
n=6のときC(3,0)+C(2,2)
n=7のときC(3,1)
n=8のときC(4,0)+C(3,2)
n=9のときC(4,1)+C(3,3)
n=10のときC(5,0)+C(4,2)
n=11のときC(5,1)+C(4,3)
n=12のときC(6,0)+C(5,2)+C(4,4)

となって、一般には、

Σ_{ceil(n/3)≦k≦floor(n/2)}C(k,n-2*k)

で表され、これをH(n)とすると、H(2)=1,H(3)=1,H(4)=1,H(n)=H(n-2)+H(n-3)
となって、これはパドヴァン数列(Padovan sequence)といいます。

n(円)の資金をもって毎日単価が1円,2円,3円の各ビールの銘柄をどれか一つずつ毎日飲んでいき
資金を使い果たしたとき、少なくとも全銘柄のビールを飲んだときのお金の使い方の方法の数については、

T(n)-F(n)-G(n)-H(n)+r(n)
r(n)=3(n mod 6=0),1(n mod 6=1,5),2(n mod 6=2,3,4)

となります。n=1～10で、

T(n) 1,2,4,7,13,24,44,81,149,274
F(n) 1,2,3,5, 8,13,21,34, 55, 89
G(n) 1,1,2,3, 4, 6, 9,13, 19, 28
H(n) 0,1,1,1, 2, 2, 3, 4, 5, 7

となりますが、T(n)-F(n)-G(n)-H(n)+r(n)は、n=1～10で、
0,0,0,0,0,6,12,32,72,152となります。

毎日単価が1円,2円,3円,4円の各ビールの銘柄をどれか一つずつ毎日飲むときの場合の数の生成関数については、

1+(x+x^2+x^3+x^4)+(x+x^2+x^3+x^4)^2+…=1/(1-x-x^2-x^3-x^4)

で表され、少なくとも全銘柄のビールを飲んだときの場合の数の生成関数については、

(1+(x+x^2+x^3+x^4)+(x+x^2+x^3+x^4)^2+…)
-(1+(x+x^2+x^3)+(x+x^2+x^3)^2+…)-(1+(x+x^2+x^4)+(x+x^2+x^4)^2+…)
-(1+(x+x^3+x^4)+(x+x^3+x^4)^2+…)-(1+(x^2+x^3+x^4)+(x^2+x^3+x^4)^2+…)
+(1+(x+x^2)+(x+x^2)^2+…)+(1+(x+x^3)+(x+x^3)^2+…)+(1+(x^2+x^3)+(x^2+x^3)^2+…)
+(1+(x+x^4)+(x+x^4)^2+…)+(1+(x^2+x^4)+(x^2+x^4)^2+…)+(1+(x^3+x^4)+(x^3+x^4)^2+…)
-(1+x+x^2+…)-(1+x^2+x^4+…)-(1+x^3+x^6+…)-(1+x^4+x^8+…)+1
=1/(1-x-x^2-x^3-x^4)
-1/(1-x-x^2-x^3)-1/(1-x-x^2-x^4)-1/(1-x-x^3-x^4)-1/(1-x^2-x^3-x^4)
+1/(1-x-x^2)+1/(1-x-x^3)+1/(1-x^2-x^3)+1/(1-x-x^4)+1/(1-x^2-x^4)+1/(1-x^3-x^4)
-1/(1-x)-1/(1-x^2)-1/(1-x^3)-1/(1-x^4)
+1

で表されます。

比べてみたらとても興味深かったです。↓↓↓

https://www.chart.co.jp/subject/sugaku/suken_tsushin/108/108-7.pdf