X



トップページ数学
1002コメント415KB
【数セミ】エレガントな解答をもとむ3【2018.10】
■ このスレッドは過去ログ倉庫に格納されています
0653132人目の素数さん
垢版 |
2020/06/11(木) 04:05:02.72ID:U1wqDpVl
出題1、結果だけならプログラム組めば出せる
無論、そこにエレガントさはカケラもない。

1から2倍と桁入れ替えで到達可能な数をリストアップすると、以下を除く4桁の数(5558個)になった。
これらが1に到達不可能なことを確かめるのは難しくない。

・3の倍数
・全ての桁が奇数
・全ての桁が2か6
・1114, 1141, 1411, 4111, 1118, 1181, 1811, 8111, 2228, 2822, 2282, 8222, 4444, 8888
0654132人目の素数さん
垢版 |
2020/06/11(木) 04:16:45.02ID:1i56AYPZ
まず、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に到達可能な数という保証ができないな。
0655132人目の素数さん
垢版 |
2020/06/11(木) 04:33:35.28ID:TkJPwCTf
読み直してみると、途中で3桁に落ちるパターンが考慮から漏れているかな。
3桁でも同じようなことを考えることはできそうだが。
0656132人目の素数さん
垢版 |
2020/06/11(木) 09:39:36.05ID:2VKGJNso
・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個
0657132人目の素数さん
垢版 |
2020/06/11(木) 12:35:16.85ID:FIRrnvGD
1/2倍だけではなく2倍の操作も許し、途中で5桁以上になっても良いとすると、1に到達不可能なのは元の数が3で割り切れることと同値なようだ。
(5桁まで膨らむ場合をPCで計算。実は5555のみが例外的に到達不能だったが、桁数を増やせば行けるんじゃないか。)

つまり、桁数を無視すると(1)(2)でつながるネットワークの頂点はmod3=1,2の集合ということになる。

あとはその中から2倍操作をしなくても1に到達するものを選ぶという話になるな。
0658132人目の素数さん
垢版 |
2020/06/11(木) 12:46:44.82ID:FIRrnvGD
>>657
5555も6桁使えば行けたわ。

5555 (×2^5)->177760->177706->88853->53888->26944->24496->12248->6124->1624->812->128->略
0659132人目の素数さん
垢版 |
2020/06/11(木) 14:03:33.02ID:8Ty+yyMM
いまどきは 蜂の巣原理 というのか
0660132人目の素数さん
垢版 |
2020/06/11(木) 14:18:21.90ID:TS8a5l3a
うん、鳩の巣原理だな
全桁奇数は回避できるが無限ループで1に到達できず、という可能性を排除できないけどなんかいえねーかなーと……
0662132人目の素数さん
垢版 |
2020/06/12(金) 21:34:07.64ID:MxsSZpyi
でも蜂の巣って一つの巣に何百何千の蜂が住んでいらっしゃるから
本来の鳩ノ巣原理のニュアンスとは違ってこなくないかい
0667132人目の素数さん
垢版 |
2020/06/13(土) 10:17:46.82ID:KjHAbDUS
日本語の鳩ノ巣じゃまずいから引き出し論法にしたのかもしれんが、もっとまずいだろ

それに比べて蜂の巣はどうだ
穴と蜂の対応関係が絶妙にイメージしやすいではないか
0668132人目の素数さん
垢版 |
2020/06/13(土) 10:19:03.33ID:KjHAbDUS
正直ピーターは手も足も出ず、こんなコメントしかできないのが恥ずかしいわ
0669132人目の素数さん
垢版 |
2020/06/13(土) 10:29:15.79ID:KjHAbDUS
ちなみに俺のアプローチを言うと、4桁から3桁へ、3桁から2桁へ移る数のうち、1へ到達可能な数を調べ上げた

例えば2桁の数は58,61,64,85,92に限られるので、
÷2でこれらに移行できる3桁の数Tは上の5数の2倍。
同様にして、最終的に上の3桁5数に到達できる4桁の数Qも多少の根気で調べ上げることができる(1000以上1999以下)

あとはQに到達できる4桁の数を網羅すればよい
この網羅は全く容易でない
ゆえにこれらの努力が無駄であることが示された(証明終)
0670132人目の素数さん
垢版 |
2020/06/13(土) 15:25:08.11ID:PwdDNtuf
蜂の巣というたらあのでっかい塊のこと
巣と巣穴を混同してはいけない

