スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ここまでの結果

コインの問題のここまでの結果をちょっとまとめときます。

興味の無い人は、この記事の一番下にあるパズルを見てみてください。
それも興味なかったら、最近の写真でも(笑)


問題を手短に言うと、
どんな金額のコインが発行されてると効率がいいのか、って言うもの。

もっと厳密に言うと、
0セントから99セントまでの金額を払うとき、
(1)ちょうど払うために必要なコインの数が一番少ないのは、
どんなコインの組み合わせが発行されてる時か。
(2)お釣りを含めて、移動するコインの数が一番少ないのは、
どんなコインの組み合わせが発行されてる時か。

(これは過去記事のコメント欄を見てもらえると分かりますが、
「貪欲法」が使えるコインの組み合わせに限ります)


まず(1)、ちょうど払う場合の結果から。

(1a)コイン2種類の場合

ベストの組み合わせは、{1、10}

0セントから99セントまでをちょうど払うのに、平均9枚必要です。

(1b)コイン3種類の場合

{1、5、22}{1、5、23}
平均5.26枚

(1c)コイン4種類の場合

{1、3、11、37}{1、3、11、38}
平均4.1枚


ちなみに、アメリカの{1、5、10、25}だと、平均4.7枚。
日本の{1、5、10、50}だと、平均5枚かかります。

kashさんが3種類で提案した{1、7、13}は6.54枚、{1、8、13}は5.48枚。
4種類の{1、3、7、24}は4.28枚でした。


次に(2)、お釣りを含めた場合の結果。

(2a)コイン2種類の場合

ベストの組み合わせは{1、13}

0セントから99セントまで払ったとき、
払う枚数とお釣りで返ってくる枚数の合計が、平均4.8枚です。

(2b)コイン3種類の場合

{1、8、29}
平均3.09枚

(2c)コイン4種類の場合

{1、4、10、37}
平均2.52枚


これはアメリカだと平均3枚、日本だと平均3.15枚です。

コイン3種類の答えの{1、8、29}は、
実はピッタリ払うのには向いてなくて、平均5.68枚もかかります。(1bの答えより0.44枚多い)

ピッタリ払うのに良い組み合わせと、お釣りを含めて良い組み合わせは、
かならずしも一致しない、って事です。

でも逆に、ピッタリ払う時に3種類でベストだった{1、5、22}と{1、5、23}の方は、
お釣りありの時でもなかなか効率が良くて、平均3.14枚。(2bの答え+0.05枚)

{1、8、29}だと、2番目に小さいコインが8セントと大きめなんで、
ちょうど払う時には1セント玉が多く必要になっちゃうんですね。


kashさんの案をお釣りありの方でも載せておくと、
{1、7、13}は3.72枚、{1、8、13}は3.25枚。
{1、3、7、24}は2.86枚でした。


ここからどうやって延長するのか、って言うのは問題ですね。
5種類、6種類とやっていくのもありだし、
100セントを区切りにしているのを変えるのもありです。


---パズル---

A男さんとB子さんの夫婦が、
友達を呼んでパーティーを開きました。
呼ばれたのは夫婦3組。

みんな揃ったところで、以前からの知り合い同士は握手を交わし、
初めて会った人達は握手をせず、ただ挨拶しました。
(夫婦同士は握手しません、笑)

みんなの挨拶が終わったところで、B子さんが言いました。
「私以外のみんなは、それぞれ違う回数握手をしたわね」と。

B子さんは何人の人と握手したでしょうか?

テーマ : 数学
ジャンル : 学問・文化・芸術

コメントの投稿

非公開コメント

No title

ふむ。なるほど。
結果を出してくれてありがとうございます。

あれから、素因数分解や近似を取るやり方を検証してみたんですが、
効率は悪い(プログラムにすると複雑 ?)かもしれませんが、
N種類のコインを0~99の場合で考える場合に、最善のコインの組み合わせと最少の枚数を求める(全体の平均をなるべく少なくする)のを同時に求める時に有効な手段の1つであることがわかりました。
(あくまで、僕の中で)
ベストなやり方では無いと思いますが、ベターなやり方の1つではあるかな、と。

No title

夫婦のパズルにトライしてみたんですが、
可能性としては2か4。
でも、もしかしたら答えを出せないようにも思います。

ただ、これはコンピュータに計算(総当たり)させた方が確実だと思いました。

