先日、知人との日常会話から、ある数学の問題へと発展しました。どなたか、以下の様な問題の解き方及び数式を、ど素人にも分かり易い説明をつけて、教えて頂けないでしょうか?解ける問題なのかすら、正直分わからずに質問しております。宜しくお願い致します。
----------------------------------------------------
りんご一個:250円
みかん一個:120円
メロン一個:480円
イチゴ一個:50円
上記の果物を全種類最低一個ずづ買うものとし、2000円で必ず300円のおつりが出る組合せを求めよ。
----------------------------------------------------
No.6
- 回答日時:
#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
(以下省略)
追加のご説明、有難うございます。お陰様で、理解する事が出来ました。これ以上効率の高い数式(単純に数字を当てはめれば、各組合せと○通りと言う解答が得られる様な)は、#5の方がご回答されている様に、数学的に未解決の問題で、今現時点では存在するのか分からないと言う事の様ですね。
No.5ベストアンサー
- 回答日時:
思いっきり単純に説明すると、
何か数式に当てはめて効率よく解く方法を P とします。
一つ一つ組合せを考えるなどして解く方法を NP とします。
で、
NP=P なのか?(効率的な方法はあるけどまだ見つかっていないだけ)
NP≠P なのか?(効率的な方法は、存在しない)
という問題は、数学的に未解決の問題です。
もし解けたら、、
クレイ研究所から1億円の懸賞金がもらえます。
ご回答、有難うございます。非常に分かり易いです!頭の中のモヤモヤがすっきりしました。つまり、この手の問題は、数学的に効率良く解く数式(数字を当てはめれば、各組合せと○通りと言う様な解答が分かるる)の存在の有無が、現時点では分かっていない種類の問題と言う事なのですね。当初、私たちは単純な数学問題だと思ったのですが、考えれば考える程、簡単に解ける数式などあるのか?と疑問に思い、こちらで質問させて頂きました。かなりすっきりしました。有難うございます。
No.4
- 回答日時:
まずは、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通りになるはずです。
ご解答、有難うございます。私たちも、一つ一つ組合せを考えていけば、何となく解けそうな感じはしたのですが、もっと効率的な数式があるのではないか?と思い、色々と考えたのですが、見つからず、こちらで質問させて頂きました。ただ、#5の方のご回答をみて、効率の良い数式の存在自体が明らかでない種類の問題だと言う事で、今はかなり納得してます。
No.3
- 回答日時:
各々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:32No.2
- 回答日時:
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:22No.1
- 回答日時:
まず, 「2000円で必ず300円のおつりが出る」ということから, 金額を合計で 1700円にすればいいということになります. そして「全種類最低一個ずづ買う」ので, とりあえず全種類 1個ずつ買ってしまいます. これで 900円使うことになるので, 残り 700円分買えばいいことになります.
これにはいろいろな方法があります.
subset sum (部分和問題) かな.
この回答への補足
早速のご回答、有難うございます。申し訳ありません。私の質問の仕方が悪かった様です。700円分を買えば良い所までは、分かったのですが、最後の700円分の組合せの求め方で、一つ一つ組合せを考えるやり方ではなく、何か数式に当てはめて、この程度の規模であれば、全ての組合せが簡単に分かる方法はあるのでしょうか?和分和問題について調べてみた所、計算複雑性理論の問題の一つと言う事ですが、名前が示す様に複雑で、中身を完全に理解出来ませんでした。ただ、何となく私の質問がこれに当てはまる様には感じました(「ナップサック問題」に近いかと)。と言う事は、この様な問題は簡単に解ける問題ではない?と言う事なのでしょうか?
補足日時:2009/11/14 11:15お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 経済学 「政府支出乗算」の求め方を教えてください。 2 2022/11/20 19:52
- 分譲マンション マンション大規模修繕工事の資金不足 神奈川県の築37年総戸数36戸のマンションの管理組合理事長を今年 7 2022/09/03 19:55
- 生命保険 保険会社の勧めで、「外貨建ての生命保険」に入るか検討しております。利率は4.5%で、147円の場合、 5 2022/11/03 23:59
- 財務・会計・経理 【経費削減と利益の関係について】 4 2022/11/20 03:01
- 予備校・塾・家庭教師 【至急】塾講師の方、助けてください。 塾の問題集の答えが貰えません。 新中学二年生です。個人塾に通っ 1 2022/03/25 00:31
- 大学・短大 次の問題がわかりません。分かる方お願いいたします! A国における1日のうどんとそばの家計の消費量に関 4 2023/01/19 23:06
- その他(ビジネススキル・経営ノウハウ) 在庫管理のこの問題が分かりません。どなたか解説お願いします 2 2022/04/18 18:35
- 数学 在庫管理のこの問題が分かりません。どなたか解説お願いします 4 2022/04/18 22:19
- 数学 在庫管理のこの問題が分かりません。どなたか解説お願いします 2 2022/04/18 22:21
- 計算機科学 2500円の人と2000円の人の集計 2 2023/08/06 07:18
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
複数回答のアンケート結果をグ...
-
72の正の約数の個数を求めよ。 ...
-
excelで前年比を求める時、どち...
-
a6条+9a3条b3条+8b6条 の因数...
-
物理です。 このグラフで三角形...
-
この問題の色をつけた部分の面...
-
面積30㎠の長方形の縦の長さx㎝...
-
数IIの問題です。a>0、b>0...
-
弧と弦で囲まれた面積はいくか?
-
数学
-
因数分解です a^2+b^2+2bc+2ca+...
-
|ab|= abはなんで ab≧0になる...
-
この問題答えが20になるのです...
-
高校1年生数学の問題です。 1....
-
小6算数の問題について教えて...
-
一辺の長さがaの正八面体がある...
-
a二乗+b二乗+bc-ca-2abを因数...
-
体積 面積 質量 密度 は大きい...
-
平方の差ってなんですか
-
算数(中学受験)の表面積の求め方
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
複数回答のアンケート結果をグ...
-
8-√5 の整数部分と小数部分っ...
-
72の正の約数の個数を求めよ。 ...
-
平方根の応用問題
-
3変数関数の最大最小
-
群論の問題についてです。 実数...
-
公務員試験の問題
-
この数の整数部分と少数部分っ...
-
excelで前年比を求める時、どち...
-
数学
-
半径と面積がわかっている時の...
-
体積 面積 質量 密度 は大きい...
-
長さが24cmの針金を折り曲げて...
-
この図形の色を塗った部分の面...
-
色がついた部分の面積を求める...
-
このいろを塗った部分の面積の...
-
中学数学 辺に対して垂直な面の...
-
影をつけた部分の面積を求める...
-
何でも
-
算数 mの上に2がつくとなんて読...
おすすめ情報