|
uchinyan |
|
なぁーんだ。原理的には簡単でした ^^/
ただ、証明は少し面倒になってしまいましたが、こんな感じかな。 30 枚のカードのうち、同じ数字のカードに注目してその一つの数字を a とし、それが x 枚、0 <= x <= 30、あるとします。 カードを、小さい順に並べます。そして、例えば、その小さい方から 15 枚がマサルさんに、残りがトモエさんにいった場合を考えます。 明らかに、こうした場合が、それぞれに配られたカードの和の差が最大になる場合です。 このとき、a のカードがトモエさんに x1 枚、マサルさんに x2 枚、15 >= x1, x2 >= 0、x1 + x2 = x になっているとします。 a は、片方にすべて配られているか、両方に配られているか、のいずれかです。 まず、a がすべてトモエさんに配られている場合を考えます。 このとき、明らかに 1 <= x <= 15 です。しかし、マサルさんのカードの最大の数字 b は a よりも小さくなっているので、 a - b >= 1 で、14 >= カードの和の差 >= (a - b) * x >= 1 * x = x で、1 <= x <= 14 です。 そこで、 少なくとも 1 枚、a とは異なる数字のカードがトモエさんにはあります。その最小を c とします。 c が a よりも大きい場合には、c > a > b なので、c - b >= 2 です。したがって、 14 >= カードの和の差 >= (a - b) * x + (c - b) * (15 - x) >= 1 * x + 2 * (15 - x) = 30 - x x >= 16 です。しかし、これは、1 <= x <= 14 に矛盾するので、ありえません。 c が a よりも小さい場合には、a > c > b 又は a > c = b となっていないといけません。 a > c > b の場合は、a - b >= 2, c - b >= 1 です。したがって、 14 >= カードの和の差 >= (a - b) * x + (c - b) * (15 - x) >= 2 * x + 1 * (15 - x) = 15 + x x <= - 1 です。しかし、これは、明らかに、ありえません。 a > c = b の場合は、a - b >= 1, c - b >= 0 です。したがって、 14 >= カードの和の差 >= (a - b) * x + (c - b) * (15 - x) >= 1 * x + 0 * (15 - x) = x です。ただ、これは、c = b なので、a 以外に等しい数字のカードがある場合で、しかもそれが両方に配られている場合です。 つまり、問題文の注釈の場合に相当し、両方に配られている場合の x が 14 よりも大きい場合には、 そちらを採用する必要があり、この段階では決定できません。 (この点が、ややこしいです．．．) 同様にして、a がすべてマサルさんに配られている場合も、同じことが分かります。 (トモエさんの最小のカードの数字を b、マサルさんの a 以外の最大のカードの数字を c として、 不等号の向きを入れ替える感じで証明できます。) 最後に、a が両方に配られている場合です。 このときは、1 <= x1, x2 <= 15 です。 ・x1 = x2 = 15 の場合：すべてのカードが a の場合で、カードの和の佐賀 14 になることはないので、題意を満たしません。 ・x1 = 15, 14 >= x2 >= 1 の場合： マサルさんの方に、a 以外の数字のカードが少なくとも 1 枚あります。トモエさんの方のカードは a だけです。 a は、マサルさんのカードの中では最大なので、それ以外の最大 b は a > b になります。そこで、a - b >= 1 です。 ここで、今 15 > x2 なので、差を考える際に、a は x2 だけ打ち消しトモエさんの方に 15 - x2 だけ残るので、 14 >= カードの和の差 >= (a - b) * (15 - x2) >= 1 * (15 - x2) = (15 + 15) - (x1 + x2) = 30 - x x >= 16 になります。この場合は、0 <= x <= 30 以外に条件はないので、これは題意を満たします。 ・14 >= x1 >= 1, x2 = 15 の場合： x1 = 15, 14 >= x2 の場合：で、トモエさんとマサルさんを入れ替えたような議論で、x >= 16 がいえます。 ・14 >= x1, x2 >= 1 の場合： トモエさん、マサルさんの両方に、a 以外の数字のカードが少なくとも 1 枚ずつあります。 しかも、a は、トモエさんのカードの中では最小、マサルさんのカードの中では最大なので、 トモエさんの方の a 以外の最小 c は c > a、マサルさんの方の a 以外の最大 b は a > b になります。 そこで、c - a >= 1, a - b >= 1, c - b >= 2 です。 ここで、今 x1 >= x2 とすると、差を考える際に、a は x2 だけ打ち消し、トモエさんの方に x1 - x2 だけ残るので、 14 >= カードの和の差 >= (a - b) * (x1 - x2) + (c - b) * (15 - x1) >= 1 * (x1 - x2) + 2 * (15 - x1) = 30 - x x >= 16 になります。x1 < x2 のときも同様で、 14 >= カードの和の差 >= (c - a) * (x2 - x1) + (c - b) * (15 - x2) >= 1 * (x2 - x1) + 2 * (15 - x2) = 30 - x x >= 16 です。この場合は、0 <= x <= 30 以外に条件はないので、これは題意を満たします。 結局、a が両方に配られる場合には、x >= 16 がいえます。 そこで、例の問題文の注釈のケースを考慮して、結局、最少枚数は、16 枚になります。 これが実現可能なのは、掲示板上の例から明らかです。 なお、この証明では、カードの数字が整数であることが重要です。 掲示板にあるように、整数の条件をはずせば、より最少の解の可能性があります。 |
|
ネコの住む家
7月6日（木） 18:59:22
MAIL:uchi@sco.bekkoame.ne.jp 27768 |