kashさん

素因数分解や近似のやり方の話なんですが、
例えば{1、7、13}、{1、8、13}をどうやって出したのかなど、
説明してもらえますか?

ただの勘ならそれはそれで良いですし、
自分も、勘や直感で分かってない事は理解してるとは言いません。
でも、その勘を検証するのが科学、証明するのが数学だと思うんです。
定義されてないやり方は、検証も証明も出来ません。
(客観的な意味では)

ちなみに、直感的な上に、説明も付く近似法はあります。
例えば日本のコインの場合、
1番小さいコイン(1)と2番目に小さいコイン(5)の比率は、5倍。
4円、9円などを払う時に、1円玉が4個も必要なのはこのためです。
でも、2番目のコイン(5)と3番目のコイン(10)の比率は、2倍だけ。
5円玉は毎回の支払いで多くて1個しか必要ないんです。
2番目のコインをもうちょっと安くすれば、もっと「均一」な分布になって、
色んな金額を少ない枚数でカバーできるんじゃないかと想像できます。

金額の比率を同じにしたい、という事は、
4種類のコインの場合、{1、x、x^2、x^3}と言う組み合わせにして、
xの4乗が100円になるようにすれば良いんです。

xは、100の4乗根(=ルート10)、小数で言うと3.16...、です。
つまり、この方法で得られる答えは、{1、3、10、32}。
(1c)を見てもらえると分かりますが、答えとそんなに離れていません。
(この組み合わせの効率は調べてませんが、悪くないはずです)

お釣りなしで、2種類、3種類の場合、
実はこの方法でベストの組み合わせがピッタリ出てきます。

100の平方根は10で、この方法で出てくる答えは{1、10}ですし、
100の三乗根は4.64、それを2乗すると21.54なので、
四捨五入すると{1、5、22}が出てきます。

kashさん

夫婦のパズルは、論理的に1つだけの可能性しかありません。
考え方が分かれば、簡単な数独みたいに、1ステップずつ考えれば解けます。
コンピュータは必要ありません。

No title

コメントを含め興味深く拝見しました。 見当違いかもしれませんが、ポーカーやBJに応用できそうな議論ですね。 

夫婦の問題は、私でもなんとか紙と鉛筆を使って、わかりました。 8人いて、7人がばらばらの回数というところと夫婦は握手しないということで、組み合わせを作っていくと、結果はひとつですね。

No title

まず、夫婦のパズルですが、僕はホストも含めて3組の夫婦だと勘違いしてました•••。
まだ答え出せてませんが、トライしてみようと思います。

で、質問へのレスですが、

僕は今回のコイン問題を組み合わせ論じゃなくて数の問題として考えました。
というのは、扱う範囲が0~99の自然数だからというのと、組み合わせ論っていうのを知らないから(学校で順列組み合わせはやりましたけど)別のアプローチでやろう、と。

で、
{1、7、13}と{1、8、13}の組み合わせは、勘ではなく、ざっぱに計算してはいます。
case99とcase1とcase10、
それと、0~99での中間点のcase49と50。
この場合の最適化を考えてはじき出しました(といっても、徹底的に調べあげたわけじゃないです)。
ただ、僕の致命的欠陥は、減法を考慮しなかったことと、前提条件を守らなかったことです。
加法と乗法で方程式組んでましたし、(Wikiで)貪欲法のプログラムを見ましたけど、今の僕にはわかりませんでしたし。

で、素因数分解するやり方(仮に、素因数分解法とします)ですが、この方法にメリットがあるとすれば、
1つの数字から2つ以上の数字が出せるところです。
3種類の場合の{1、12、19}でのcase24は、
24=2の3乗×3の1乗
右辺に出てきた数字を全部足すと、
2+3+3+1=9
この9という値は、最善のコインの組み合わせを考える上で有力な情報です。
(それ以前に、コンピュータで最善が出てますが)
で、case25を考えてみます。
25=5の2乗
5+2=7
で、case24で出た9と足して2で割って出る値が8。
という風に、総当たりでやってもいいし、僕の勘では素数を中心にこのやり方でやっていけば(それと、10進法なので、10や100、今回の場合、最大の数の99など)、最善が出てくると思います。
{1、7、13}などは、このやり方を基に、Nが99までなのを考慮して出してみました。
99ー7or8=92or91
なので、case91かcase92の最適化を考える、といった具合です。

検証はしましたが、素因数分解法が有力である証明は(現段階では)出来ません。それが出来るだけの論理的思考や数学の知識など、持ち合わせてませんので。

数を扱うにあたり、素因数分解が有力かどうかは、お知り合いの数学者の方に聞いてみてくださる方がいいと思います。
僕は、上手く説明出来ませんから。

LFMさん

ポーカーやブラックジャックの最善策っていう問題は、
最適化、って言う意味では同じですね。

カードゲームならルールがはっきりしてるんで、
最適化の基準はもちろんある手を打ったときに勝つ確率ですが、
コインの場合、なにを基準にして最適化するのかも問題として考えてます。

ちょうど払う枚数、お釣りを含めて払う枚数、などなど。

kashさん

率直に言います。
kashさんが、なんで素因数分解をしているのかが全く分かりません。
コメント毎にやっている事が違うように思うので、
「素因数分解法」と言えるような、
定義できるやり方があるようにも見えません。

こんがらがらないよう、箇条書きで質問します。
どれも、ここまでのコメントから僕には判別できないから聞いている、
と言う事で理解してください。

1.kashさんが素因数分解をしている理由は何ですか?
証明して欲しいとか言う事じゃなくて、
kashさんが素因数分解しようと思った理由はなんですか?

2.「素因数分解法」の、インプットとアウトプットは何ですか?

貪欲法の場合、発行されてるコインの金額(例えば{1、5、10、25})と、
払うべき金額(37)をインプットとして与えれば、
払うコインの組み合わせ({25、10、1、1})をアウトプットとして出してきます。

kashさんが、「素因数分解法」を使う時、
考慮に入れる情報(インプット)は何で、
結果として出てくる情報(アウトプット)は何なんですか?

3.上のコメントで、24を因数分解して、24=(2^3)×(3^1)としたあと、
右辺に出てくる数字を全部足しています。
これにはどういう意味があるんですか?
○乗する数と、○乗される数は違う種類の数字なわけで、
全部を足す事に意味があるとは思えません。
kashさんがこうしようと思った理由は何ですか?

4.24から上に書いたような手順を踏んで9が出たわけですが、
なんで9は使わず、
25から出てきた7は使ったんでしょうか?

5.そもそも、なんで24と25なんでしょうか?


基本的に、全ての段階で、
kashさんのやろうとしている事が分からないんです。
理由がどの段階でも分からないので、
勘で出てきた答えに、後付けで素因数分解から数字を出してきているように見えます。

No title

まず、僕の計算は(今回の問題を考えるにあたって)正しくない、ということを念頭に置いて回答を読んでください。

その理由として、
①コンピュータで答えが出ているし、アシュリーさんが3乗根などを用いてわかりやすい説明を与えてくれている
②僕の頭は、(よくて)中学卒業までの数学程度の思考レベルで動いている

②については、僕のある信念のもと、今はまだ敢えてそういう手法を取っています、としか言いようがないです。
(ただ、今回の問題を考えるにあたり、適切ではなかったかもしれません。すいません)

(僕が習った)中学数学で3乗根が出てきたかどうか、ちょっと定かでないんです。僕は思考を働かせる上でルートを使いませんが、アシュリーさんのルートを使った説明は理解してるつもりです。

それを踏まえて、回答します。

1.
(コインが4種類の場合)コインの組み合わせ{a、b、c、d}と、これらのコインを使って0~99セントを支払った場合に平均N枚コインが行き来する(ないしは丁度払う。僕は丁度払うのを主に考えてました)として、{a、b、c、d}とNを同時に求めてみたかったからです。

2.

※インプットとアウトプットは、アシュリーさんの例から推測してます。

アシュリーさんの例えに沿うと、
インプットは、37です。
で、
アウトプットは、コインが4種類の場合は{a、b、c、d}(a、b、c、dは任意の数)と平均値のNです。

ただ、これまでのやり取りの中で、僕は大ざっぱにしか計算してませんので、アウトプットの値は大ざっぱにしか出てませんが。

3.

足した理由については、きちんとした説明が現段階では出来ません。(仮説の域を出ないものでも構わないなら、説明は一応出来ます)
なので、足さない方がよかったですね。
すいません。

4.