だから蜂の巣穴論法というべき
0675132人目の素数さん
垢版 |
2020/06/16(火) 15:11:23.56ID:2YfX/iX0
ワークマンの作業着を着た女子高生に萌える
0677132人目の素数さん
垢版 |
2020/06/17(水) 23:47:40.09ID:NyxAI4wb
どおくまんの男子大学生問題
0685132人目の素数さん
垢版 |
2020/06/22(月) 18:45:51.31ID:TPfYUS8O
>>679 >>680
この話に心当たりがあったのでもうググって答え見た。
資料みて思うにコレは表の存在を自分で導出するのは無理だ。
なんせ表の存在だけで論文になってるレベル。
この表をいかに簡単に作れるかでひとつのテーマになってる。
(1)も(2)も存在しうるならこの2つしかないまでで良いんだろうと思う。
0686132人目の素数さん
垢版 |
2020/06/22(月) 22:09:11.35ID:nOEAAo4S
先月号の出題2が全然話題にならないのは
個々の住人には簡単すぎたから?
0687132人目の素数さん
垢版 |
2020/06/22(月) 22:55:21.87ID:dX9g2rrw
>>686
早々に解けたことは覚えてるけど全く記憶にない
簡単すぎたのか、ピーターに時間を費やしすぎたか
0688132人目の素数さん
垢版 |
2020/06/22(月) 22:58:09.25ID:dX9g2rrw
>>687
いま問題見て思い出した
大学受験みたいだなーと思った
こういう問題はツマラン
0690132人目の素数さん
垢版 |
2020/06/23(火) 06:17:24.18ID:EJLy4HwQ
先月の出題2は x^2+y^2=z^2 の一般整数解を知ってればつまんない問題ではないかな
交点の確認から外接条件、と誘導もしっかりしてて、あとは計算するだけに見える
0691132人目の素数さん
垢版 |
2020/06/23(火) 17:29:54.58ID:DYKTirLl
この雑誌って完全に数学科向け?
物理出身だが買ってみたいんだか
0693132人目の素数さん
垢版 |
2020/06/23(火) 19:25:40.67ID:F5pXlGP9
出題2の(3)、多分解けた。
条件をみたす「島」を思い付くと意外と気持ち良い。
0694132人目の素数さん
垢版 |
2020/06/23(火) 22:51:05.43ID:3g7BJMko
中学生だけど、愛読してる。うふ
0695132人目の素数さん
垢版 |
2020/06/24(水) 15:16:16.24ID:W2vxdtjk
島の面積としてあり得る数は決定できますか
0696132人目の素数さん
垢版 |
2020/06/24(水) 22:46:45.99ID:LOdimE5b
>>693
早いじゃないか
島であること、有界でないこと、の2ステップだな
なんとなくイケる気がするんだが2トライして失敗
次は何を試そうかなあ(楽しい)
0699132人目の素数さん
垢版 |
2020/06/30(火) 21:34:50.83ID:ECJqkbpx
>>685
Steiner system S(5,8,24) の自己同型群は Mathieu群 M_24 で5重可移なんだね。
しかし一般に、どのようなパラメータに対して block design が存在するか
という問題は非常にむずかしい問題で、Combinatory Analysis のもっとも
重要な問題の一つらしい。。。
0702693
垢版 |
2020/07/05(日) 00:45:59.11ID:izl2mYWJ
>>701
出来たよ。回答は今月8日の締め切り後に出すつもりだけど。
ヒント(といえるかはわからんが)として、明日ぐらいに回答に使った定理ぐらいは書いてもいいよ。
書いて欲しい人がいればの話だけど。
0705132人目の素数さん
垢版 |
2020/07/06(月) 00:30:19.65ID:HPDcrjtp
明日になった。(?)
・中国剰余定理は、主張をきちんと述べれば証明する必要はありません。
・ディリクレの算術級数定理も証明なしに用いて構いませんが、用いないで済めばその方が良しとします。
らしいぞ。
0707132人目の素数さん
垢版 |
2020/07/06(月) 19:54:44.64ID:CzRhbiNT
すまんが706は忘れてくれ
これはヒントだろうか?
否。断じて否である。
0710693
垢版 |
2020/07/09(木) 00:16:57.17ID:kJ0rN7sT
出題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)
0711693
垢版 |
2020/07/09(木) 00:18:02.23ID:kJ0rN7sT
出題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はいくらでも大きくとれるから、いくらでも大きな「面積」の「島」の存在が言えた。
0712693
垢版 |
2020/07/09(木) 00:20:08.67ID:kJ0rN7sT
出題2の(2)は>>710-711でr=2とおけばよい。
0713132人目の素数さん
垢版 |
2020/07/09(木) 01:07:25.61ID:XFAfLnLw
任意の大きさを作る解

補題
自然数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式はユークリッドの互除法によりとれる。
0715132人目の素数さん
垢版 |
2020/07/09(木) 16:50:56.86ID:2IXNWIKB
>>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).
とおく。
0716132人目の素数さん
垢版 |
2020/07/10(金) 14:51:42.70ID:F5aduSPW
作者土岡君か
0719132人目の素数さん
垢版 |
2020/07/10(金) 20:40:26.35ID:zO+7FxbR
数セミ増刊「数学100の問題」日本評論社 (1984)
 p.60-61 (山本幸一)

中村義作ほか:「数理パズル」中公新書 (1976)
 p.178-187

別冊 数理科学「群とその応用」サイエンス社 (1991)
 p.36-40 (永尾 汎)  p.150-158 (景山三平)

