マンガでよめる痔のこと・薬のこと

先日、知人との日常会話から、ある数学の問題へと発展しました。どなたか、以下の様な問題の解き方及び数式を、ど素人にも分かり易い説明をつけて、教えて頂けないでしょうか?解ける問題なのかすら、正直分わからずに質問しております。宜しくお願い致します。

----------------------------------------------------
りんご一個:250円
みかん一個:120円
メロン一個:480円
イチゴ一個:50円

上記の果物を全種類最低一個ずづ買うものとし、2000円で必ず300円のおつりが出る組合せを求めよ。
----------------------------------------------------

このQ&Aに関連する最新のQ&A

A 回答 (6件)

思いっきり単純に説明すると、



何か数式に当てはめて効率よく解く方法を P とします。
一つ一つ組合せを考えるなどして解く方法を NP とします。
で、
NP=P なのか?(効率的な方法はあるけどまだ見つかっていないだけ)
NP≠P なのか?(効率的な方法は、存在しない)
という問題は、数学的に未解決の問題です。

もし解けたら、、
クレイ研究所から1億円の懸賞金がもらえます。
    • good
    • 0
この回答へのお礼

ご回答、有難うございます。非常に分かり易いです!頭の中のモヤモヤがすっきりしました。つまり、この手の問題は、数学的に効率良く解く数式(数字を当てはめれば、各組合せと○通りと言う様な解答が分かるる)の存在の有無が、現時点では分かっていない種類の問題と言う事なのですね。当初、私たちは単純な数学問題だと思ったのですが、考えれば考える程、簡単に解ける数式などあるのか?と疑問に思い、こちらで質問させて頂きました。かなりすっきりしました。有難うございます。

お礼日時:2009/11/14 20:12

#3です。



ある程度は数式を使うことで問題を単純化した方が、
抜け・漏れなく考えられると思います。

>(3) 5の倍数である項に注目していくと、さらに絞り込むことができます。
たとえば、x= 0, z= 0のときを考えます。
このとき、元の関係式は
12y + 5w = 80
となります。
5wも 80も 5の倍数ですから、12yも 5の倍数でなければなりません。
すると、0 ≦ y ≦ 6より y= 0または 5としかなりえないことがわかります。
それぞれの yに対して、最後の wが決定されます。

このことを数式で(試験の解答風に)表現すると次のようになります。
12y = 80 - 5w
12y = 5* (16 - w)

12と 5は互いに素であるから、yは 5の倍数でなければならない。
0 ≦ y ≦ 6より y= 0または 5
(以下省略)
    • good
    • 0
この回答へのお礼

追加のご説明、有難うございます。お陰様で、理解する事が出来ました。これ以上効率の高い数式(単純に数字を当てはめれば、各組合せと○通りと言う解答が得られる様な)は、#5の方がご回答されている様に、数学的に未解決の問題で、今現時点では存在するのか分からないと言う事の様ですね。

お礼日時:2009/11/14 19:57

まずは、1個ずつは買わなくてはいけないので・・・・


各1個で900円
1700円にするには残り800円です。
ぱっと思いつくのは、イチゴを16個でしょう。(800/50=16)
1(リンゴ1個、みかん1個、メロン1個、イチゴ17個)
そうすれば、イチゴ何個と他の果物何個で交換できるかを考えれば答えは出ます。
リンゴ1個とイチゴ5個は交換できるので、
2(リンゴ2個、みかん1個、メロン1個、イチゴ12個)
3(リンゴ3個、みかん1個、メロン1個、イチゴ7個)
4(リンゴ4個、みかん1個、メロン1個、イチゴ2個)
リンゴが5個だとイチゴ25なのでこれ以上は無理)
みかん5個とイチゴが12個も交換が出来るので、
5(リンゴ1個、みかん6個、メロン1個、イチゴ5個)
みかん10個だとイチゴが24個必要なので、これ以上は無理。
また、ここからリンゴとイチゴの交換も無理です。
一方でメロン1個とみかん4個の交換は可能なので、
6(リンゴ1個、みかん2個、メロン2個、イチゴ5個)
以上です。
以上、6通りになるはずです。
    • good
    • 0