24と25の前後の数である23と26から僕のやり方で数字を割り出すと8という値が出てきます。
23で8、24で9、25で7、26で8。
ここで、僕は平均を取ります。
(平均を取る理由は、最終的に平均値を割り出すことを目標にしているからなんですが、この考え方が間違ってる、と指摘されたら、反論する術を僕は持ちません)
平均したら32÷4=8。
僕が3種類のコインの組み合わせで8を使ったのは、これに基づいてます。
同じ手法で22から6、27から6という値が出ます。
で、(22、23、24)から得られる<6、8、9>の平均7.3と、(25、26、27)から得られる<7、8、6>の平均7から推測して(近似値を取って)7をはじき出しました。

5.
24と25に深い意味は無いです。
これまでのやり取りの中で24と25が出てきたから使ってみただけです。

以上が回答です。

ちなみに、夫婦のパズルの答えは3じゃないかと思います。
一辺に1組の夫婦が並んで座れる正方形のテーブルがあるとして、時計回りに(A、B)(C、D)(E、F)(G、H)の順で座らせます。
で、正方形をずらしていきました。

No title

回答の1.と2.の補足と訂正をします。

1.

こちらは上のコメントの補足として読んでください。

0~99までの整数nの場合、
n=1^x+2^x+3^x+5^x+7^x+•••
という風に、1と素数(の累乗?)の組み合わせというか数式というか(すいません、専門用語がわかりません)、いずれにしろ、上の形に表せると思ったからです。
で、行き来するコインの枚数は、コインが2~4種類の場合であれば、十中八九、1~10(1~1+3^2)くらいまでだろうと推測したので、素因数分解しようと思いました。
ただ、2^0は、たしか1ですよね?
そこは、考慮に入れてませんでした。

2.

こちらは、訂正。

アウトプットですが、4種類の場合は{a、b、c、d}は出てきます(その組み合わせが正しいかどうかは、僕が仮に位置付けた素因数分解法が有用なものなのかどうか、ちゃんとわかってないので、僕も確信はしてません)。
それと、0~99までを総当たりで探るプログラムを組むなら、上に書いたように平均値のN枚が出ると思います。

プログラミングで可能かどうかわかりませんが、僕のステップは以下の通りです。

① 任意の数p(ここでは37とします)を素因数分解する → 37=1×37
②コインの種類Qが1より大きい、つまり、1<Qとして(Q=1の場合、アウトプット出来ないんじゃないか、と)、①で出た1と37を○○セント硬貨の有力候補として、とりあえず放り込みます(つまり、{a、b、c、d}のどれかに放り込む)。
③ ②で出た1と37を使って、case99を考える。
この場合、
99=37×2+1×25
  =37×3ー1×12

つまり、1セント硬貨と37セント硬貨を使って99セントを支払う場合、最少で15枚必要になる、とします。
なので、(とりあえず)理想の平均値Nは15だと設定することにして、他のcase(case1など)を探っていきます。

(ここからは自信ないですが)
と同時に、上の式で出てきた2、3、12、25という数字をコインの候補にリストアップします。

で、①の手順に戻ってもいいのかもしれませんし、
僕は、1、2、3、12、25、37を使って、まずはcase99の最適化(使うコインの最少化)を考えていきます。
という風に、4種類の場合は{a、b、c、d}を絞っていこうと試みました。

ただ、これは貪欲法に従ってないし(ルールに乗っ取ってない)、アシュリーさんがご指摘のようにプログラムにすると複雑になるかもしれません。

それから、○乗する数と○乗される数は違うとご指摘があったので、使ってません。

kashさん

返答どうもです。
ではでは、返答の返答。

1.素因数分解の一番の特徴は、2以上の全ての数について、
ちょうど1通りの分解が出来る事です。
24は24=2×2×2×3と言う分解が出来て、それ以外の分解は出来ません。
24と言う数字と2×2×2×3と言う分解が1対1で対応するからこそ、
この素因数分解が24の特性と言えるんです。

一方、kashさんの書かれた、
24=1^a+2^b+3^c+5^d+7^e+...と言うのは、
何通りも書き出し方があるんで、どれを選ぶのかが問題になってしまうと思います。

これは3の質問とも、1の返事でkashさんが気付いてる部分とも繋がりますが、
24=2^3×3^1の○乗する数の方に意味を持たせてしまうと、
24=2^3×3^1×5^0とか、24=2^3×3^1×23^0と言う風に、
同じ分解でも違う意味になってしまう事になります。
これは同じようにまずいんじゃないかと思います。

