2009年03月21日の記事一覧 - 詳細表示

2490：線分分割

イメージ 1

問題2490・・・算チャレ掲示板にてあみーさん提示問 Orz～

線分を2等分から100等分する99回目の作業までに「３本増える」のは何等分するときか？

解答

・わたしの

m 等分するとき、m=p^a_1*q^a_2*・・・
増える数=(m-1)-(p^a_1-1)-(q^a_2-1)-・・・=3
m=p^a_1+q^a_2+・・・+3-α
3-α は、素因数の種類が偶数の時、偶数
　　　　　　　　　　　奇数の時、奇数
m が偶数の時、2以外に奇数個の奇素因数をもつ時、
m=偶数＋奇数*奇数＋偶数=奇数で矛盾。
2以外に、偶数個の奇素因数をもつ時、
m=偶数＋奇数*偶数＋奇数=奇数で、矛盾。
m が、奇数の時、m の素因数はすべて奇素数
奇素数の種類が偶数の時、m=奇数*偶数＋偶数=偶数で矛盾。
奇素数の数が奇数の時、m=奇数*奇数＋奇数=偶数で、やはり矛盾。
よって、存在しない。
ってことは、、、増加分が3以上の奇数になることはあり得ない・・・？
唯一、2等分にする時、1だけ増える。

たとえば、m=p*q のとき、
m 等分して増える数=m-1-(p-1)-(q-1)=pq-p-q+1=p(q-1)-(q-1)=(p-1)(q-1)
これは、
φ(m)=φ(p*q)=φ(p)*φ(q)=(p-1)(q-1)
という、オイラーのトーティエント関数と同値なんだ...
m=p^a
m-1-(p^(a-1)-1)=p^a-p^(a-1)
だから、、、上の式は・・・

m 等分するとき、m=p^a_1*q^a_2*・・・
増える数=(m-1)-(p^(a_1-1)-1)-(q^(a_2-1)-1)-・・・=3
m=p^(a_1-1)+q^(a_2-1)+・・・+3-α
でないとだめですね...Orz...^^;

・友人のもの

左右対称にとられるから（奇数の場合も最初真中がとられているので
左右同数ずつ残っている）、3本（奇数個）増えることはない。

たしかにシンプルでいい♪