ご祝儀の問題

質問

「結婚式のご祝儀は奇数」という話題から思いつきました
(数学カテゴリなので、この話の真偽は置いておいてください)。
また、[ ]でくくったのは添え字(数列に使う下付き文字)です。

結婚式にはN人の出席者があり、ご祝儀は
a[1]万円,a[2]万円,a[3]万円,…,a[N]万円とします(但しa[1]≦a[2]≦a[3]≦…≦a[N])。
仮に新郎と新婦が結婚式直後に不仲になった時は
ご祝儀袋にお金が入ったまま分配するとします。

このとき、全ての総和S[N]=a[1]+a[2]+a[3]+…+a[N]が奇数であれば
明らかに2分配することはできませんが、
例えばN=3で、a[1]=2,a[2]=3,a[3]=3のとき、和が偶数になっても
ご祝儀袋を開けなければ2分配できませんね。

つまり、a[1],a[2],a[3],…,a[N]のどの組み合わせも
和がS[N]/2と等しくないような整数列{a[n]}はどのような数列か教えてください。

また、もし可能でしたら
このような数列を作るために出席者たちは
互いにどのような申し合わせをすれば良いか
(結婚式なので金額を申し合わせるのは無しです)も教えてください。

回答No.2

SortaNerd_ · ベストアンサー

ある数列がそのような条件を満たすかを判定する問題は「分割問題」と呼ばれるようです。
その一般形である「部分和問題」についてWikipediaに書かれていました。
http://ja.wikipedia.org/wiki/%E9%83%A8%E5%88%86%E5%92%8C%E5%95%8F%E9%A1%8C
また、これをさらに一般化したものが「ナップサック問題」です。
これらは「NP困難」というクラスに属しています。分割問題と部分和問題についてはクラス「NP」にも属しており、これを「NP完全」と呼んだりします。
このNPやNP困難というものの説明は難しいのですが、大まかに説明すると「コンピューターを使っても(現実的な時間では)解けない」ようなものを示します。(正確に言うと、証明はされていないがまず間違いないと考えられている)

というわけで、
「～はどのような数列か」=「全ての数列について～を満たすかを判定せよ」の答えを求めることはコンピューターを使っても不可能であり、ましてやどのような数列かを式や文章で簡潔に書けるようなものではない。
というのがこの質問への答えになると思います。

なお、後半の「可能でしたら」の方は、問題自体不明確なので答えようがありません。
金額を申し合わせないといいますが、では何を申し合わせるのでしょう。具体的な金額は指定しないということかとも思いますが、何らかの形で金額に条件を付けることと具体的な金額を指定することの間に境は無いと思います。
例えば「素数にせよ」という指示と「2, 3, 5, 8, 13のいずれかにせよ」という指示と「3万円にせよ」という指示の間に何か違いはあるのでしょうか。

補足

回答ありがとうございます。
わからないのだということが、よくわかりました。

＞例えば「素数にせよ」という指示と「2, 3, 5, 8, 13のいずれかにせよ」という指示と
＞「3万円にせよ」という指示の間に何か違いはあるのでしょうか。
結婚式のご祝儀という前提を踏まえたためです。
友人どうしで「○○万円持っていく」と言っても
裏切ることはよくありますし経済状況もありますから
そういう約束自体を嫌うことはよくあると思います。

「Aは3で割り切れる数、Bは3で割ったら1余る数、Cは3で割ったら2余る数」とか
「結婚式の出席番号に書かれた数の約数のどれか」のような(たぶん条件を満たしませんが)
ものを想定していました。

回答No.1

saxan

お気づきとは思いますが
0<a[1]<a[2]=a[3]=…=a[N]ならOKですね。
他にも色々できるでしょうけど。

補足

回答ありがとうございます。
一般的ルールや過去の研究は無いでしょうか?