【数セミ】エレガントな解答をもとむ3【2018.10】
■ このスレッドは過去ログ倉庫に格納されています
Nothing really matters to me,
anyway the wind blows.
http://www.youtube.com/watch?v=sBspSJWRT2E 05:58 出題1、結果だけならプログラム組めば出せる
無論、そこにエレガントさはカケラもない。
1から2倍と桁入れ替えで到達可能な数をリストアップすると、以下を除く4桁の数(5558個)になった。
これらが1に到達不可能なことを確かめるのは難しくない。
・3の倍数
・全ての桁が奇数
・全ての桁が2か6
・1114, 1141, 1411, 4111, 1118, 1181, 1811, 8111, 2228, 2822, 2282, 8222, 4444, 8888 まず、3の倍数であることは(1)(2)で変わらない。
最大n回(2)が可能、で考察すると
0回:全ての桁が奇数
1回:全ての桁が2か6、1114, 1141, 1411, 4111, 1118, 1181, 1811, 1110, 1101, 1011
これは下2桁が4の倍数+2、2で割って千の位が奇数、2で割って十の位が奇数、を考えればよい。
2倍→桁を入れ替え→2で割る、という手順でここから抜けられない数を順次リストアップしていくと
2回:2228, 2822, 2282, 8222, 4444, 2220, 2202, 2022
3回:8888, 4440, 4404, 4044
4回:8880, 8808, 8088
5回:なし
となって、上記に含まれない数は手順を選べば無限回(2)が可能。
蜂の巣原理から、その手順のどこかで桁の組合せが同じ数に戻る。
……までは考察できたが、それが1に到達可能な数という保証ができないな。 読み直してみると、途中で3桁に落ちるパターンが考慮から漏れているかな。
3桁でも同じようなことを考えることはできそうだが。 ・3の倍数
1002から9999まで 3000個
・全ての桁が奇数 {1,3,5,7,9}
5^4 - 208 (3の倍数) = 625 - 208 = 417個
・全ての桁が {2,6}
2^4 - 4 (2が3個) -1 (6666) = 11個
・{1114} {1118} {2228}, 4444, 8888 = 14個
・{1110} {2220} {4440} {8880} は3の倍数 = 0個
ここまで 3442個 (到達不能)
・全体で
1000から9999まで 9000個
・上記のリストにないものは
9000 - 3442 = 5558個 1/2倍だけではなく2倍の操作も許し、途中で5桁以上になっても良いとすると、1に到達不可能なのは元の数が3で割り切れることと同値なようだ。
(5桁まで膨らむ場合をPCで計算。実は5555のみが例外的に到達不能だったが、桁数を増やせば行けるんじゃないか。)
つまり、桁数を無視すると(1)(2)でつながるネットワークの頂点はmod3=1,2の集合ということになる。
あとはその中から2倍操作をしなくても1に到達するものを選ぶという話になるな。 >>657
5555も6桁使えば行けたわ。
5555 (×2^5)->177760->177706->88853->53888->26944->24496->12248->6124->1624->812->128->略 うん、鳩の巣原理だな
全桁奇数は回避できるが無限ループで1に到達できず、という可能性を排除できないけどなんかいえねーかなーと…… でも蜂の巣って一つの巣に何百何千の蜂が住んでいらっしゃるから
本来の鳩ノ巣原理のニュアンスとは違ってこなくないかい >>662
蜂の巣は誰でも知ってるでしょ
でも鳩ノ巣を見たことあるか? pigeonhole principle
pigeonhole:
鳩がせっせと作る巣ではなくて、(区分けされた)巣箱
転じて、棚などの区画
鳩の巣
https://gaiju-seikatsukyukyusya.com/pigeon/information/post-72/ 日本語の鳩ノ巣じゃまずいから引き出し論法にしたのかもしれんが、もっとまずいだろ
それに比べて蜂の巣はどうだ
穴と蜂の対応関係が絶妙にイメージしやすいではないか 正直ピーターは手も足も出ず、こんなコメントしかできないのが恥ずかしいわ ちなみに俺のアプローチを言うと、4桁から3桁へ、3桁から2桁へ移る数のうち、1へ到達可能な数を調べ上げた
例えば2桁の数は58,61,64,85,92に限られるので、
÷2でこれらに移行できる3桁の数Tは上の5数の2倍。
同様にして、最終的に上の3桁5数に到達できる4桁の数Qも多少の根気で調べ上げることができる(1000以上1999以下)
あとはQに到達できる4桁の数を網羅すればよい
この網羅は全く容易でない
ゆえにこれらの努力が無駄であることが示された(証明終) 蜂の巣というたらあのでっかい塊のこと
巣と巣穴を混同してはいけない
だから蜂の巣穴論法というべき 規則性や保存量を一生懸命探したが見つからなかったな 嗚呼!! 花の応援団(1975〜1979)
チト古杉.... 出題1むずすぎるんだが
nは絞り込めても表が作れる気がせん >>679
十分条件を求められているかというとハテナでございます 出題2は(3)が1番簡単な気がするんだが
読み違えてるのかな >>679 >>680
この話に心当たりがあったのでもうググって答え見た。
資料みて思うにコレは表の存在を自分で導出するのは無理だ。
なんせ表の存在だけで論文になってるレベル。
この表をいかに簡単に作れるかでひとつのテーマになってる。
(1)も(2)も存在しうるならこの2つしかないまでで良いんだろうと思う。 先月号の出題2が全然話題にならないのは
個々の住人には簡単すぎたから? >>686
早々に解けたことは覚えてるけど全く記憶にない
簡単すぎたのか、ピーターに時間を費やしすぎたか >>687
いま問題見て思い出した
大学受験みたいだなーと思った
こういう問題はツマラン >>685
与えられた問題を解くだけなら簡単そうだ
やはり出題2(3)だな今月の山場は 先月の出題2は x^2+y^2=z^2 の一般整数解を知ってればつまんない問題ではないかな
交点の確認から外接条件、と誘導もしっかりしてて、あとは計算するだけに見える この雑誌って完全に数学科向け?
物理出身だが買ってみたいんだか 出題2の(3)、多分解けた。
条件をみたす「島」を思い付くと意外と気持ち良い。 >>693
早いじゃないか
島であること、有界でないこと、の2ステップだな
なんとなくイケる気がするんだが2トライして失敗
次は何を試そうかなあ(楽しい) >>685
Steiner system S(5,8,24) の自己同型群は Mathieu群 M_24 で5重可移なんだね。
しかし一般に、どのようなパラメータに対して block design が存在するか
という問題は非常にむずかしい問題で、Combinatory Analysis のもっとも
重要な問題の一つらしい。。。 >>701
出来たよ。回答は今月8日の締め切り後に出すつもりだけど。
ヒント(といえるかはわからんが)として、明日ぐらいに回答に使った定理ぐらいは書いてもいいよ。
書いて欲しい人がいればの話だけど。 明日になった。(?)
・中国剰余定理は、主張をきちんと述べれば証明する必要はありません。
・ディリクレの算術級数定理も証明なしに用いて構いませんが、用いないで済めばその方が良しとします。
らしいぞ。 すまんが706は忘れてくれ
これはヒントだろうか?
否。断じて否である。 出題2の(3)の回答
rを素数とする。rより大きな2r+2個の素数p(0),p(1),…,p(r),q(0),q(1),…,q(r)をとる。
正の整数aを以下の様に定める。
「
a≡0 (mod r)
rより小さな任意の素数sに対して
a≡1 (mod s)
a≡1 (mod p(0)p(1)…p(r) )
a≡-1 (mod q(0)q(1)…q(r) )
」
また正の整数bを以下のように定める。
「
b≡0 (mod a)
0≦i≦rをみたす任意の整数iに対して
b≡-i (mod p(i)q(i) )
」
明らかに、gcd(a,p(0)p(1)…p(r)q(0)q(1)…q(r) )=1
であることに注意すると、a,bは無数の値をとりうることがわかる。
ここで、r-1個の点(a,b+i)達は、「面積」r-1の「島」であることを示す。…※
(ただし、1≦i≦r-1) 出題2の(3)の回答続き
命題※の証明
3r+3個の点(a-1,b+i),(a,b+i),(a+1.b+i)達を考える。(ただし0≦i≦r)
a-1,b+iは、少なくとも公約数p(i)を持つので、点(a-1,b+i)はCの要素ではない。
またa+1,b+iは、少なくとも公約数q(i)を持つので、点(a+1,b+i)はCの要素ではない。
点(a,b+i)を考える (ただし0≦i≦r)
i=0,rのとき
a,b,b+rは、少なくとも公約数rをもつので、点(a,b),(a,b+r)はCの要素ではない。
1≦i≦r-1のとき
gcd(a,b+i)=gcd(a,i)=1
(∵aの素因数は、すべてr以上であり、かつiの素因数は、すべてrより小さいから。)
だから、点(a,b+i)はCの要素である。
したがって、命題※が正しいことがわかる。
素数rはいくらでも大きくとれるから、いくらでも大きな「面積」の「島」の存在が言えた。 出題2の(2)は>>710-711でr=2とおけばよい。 任意の大きさを作る解
補題
自然数nにたいし自然数a,b,k,eと素数p,q,ri,si (0≦i≦n+1)が
n<p<q、
(pq)^e ≡ 1 (mod ri)、(pq)^e ≡ -1 (mod si)、
pqk + ap ≡ -i (mod ri)、pqk + ap ≡ -i (mod si)、
(pqk + bq - 1) - (pqk + ap + 1) + 1 = n、
を満たす時、{((pq)^e, pqk + ap + i) | 1≦i≦n}は大きさnの島である。
∵) pqk + ap + i = pqk + bq - (n+1-i) は1≦i≦nであるとき、p,qのいずれとも互いに素であるから(pq)^eとも互いに素であるから((pq)^e, pqk + ap + i) は陸地である。
pqk + ap + 0はpの倍数、pqk + ap + n+1 = pqk + bqはqの倍数であるから陸地ではない。
0≦i≦n+1にたいしpqk + ap + i、(pq)^e-1は共にriの倍数であるから((pq)^e-1, pqk + ap + i)は陸地ではなく、pqk + ap + i、(pq)^e+1は共にsiの倍数であるから((pq)^e+1, pqk + ap + i)は陸地ではない。□
そこで補題の条件を満たす組みが存在する事を示せば良い。
eiをe1=3、e(i+1)=ei(pq)^eiと定めるとき、
((pq)^e(i+1)-1)/((pq)^ei-1) ≡ (pq)^ei ≡ 1 (mod (pq)^ei-1)、
((pq)^e(i+1)+1)/((pq)^ei+1) ≡ (pq)^ei ≡ -1 (mod (pq)^ei+1)
により相異なるi,jに対し((pq)^e(i+1)-1)/((pq)^ei-1)、((pq)^e(j+1)-1)/((pq)^ej-1)は互いに素である。
そこで((pq)^e(i+1)-1)/((pq)^ei-1)の素因子からri、((pq)^e(i+1)+1)/((pq)^ei+1)の素因子からsiを選べば良い。
この時第3式を満たすkは中国の剰余の定理によってとれる。
第4式はユークリッドの互除法によりとれる。 8月号の問題2は一見ラマヌジャン的な唐突さを感じるな >>710
M = (rより小さな素数s すべての積)・p(0)p(1)・・・・p(r),
N = q(0)q(1)・・・・・q(r),
とおく。
仮定により MとNは互いに素だから、
M u - N v = -1 をみたす整数 u,v がある。
(ユークリッドの互除法で得られる。)
2Mu+1 = 2Nv-1,
一方、仮定により MNとrは互いに素だから
k・(-MN) ≡ 1 (mod r)
となる整数 k がある。そこで
a = (2Mu+1)(1+kMN) = (2Nv-1)(1+kMN),
とおく。
-------------------------
i ≦ r < p(i), q(i) より i と p(i)q(i) は互いに素。
L(i) = aΠ[j≠i] p(j)q(j)
とおく。
仮定により L(i) と p(i)q(i) は互いに素だから
k(i)L(i) ≡ -i (mod p(i)q(i))
となる k(i) がある。そこで
b = Σ[i=0,r] k(i)L(i) = aΣ[i=0,r] k(i)Π[j≠i] p(j)q(j).
とおく。 7月号問1は本誌読んでるかの抜き打ちチェックだったな 数セミ増刊「数学100の問題」日本評論社 (1984)
p.60-61 (山本幸一)
中村義作ほか:「数理パズル」中公新書 (1976)
p.178-187
別冊 数理科学「群とその応用」サイエンス社 (1991)
p.36-40 (永尾 汎) p.150-158 (景山三平)
永尾 汎:「群とデザイン」岩波 数学選書 (1974) 折れも任意の自然数nに対して面積nの島を考えてみた。
(文字や考え方など、大分>>713氏をパクっているがw)
「
nを整数、p.qをn<p<qをみたす素数とする。
a,e,r(i),s(i)を下記のようにとる。(ただし、0≦i≦n+1)
a≡0 (mod p)
a+i≡0 (mod r(i)s(i) )
a+n+1≡0 (mod q)
eはある正の整数
r(i)達は(pq)^e-1を割り切る相異なる素数。
q(i)達は(pq)^e+1を割り切る相異なる素数。
」…♪
このとき、( (pq)^e,a+i)達は「面積」nの「島」である(ただし、1≦i≦n)。
3n+6個の点( (pq)^e-1,a+i)、( (pq)^e,a+i)、( (pq)^e+1,a+i)を考えると
(ただし、0≦i≦n+1)
上記のようにとれば、(pq)^e-1,a+iは少なくとも公約数r(i)を持ち
(pq)^e+1,a+iは少なくとも公約数s(i)を持つので、
( (pq)^e-1,a+i),( (pq)^e+1,a+i)達はCの要素ではない。
(pq)^e,aは公約数pを持ち、(pq)^e,a+n+1は公約数qを持つ。
aより大きな最小のpの倍数はa+p>a+nでありかつ
a+n+1より小さな最大のqの倍数はa+n+1-q<aだから
a+1,…,a+nはp.qいずれでも割り切れない。
したがって、1≦i≦nのとき( (pq)^e,a+i)はCの要素である。 あとは、♪が実際に構成可能であること。
n,p,qは明らか。
bをpqの倍数とするとき
gcd( b^(pq)士b^(pq-1)+b^(pq-2)+…+1,b干1)=gcd(pq,b干1)=1
b^(pq)士b^(pq-1)+b^(pq-2)+…+1≡1 (mod 2)より、
b^(pq)±1にはb±1にはない奇数の素因数が必ず存在する。
このことを踏まえると、以下のような構成が出来る。
e=(pq)^(n+2)とおく。すると素数r(i),s(i)達を下記のようにとれる。
r(i)はpq^((pq)^(i+1))-1を割り切るが、pq^((pq)^i)-1を割り切らない奇素数。
s(i)はpq^((pq)^(i+1))+1を割り切るが、pq^((pq)^i)+1を割り切らない奇素数。
上記のようにおくと、(pq)^e-1を割り切る相異なるn+2個の素数r(i)達と
(pq)^e+1を割り切る相異なるn+2個の素数s(i)達を構成できる。
またgcd((pq)^e+1,(pq)^e-1)=2だから、r(i)達とs(i)達も相異なることわかる。
以上より、aは中国剰余定理より存在が言える。 あと個人的な推測だが、たぶん>>713氏の回答には表向きでは使われてないけど
Zsigmondyの定理が背景にあると思った。
折れも考えてみたけど、>>713と似たものになっちまったw
折れも>>713もZsigmondyの定理の使用を表向きには避けたため、
eの値は非常に大きなものになっている。
Zsigmondyの定理を用いれば、eの値は大分小さくなると思う。
興味がある人はチャレンジしてみるといいんじゃないかな。
Zsigmondyの定理のステートメント
https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem >>724の補足だが
>折れも考えてみた
これはZsigmondyの定理を用いないeの構成方法 〔ジグモンディの定理〕
a>b は互いに素な整数、nは正の整数とする。(*)
このとき、a^n−b^n を割り切るが a^k−b^k (1≦k≦n−1) を割り切らないような素数pが存在する。
* 但し、以下の場合を除く。
(n=1, a-b=1) (n=2, a+b=2^k) (n=6, a=2, b=1)
n→2n とすれば・・・・
〔和のジグモンディの定理〕
a>b は互いに素な整数、nは正の整数とする。(*)
このとき、a^n+b^n を割り切るが a^k+b^k (1≦k≦n−1) を割り切らないような素数pが存在する。
* 但し、以下の場合を除く。
(n=3, a=2, b=1)
上記の数を "primitive prime divisor" と呼ぶらしい。 島の形だけ示した宝の地図を提示してその座標を特定する宝探しゲームができないかと思ったが同じ形の島が無限個あるからだめだった 色んな方法があるんだね
けどやはり算術級数定理を使うのが1番シンプルと思った まぁそうだな。
オレは素数定理使えばいいと思うんだけど出題者が「使わない方がなお良い」って言ってるからなぁ。
素数定理使っていいなら>>713で先にqi,riとって後でp,qとってeなんか全く必要なくなるし。 >>728
もし、良かったら解答書いてくれないかな。
折れ自身、まず算術級数定理を使おうとしたけど、どうしてもうまくいかずに挫折したんだ。
方針転換して、解答>>710-711を見つけたがw ヨコだけど>>713でまず任意に相異なる奇素数ri,si (0≦i≦n+1)を先にとっておいて、それから任意に別の奇素数p>nをとり、最後にq>pを算術級数の素数定理で
pq ≡ 1 (mod ri)、pq ≡ -1 (mod si)
ととればe=1である解を与える。 >>731
それそれ。中心のX座標を2素数の積の形にできる。 >>710
>rより小さな任意の素数sに対して
>a≡1 (mod s)
これで逃げられるならこのほうが賢いわな 先月号出題2の(3)の出題者の意図した解は多分下記だと思う。
>>713や>>722と同様にまず素数r(i)とs(i)を決めてやって
上記の素数とは別にnより大きな素数pをとる。
最後にpq≡1 (mod r(0)…r(n+1) )、pq≡-1 (mod s(0)…s(n+1) )
みたす整数qを中国剰余定理より求める。
>>731氏がやった通り、算術級数定理よりqの値を素数にすることができる。
(たぶんこれが、出題者の意図した算術級数定理を用いた解答)
ただ実はqが素数である必要は実はなく、qがn以下の素数で割り切れなければ
題意を満たすことが言える(その際に>>693と似た議論を用いる)。
例えばn以下の任意の素数tに対してさらにq≡1 (mod t)をみたす。
ように正の整数qをとればよい。
(そしてこれが、たぶん出題者の意図した算術級数定理を用いない解答) あと、>>735で「n以下の任意の素数t」と書きましたが、
勿論、tはr(i),s(i)以外の値をとりますw >>738
え?締め切り翌日には掲載されてたけど。 今月のエレ解、「数学」とか「エレガント」のタグがついてないね >>714
個人的にはなかなか楽しめた問題だったわ。 これならどうなるでしょう?
485132人目の素数さん2020/07/22(水) 09:39:00.16ID:h9mML7y2>>486>>487
今月のエレガントな問題を少し変更したやつ
[x]はx以下の最大の整数
[[x]]はx以上の最小の整数
logは自然対数とする
n≧2のとき、次は常に成り立ちますか?
[2^(1+1/n)/(2^(1/n)-1)]=[[2n/log2]] >>745
解けるよ。解き方は元の問題とほぼ同じだからここには書かないけど。
ていうか、これどこのスレ? >>747
うーん、本当に同じ手法で解けたんだけどな。俺何か勘違いしてるかなあ。ただ、かなり邪道な手法だが。
締切以降に書くわ。 >>748
そうか、自分が勘違いしてる可能性もある
締切後、解答頼む ■ このスレッドは過去ログ倉庫に格納されています