2.インプットとアウトプットは、こちらの例が悪かったかもしれません。

一番上のコメントで自分が書いた、「累乗法」の例で言うと、
インプットは、コインで払わなくて良い最小の金額
(これは今のところは100ですが、1000でも、64でもなんでもいいです)
コインの種類の数(2、3、4、等等)の2つの数字です。

この2つの数字から、上に書いたような方法で、
コインの金額の組み合わせがアウトプットとして出てきます。

kashさんの方法のアウトプットが、
コインの組み合わせと、
払う平均枚数(これがどうやって出るのかはまだ良く分かりませんが)、
だと言う事は分かりました。

ただ、インプットに付いてはまだはっきりと分かりません。
kashさんの方法を使って、
3種類のコインの組み合わせを得ようとすると、違った答えが出るんでしょうか?
100セントじゃなくて、64セントが1ドルだったら、
(63セントまでしか硬貨で払わなくて良かったら)
違った答えが出てくるんでしょうか?
と言った事が聞きたかったんです。

種類の数や、払う上限の金額が変わる事で、
違った答えが出てくるのなら、それはインプットです。

この辺は、用語のせいで分かりづらくなってるかもしれません。
「方法」と「関数」は、同意義として考えてもらって良いです。
y=f(x)って言う式は、xと言う数字をfって言う関数にインプットすると、
yと言う数字がアウトプットとして出てくる、と言う事です。

言い換えると、fは、xと言う数字から、yと言う数字を出す「方法」です。

4.&5.平均されている数字の意味が分からないんで、
平均を取るべきかどうかについてはコメントできません。
ただ、23から26で得た数字を平均する、と言う事は、
1から22、27から99の数字を無視している、と言う事にもなりませんか?

(こういう順番で書きますけど、以下、2番の続きです)
コンピュータからの結果で分かるように、
コインの種類の数によって、答えに入ってくるコインの金額は全然違ってきます。
kashさんの方法が、どうやってその違いを出すのかが、
ここまで聞いても良く分からないんです。

kashさん

パズルの方ですが、3人で正解です。

ただ、「正方形をずらしていきました」、って言うのは、
どういう事でしょう?
自分が考えてた解とはかなり違う発想なんで。

No title

返答の返答に返答します(笑)。


といっても、一言だけ。

今の自分には、アシュリーさんの返答の全てに自信を持って自分の意見を展開出来るだけの理論武装(知識)がありません。
(ここはアシュリーさんの場所なので、これ以上、持論を展開するのは、今は自粛したいです)

逆に言えば、今回のやり取りで安心して次のステップに進めると感じました。

ご教授、ありがとうございます。

No title

あ、勘違いしないでほしいんですが、
議論を勝手に放棄するというネガティブな意味に受け取ってほしくないです。
アシュリーさんが構わないのであれば、今の自分の考えを返答します。

判断は、アシュリーに委ねます、ということです。

蛇足になりましたが、一応。

kashさん

じゃあ、1つだけ質問します。
次のステップは、どこを目指してるんでしょうか?

今日考えてみたら、
一番単純なケースに限ると、証明可能な答えが出てきました。
これは記事にして説明しますね。
振り返ってみると、単純な問題を解く前から、
難しい問題に取り組んじゃってたように思います。

No title

次のステップは、高校数学を(僕が高校生だった時の参考書を使って)復習して、その頭で色々考えてみる、です。

高校物理もやります。
それが、その次のステップに進むために必要なことが明白なので。

今回のやり取りは、僕にとってとても有意義なものでした。
ありがとうございます。

FC2ブログランキング

FC2ブログランキング

プロフィール

アシュリー

Author:アシュリー
カリフォルニア州バークリー在住、元スポーツジャンキーのアシュリーです。

今観るスポーツは、アーセナル(サッカー)とグリズリーズ(バスケ)、あとテニス。

専門の物理ネタ以外にも、色々書いていくつもりです。

Twitterをハンドル名Inoueianでやっています。

ブログ内検索
カレンダー
10 | 2017/11 | 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -
最近の記事
最近のコメント
最近のトラックバック
カテゴリー
リンク
RSSリンク
月別アーカイブ
メールフォーム

名前:
メール:
件名:
本文:

カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。