この回答へのお礼

ご解答、有難うございます。私たちも、一つ一つ組合せを考えていけば、何となく解けそうな感じはしたのですが、もっと効率的な数式があるのではないか?と思い、色々と考えたのですが、見つからず、こちらで質問させて頂きました。ただ、#5の方のご回答をみて、効率の良い数式の存在自体が明らかでない種類の問題だと言う事で、今はかなり納得してます。

お礼日時:2009/11/14 20:03

各々1個ずつ買った後で、800円分をどう買うかということですね。


たとえば、りんご:x個、みかん:y個、メロン:z個、イチゴ:w個とすると、
250x + 120y + 480z + 50w = 800
25x + 12y + 48z + 5w = 80

x, y, z, wはともに 0以上の整数なので、
0 ≦ x ≦ 3(りんごだけを買ったとしても最大3個までしか買えない)
0 ≦ y ≦ 6(みかんだけ~)
0 ≦ z ≦ 1(メロンだけ~)
0 ≦ w ≦ 16(イチゴだけ~)

選択肢の少ないところから、場合分けをしていけば少しは効率的に組合せが出せると思います。
(1) z= 0の場合と z= 1の場合で場合分け
(2) さらに、x= 0, 1, 2, 3で場合分け
(3) 5の倍数である項に注目していくと、さらに絞り込むことができます。

この回答への補足

ご回答、有難うございます。まさに、この様な数式を使った求め方を探していました。(3)の5の倍数である項に注目していくと、さらに絞り込めるとの事ですが、この部分、もう少し分かり易くご説明頂けますでしょうか?また、もし、この数式よりさらに効率的に組合せを求める事が出来るものがあれば、併せてご教示頂けると幸いです。

補足日時:2009/11/14 11:32
    • good
    • 0

2000円で必ず300円のおつりだから1700円


全種類最低一個ずづ買うから900円
残りは800円
このくらいの組み合わせなら、一番安い50円16個で800円を作れるので、以下、50円15個、14個、13個、・・・と探していけば組み合わせは求まるのではないか。
メロン一個 480円 0  0 1 480 0  0  0  0
りんご一個 250円 0  0 0 0  1  250 2 500
みかん一個 120円 0  0 1 120 0  0  0  0
イチゴ一個 50円 16 800 4 200 11 550  6 300
         16 800 6 800 12 800  8 800

一般的な解法はわかりません。

この回答への補足

早速のご回答、有難うございます。申し訳ありません。私の質問の仕方が悪かった様です。800円分を買えば良い所までは、分かったのですが、最後の800円分の組合せの求め方で、一つ一つ組合せを考えるやり方ではなく、何か数式に当てはめて、この程度の規模であれば、全ての組合せが簡単に分かる方法はあるのでしょうか・・・。

補足日時:2009/11/14 11:22
    • good
    • 0

まず, 「2000円で必ず300円のおつりが出る」ということから, 金額を合計で 1700円にすればいいということになります. そして「全種類最低一個ずづ買う」ので, とりあえず全種類 1個ずつ買ってしまいます. これで 900円使うことになるので, 残り 700円分買えばいいことになります.


これにはいろいろな方法があります.
subset sum (部分和問題) かな.

この回答への補足

早速のご回答、有難うございます。申し訳ありません。私の質問の仕方が悪かった様です。700円分を買えば良い所までは、分かったのですが、最後の700円分の組合せの求め方で、一つ一つ組合せを考えるやり方ではなく、何か数式に当てはめて、この程度の規模であれば、全ての組合せが簡単に分かる方法はあるのでしょうか?和分和問題について調べてみた所、計算複雑性理論の問題の一つと言う事ですが、名前が示す様に複雑で、中身を完全に理解出来ませんでした。ただ、何となく私の質問がこれに当てはまる様には感じました(「ナップサック問題」に近いかと)。と言う事は、この様な問題は簡単に解ける問題ではない?と言う事なのでしょうか?

補足日時:2009/11/14 11:15
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング