アットランダム≒ブリコラージュ

2635：お釣り

問題2635・・・浮浪の館 http://www.geocities.jp/hagure874/　より Orz〜
















































解答

・理科ちゃんマンさんのもの Orz〜

おつりの硬貨は4種類。そのうち、50円と5円は2枚もらうことはないし、10円と1円も5枚もらうことはない。
でもって、場合分け〜。
1400円で、10円×２，5円×１，1円×１のおつり。
1900円で、50円×１，10円×１，5円×１，1円×３のおつり。

同じく...^^

2634：場合の数

問題2634（友人問）

1から10までの10枚のカードから3枚を取り出す組み合わせ（10C3=120）のうち、
カードの最大数が、その他の2枚に書かれている数の和より大きい組み合わせは何通りあるか。






























































解答

・わたしの

3=1+2・・・4〜10
4=1+3・・・5〜10
5=1+4=2+3・・・6〜10
6=1+5=2+4・・・7〜10
7=1+6=2+5=3+4・・・8〜10
8=1+7=2+6+3+5・・・9〜10
9=1+8=2+7=3+6=4+5・・・10
つまり、1*7+1*6+2*5+2*4+3*3+3*2+4*1=50

対称なら、、、(そうであるかどうか証明できない ^^;・・・ac との数が同数あるのか？）
10=1+9=2+8=3+7=4+6
9=1+8=2+7=3+6=4+5
8=1+7=2+6=3+5
7=1+6=2+5=3+4
6=1+5=2+4
5=1+4=2+3
4=1+3
3=1+2
の20個あるので、(120-20)/2=50

もっと華麗な方法がありそうね...^^;
追記：2009.05.18
対称性の証明を鯨鯢(Keigei)さんよりいただきました Orz〜（以下のコメ欄参照ください）♪

2633：メビウス関数と指数関数

問題2633・・・ひよこさんのサイト http://myhome.cururu.jp/gersdorffite/blog/article/71002606795　より Orz〜

n│Σ_[d|n]μ(d)2^(n/d)　 を証明せよ。























































解答

上記サイトより Orz〜

・ひまつぶしさんのもの Orz〜

別に2で考える必要もないですので、一般化して考えます
n|Σ_[d|n]μ(d)a^(n/d)を示します。

かえでさんの方針でやってみました。

記述を簡単にするために、巾乗を一部以下のように書きます
x^n=Po(n,x)

補題※
pを素数、a，k，mを正整数とするとき以下が成り立つ。
p^k|Po(p^k *m，a)-Po(p^(k-1) *m，a)

補題※証明
Po(p^k *m，a)-Po(p^(k-1) *m，a)=Po(p^(k-1) *m，a)*{Po({(p-1) *p^(k-1)}*m，a)-1}

aがpで割り切れるとき
当然、p^k|Po(p^(k-1) *m，a)が成立する。
aがpで割り切れないとき
フェルマー・オイラーの定理より、p^k|Po({(p-1) *p^(k-1)}*m，a)-1が成立する。

よって、p^k|Po(p^k *m，a)-Po(p^(k-1) *m，a)が示された
補題※証明ここまで

本題に入ります。
f(n)=Σ_[d|n]μ(d)a^(n/d)とおくとき、メビウスの反転公式より
Σ_[d|n]f(d)=a^n…○
がいえます。

nの素因数pを任意にとり、k=v_p(n)とおくと、n=p^k *bとかける

任意の正整数mに対して、p^k|f(p^k *m)となること…♪
を示す。

m=1のとき
○の式は、f(p^k)=Po(p^k，a)-Po(p^(k-1)，a)と変形できる
補題※よりp^k|Po(p^k，a)-Po(p^(k-1)，a)がいえる。

m<hのとき正しいと仮定して、m=hの時を考える。
○の式は
Σ_[d|p^k *hかつdはp^kで割り切れない]f(d)+Σ_[d|p^k *hかつdはp^kで割り切る]f(d)
=Po(p^k *h，a)
と書ける。

Σ_[d|p^k *hかつdはp^kで割り切れない]f(d)=Po(p^(k-1) *h，a)より
Σ_[d|p^k *hかつdはp^kで割り切れ、かつd<p^k *h]f(d)+f(p^k*h)
=Po(p^k *h，a)-Po(p^(k-1) *h，a)
となる
補題※より、p^k|Po(p^k *h，a)-Po(p^(k-1) *h，a)がいえ、帰納法の仮定より
p^k|Σ_[d|p^k *hかつdはp^kで割り切れ、かつd<p^k *h]f(d)もいえる。
したがって、p^k|f(p^k *h)がいえる。
したがって帰納的に、p^k|f(p^k *m)がいえたことになる。

♪より、n|f(n)がいえることは明らかである。

・ひよこさんのもの Orz〜

私の用意していた解答はこんな感じです。
（反転公式を適用せずにそのまま計算します）

任意に素数冪p^kを取り、
pで割り切れない正整数mを任意に取ります。
n=m*p^k　とおきます。
このとき、 p^k|f(n) を示します。

f(m*p^k)=Σ_[d|m*p^k]μ(d)a^(n/d)=Σ_[d|m*p]μ(d)a^(n/d)
=Σ_[d|m*p, ?p|d]μ(d)a^(n/d)＋Σ_[d|m*p, p|d]μ(d)a^(n/d)
=Σ_[d|m]μ(d)a^(n/d)＋Σ_[pe|m*p]μ(pe)a^(n/(pe))
=Σ_[d|m]μ(d)a^(n/d)＋Σ_[e|m]μ(p)μ(e)a^(n/(pe))
=Σ_[d|m]μ(d)a^(n/d)‐Σ_[d|m]μ(d)a^(n/(pd))
=Σ_[d|m]μ(d){a^(n/d)-a^(n/(pd))}
=Σ_[d|m]μ(d){a^(m*p^k/d)-a^(m*p^(k-1)/d)}

｛　｝内はp^kで割り切れますので示せました。


メビウス関数から勉強しないと...すぐについては行けないなあ...^^;;
メビウス関数ってとっても便利でおもしろそうだと思った記憶あり...

2632：n乗数の下n桁を消してもn乗数

問題2632・・・ひよこさんのサイト http://myhome.cururu.jp/gersdorffite/blog/article/71002639387　より Orz〜

次の条件を満たす自然数を全て求めよ。

（条件）
n乗数であり、下n桁消してもn乗数である。


























































解答

・わたしの

証明ではないけど、、、流れ的には、、、
9^2=81 は二桁なので、二桁以上の2乗数・・・
100^(1/2)<=x<200^(1/2)・・・10^2,11^2,13^2,14^2
400^(1/2)<=x<500^(1/2)・・・20^2,21^2,22^2
900^(1/2)<=x<1000^(1/2)・・・30^2,31^2
1600^(1/2)<=x<1700^(1/2)・・・40^2,41^2
2500^(1/2)<=x<2600^(1/2)・・・50^2

1000^(1/3)<=x<2000^(1/3)・・・10^3,11^3,12^3
8000^(1/3)<=x<9000^(1/3)・・・20^3,
27000^(1/3)<=x<28000^(1/3)・・・30^3

10000^(1/4)<=x<20000^(1/4)・・・10^4,11^4
160000^(1/4)<=x<170000^(1/4)・・・20^4

100000^(1/5)<=x<200000^(1/5)・・・10^5,11^5

2^(1/8)=1.09・・・

つまり、n>=8 では、(10*m)^n のみ。
それまでは、(10m)^n,(10m+k)^n ・・・n によって、1<=k<=4 までありうる。
上手く言えない...^^; Orz...

・ひよこさんのコメ Orz〜

それらに加えて、11^6, 11^7を加えてもらえれば、
答えとしてはそれで正しいです。

書いてあることを見るかぎり、言いたいことはわかります。
そのような感じになるとおもいます。
あとは、それらのことを不等式で形式的に
示すことができるかできないかの違いです。


それが...言えそうでどういう風に言えばいいのかわからない...^^;

2631：平方数

問題2631・・・ひよこさんのサイト http://myhome.cururu.jp/gersdorffite/blog/article/71001600636　より Orz〜

m, n ∈N 　とする。
次の数は平方数になりうるか。

(mn)^2+m(2n^2-1)

















































解答

上記サイトより Orz〜

「補題」
任意に正整数mを与えます。
このとき、次の2元2次不定方程式は正整数解を持ちません。
x^2-2(m+1)xy+y^2+m=0　　・・・☆

「証明」
☆が正整数解をもっていると仮定します。
☆の正整数解全体の集合をXとおきます。

ある正整数sが存在していて、
(s,s)∈X であると仮定しますと、
s^2-2(m+1)s^2+s^2+m=0 ⇔ m=0 となります。
これはm＞0であることに反します。
よって、(s,s)∈X となるような正整数sは存在しません。

ここで、任意にe∈min｛x+y| (x,y)∈X｝ を取りますと、
さきほどいったことと、☆のx,yにおける対称性から、
とくに、q＞p かつ、(p,q)∈X かつ p+q=e を満たす
正整数p,qの組が取れます。

すると、まず、(p,q)∈X から、
方程式：x^2-2(m+1)px+p^2+m=0　・・・(*)
がすくなくとも1つの正整数解x=qをもつことがいえますが、
(*)はもう１つの実数解x=rをもっています。
解と係数の関係から、q+r=2(m+1)p かつ qr=p^2+m ですから、
前者から、rは整数であるとわかり、
後者から、rが正であることがわかります。
つまり、(*)は正整数解rも持つとなります。
（前者の式は再び使うので、r=2(m+1)p-q　・・・○　としておきます）
このことから、(p,r)∈X であることがいえました。
あとは、p+r＜e=p+q であることが示されれば、
矛盾となり、めでたく証明終了となるわけです。
以下、それを主に不等式の同値変形から示します。

(p,q)∈X でしたから、
q^2-2(m+1)pq+p^2+m=0 ⇔ m=(q-p)^2/(2pq-1)　・・・△

○と△の下で、不等式：p+r＜p+q を同値変形していきます。

p+r＜p+q ⇔ r＜q ⇔ 2(m+1)p-q＜q ⇔ (m+1)p＜q
⇔ mp＜q-p ⇔ p(q-p)^2/(2pq-1)＜(q-p)
⇔ p(q-p)/(2pq-1)＜1　　（q＞pに注意して下さい）
⇔ p(q-p)＜2pq-1 ⇔ -p^2＜pq-1

最後の不等式は、-p^2＜0＜pq-1 より成立がいえますので、
よって、p+r＜p+q がいえたことになります。
これはeの取り方に反していますので矛盾となりますので、
したがって、補題の証明が完了したといえます。

以下、本題の解答例となります。

D=(mn)^2+m(2n^2-1) とおきます。
ある正整数m,nに対して、Dが平方数になったと仮定します。
このとき、矛盾が生じることを示します。

Dが平方数であることより、4Dも当然平方数ですから、
x^2-2(m+1)nx+(m+n^2)の判別式が4Dであることに注意して、
x^2-2(m+1)nx+(m+n^2)=0 がある正整数解x=αをもつことがいえます。
これから、2元2次不定方程式x^2-2(m+1)xy+y^2+m=0
がある正整数解(x,y)=(α,β)をもつことがいえますが、
「補題」より、それは矛盾となります。

以上より、(mn)^2+m(2n^2-1)が平方数となるような
正整数m,nは存在しないと結論することができます。

巧い感じだけど...熟読玩味...^^;