永尾 汎:「群とデザイン」岩波 数学選書 (1974)
0722693
垢版 |
2020/07/11(土) 02:10:00.43ID:Xb1OTyfv
折れも任意の自然数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の要素である。
0723693
垢版 |
2020/07/11(土) 02:24:38.65ID:Xb1OTyfv
あとは、♪が実際に構成可能であること。
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は中国剰余定理より存在が言える。
0724132人目の素数さん
垢版 |
2020/07/11(土) 02:37:12.16ID:Xb1OTyfv
あと個人的な推測だが、たぶん>>713氏の回答には表向きでは使われてないけど
Zsigmondyの定理が背景にあると思った。
折れも考えてみたけど、>>713と似たものになっちまったw

折れも>>713もZsigmondyの定理の使用を表向きには避けたため、
eの値は非常に大きなものになっている。
Zsigmondyの定理を用いれば、eの値は大分小さくなると思う。
興味がある人はチャレンジしてみるといいんじゃないかな。

Zsigmondyの定理のステートメント
https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem
0725132人目の素数さん
垢版 |
2020/07/11(土) 02:40:24.21ID:Xb1OTyfv
>>724の補足だが
>折れも考えてみた
これはZsigmondyの定理を用いないeの構成方法
0726132人目の素数さん
垢版 |
2020/07/11(土) 07:05:15.58ID:ZnhtLn45
〔ジグモンディの定理〕
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" と呼ぶらしい。
0727132人目の素数さん
垢版 |
2020/07/11(土) 15:52:13.30ID:4lYEolum
島の形だけ示した宝の地図を提示してその座標を特定する宝探しゲームができないかと思ったが同じ形の島が無限個あるからだめだった
0728132人目の素数さん
垢版 |
2020/07/12(日) 08:37:42.29ID:TfKcF3sP
色んな方法があるんだね
けどやはり算術級数定理を使うのが1番シンプルと思った
0729132人目の素数さん
垢版 |
2020/07/12(日) 08:47:35.38ID:lCCkuzVr
まぁそうだな。
オレは素数定理使えばいいと思うんだけど出題者が「使わない方がなお良い」って言ってるからなぁ。
素数定理使っていいなら>>713で先にqi,riとって後でp,qとってeなんか全く必要なくなるし。
0730693
垢版 |
2020/07/13(月) 06:18:19.18ID:r0ffJNeq
>>728
もし、良かったら解答書いてくれないかな。
折れ自身、まず算術級数定理を使おうとしたけど、どうしてもうまくいかずに挫折したんだ。
方針転換して、解答>>710-711を見つけたがw
0731132人目の素数さん
垢版 |
2020/07/13(月) 12:32:27.91ID:tR49RdlH
ヨコだけど>>713でまず任意に相異なる奇素数ri,si (0≦i≦n+1)を先にとっておいて、それから任意に別の奇素数p>nをとり、最後にq>pを算術級数の素数定理で
pq ≡ 1 (mod ri)、pq ≡ -1 (mod si)
ととればe=1である解を与える。
0733132人目の素数さん
垢版 |
2020/07/13(月) 19:50:25.83ID:qNTcwU4s
>>710
>rより小さな任意の素数sに対して
>a≡1 (mod s)

これで逃げられるならこのほうが賢いわな
0734693
垢版 |
2020/07/14(火) 01:34:46.10ID:L+AsbTGF
>>731
ありがとう
0735132人目の素数さん
垢版 |
2020/07/15(水) 01:51:09.43ID:5dJcX4Gp
先月号出題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をとればよい。
(そしてこれが、たぶん出題者の意図した算術級数定理を用いない解答)
0736132人目の素数さん
垢版 |
2020/07/15(水) 05:09:10.83ID:5dJcX4Gp
× >>713>>722と同様に
〇 >>713>>722
0737132人目の素数さん
垢版 |
2020/07/15(水) 05:12:22.69ID:5dJcX4Gp
あと、>>735で「n以下の任意の素数t」と書きましたが、
勿論、tはr(i),s(i)以外の値をとりますw
0743132人目の素数さん
垢版 |
2020/07/21(火) 22:14:25.83ID:+NGICN8G
正解者がとっても少ないの
0745132人目の素数さん
垢版 |
2020/08/06(木) 19:52:51.24ID:1/AtprVO
これならどうなるでしょう?

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]]
0746132人目の素数さん
垢版 |
2020/08/06(木) 20:25:33.99ID:zAQTDrQb
>>745
解けるよ。解き方は元の問題とほぼ同じだからここには書かないけど。
ていうか、これどこのスレ?
0748132人目の素数さん
垢版 |
2020/08/06(木) 21:08:53.87ID:zAQTDrQb
>>747
うーん、本当に同じ手法で解けたんだけどな。俺何か勘違いしてるかなあ。ただ、かなり邪道な手法だが。
締切以降に書くわ。
■ このスレッドは過去ログ倉庫に格納されています

ニューススポーツなんでも実況