X
トップページ⇒数学
1002コメント415KB
【数セミ】エレガントな解答をもとむ3【2018.10】
レス数が1000を超えています。これ以上書き込みはできません。
0953１３２人目の素数さん垢版2021/06/09(水) 10:16:12.64ID:W7KpASHn
エレガントで無くていいから
まず解けな
注目する点を間違ってるぞ
　




　
0955１３２人目の素数さん垢版2021/06/10(木) 09:12:11.83ID:wOdXYdYP
2021年６月号

■出題１
(1) は あと回し。
(2)
O以外の格子点
　A(a1,a2)　B(b1,b2)
に対して
　C(c1,0) c1 = (a1)^2 + (a2)^2 = OA^2,
　D(d1,d2)　d1 = a1b1+a2b2,　d2=a1b2-a2b1,
とおくと、3平方の定理より
　OC/OA = OD/OB = CD/AB = OA,
∴　⊿AOB ∽ ⊿COD　　　(相似)
∴　θ = ∠AOB = ∠COD = ∠D'OD,
D'(d1,0) はDからx軸に下した垂線の足。
∴　θ=∠AOB ならば、θを内角とする直角三角形の
直辺の比 (つまり tangent) は整数比をなす。
逆は明らか。

(1)　上手いやり方が見つからない…
格子点 A(x,0)　B(x,y)　(y≠0)
が ∠AOB=θ を満たすとする。さらに
　C(xx-yy, 2xy)
　D(x(xx-3yy), (3xx-yy)y)
とおく。
　⊿AOB ∽ ⊿BOC ∽ ⊿COD,
　∠AOB = ∠BOC = ∠COD,
　∠AOD = ∠AOB + ∠BOC + ∠COD = 3θ,
θ=60° とすると Dはx軸上にあるから
　(3xx-yy)y = 0　かつ　y≠0
∴　3xx = yy,
左辺の3の指数は奇数、右辺の3の指数は偶数(0も含む)
∴　これを満たす格子点(x,y)は存在しない。
かなり牛刀だなぁ。
0956１３２人目の素数さん垢版2021/06/10(木) 18:43:37.15ID:wOdXYdYP
2021年６月号

■出題２
・n=2 と n=4 は (1)は可能、(2)は不可能。
　タイルの総数m ≦ [nn/3]
　奇数行、奇数列のマス目の数 [(n+1)/2]^2 ≦ m,
∴　[(n+1)/2]^2 ≦ [nn/3]
・n=3 と n=5 は不可能。
・n=6n' は 2x3 ブロックを縦横に並べればよいので、全Lで可能。
・n=7 は L +1S で可能。
・n=3n'+1 は 3n'-1 に2行2列(全L)を追加して可能。
・n=3n'+2 は 3n' に2行2列(∋1S)を追加して可能。
・n=6n'+3 は 6n'+1 に2行2列(∋2S)を追加して可能だが、
　S型を減らせないので (2)では使えない。
これらより
　nが6以上の偶数のときは可能。
　nが7以上の奇数のときは (1)は可能、(2)は？
以上まとめて
(1)　n=3, n=5 以外のすべて
(2)　6以上の偶数と7と…？
0962１３２人目の素数さん垢版2021/06/10(木) 23:50:24.63ID:XvcT0GX9
あとn=5の時に不可能である事を示すのは(1)の方が難しい
不可能性の証明は(1)の方が難しくなるけど、そもそも不可能であるのがちょっとしかないからなぁ
0965１３２人目の素数さん垢版2021/06/11(金) 06:38:13.23ID:ti7gUo9H
オレ的なキーは
2×5, 7×7, 5×9
が見つけられるかどうかがだった様な気がする
m×nまで解決するには4×7もミソ

┏━┳━┳━━┳━┓
┃　┃　┃　　┃　┃
┃　┃　┣━┳┫　┃
┣━┻┳┫┏┫┗┳┫
┃　　┃┗┫┗┳┛┃
┗━━┻━┻━┻━┛
┏━━┳━┳━┓
┃　　┃　┃　┃
┣┳━┫　┃　┃
┃┗┓┗┳┻━┫
┣━╋━┫　　┃
┃　┃　┣━━┫
┃　┃　┃　　┃
┗━┻━┻━━┛
┏━━┳━┳━┓
┃　　┃┏┻┓┃
┣┳━╋┻┓┣┫
┃┗┓┗┓┣┛┃
┗━┻━┻┻━┛
┏┳━┳━┓
┃┗┓┗┓┃
┗━┻━┻┛
0966１３２人目の素数さん垢版2021/06/11(金) 20:04:12.04ID:q8bkQe7j
(2)の条件を緩めて

S字ブロックは2個以内

としてm×nて分割可能てある場合について考える

Prop 2×n (n-=3,n≧5)、3×2n (n≧1)は全て可能
∵ ) 前半は2×3,2×5,2×7可能であることから容易
後半は自明

Prop m≧n≧4のとき(m,n) = (4,4), (5,5), (5,7)を除いて全て可能

∵ ) (m,n)が分割不可能なら(m-6,n)も分割不可能であるから最小反例があるとすればm≦9であるか、(m,n) = (10,4),(11,5),(13,5),(11,7)のいずれかであるが、コレらの場合は下の計算と分割例で反例足り得ないとわかる
(式の意味はエスパーすべし)

(4,4) = impossible
(4,5) = (2,5)+(2,5)
(4,6) = any × 6m
(4,7) = (4,7)
(4,8) = ((2,3)+(2,5))+((2,3)+(2,5))
(4,9) = even × 3n
(5,5) = impossible
(5,6) = any × 6n
(5,7) = impossible
(5,8) = (2,3)+(2,5)+(3,8)
(5,9) = (5,9)
(6,6) = any × 6n
(6,7) = any × 6n
(6,8) = any × 6n
(6,9) = any × 6n
(7,7) = (7,7)
(7,8) = (4,7)+(4,7)
(7,9) = (2,9)+(5,9)
(8,8) = (2,3)+(2,5)+(6,8)
(8,9) = even × 3n
(9,9) = (4,9)+(5,9)

(4,10) = (4,7)+(4,3)
(5,11) = (5,2)+(5,9)
(5,13) = (5,2)+(5,2)+(5,9)
(7,11) = (7,4) + (7,7)
0967１３２人目の素数さん垢版2021/06/11(金) 20:04:40.00ID:q8bkQe7j
9×5
┏━┳━┳┳━┳━┓
┣┓┣┓┃┗┓┣┓┃
┃┗┫┗╋━╋┫┗┫
┣┳┻┳┫┏┫┗┳┫
┃┗┓┃┗┫┗┳┛┃
┗━┻┻━┻━┻━┛
7×7
┏┳━┳━┳━┓
┃┗┓┣┓┣┓┃
┣┳┻┫┗┫┗┫
┃┗┓┗┳╋━┫
┣━╋━┫┗┓┃
┣┓┣┓┣┳┻┫
┃┗┫┗┫┗┓┃
┗━┻━┻━┻┛
7×4
┏┳━┳━┳━┓
┃┗┓┃┏┻┓┃
┣┳┻╋┻┓┣┫
┃┗┓┗┓┣┛┃
┗━┻━┻┻━┛
7×2
┏┳━┳━┳━┓
┃┗┓┗┓┗┓┃
┗━┻━┻━┻┛
5×2
┏┳━┳━┓
┃┗┓┗┓┃
┗━┻━┻┛
0968１３２人目の素数さん垢版2021/06/11(金) 21:42:21.92ID:q8bkQe7j
訂正
(7,8) = (2,7) + (6,7)

ちなみに逆、すなわち(4,4),(5,5),(5,7)のとき不可能の証明はエレガントと呼べる解答は持ってない
使用するSブロックの位置でコツコツ場合わけする方法しか知らない
少なくとも(4,4),(5,5)で不可能は出題されてる内容に含まれてるので答えないと解答としては完成してない
0970１３２人目の素数さん垢版2021/06/11(金) 23:13:50.42ID:q8bkQe7j
おお、やっぱりこういう解答があったか
５×７だと同じように塗って12枚必要になるから不可能と示せるな
0971１３２人目の素数さん垢版2021/06/14(月) 20:59:31.06ID:IKVeisyG
m×n の長方形の場合
タイルの総数 ≦ [mn/3]
奇数行目、奇数列目のマスの数 = [(m+1)/2][(n+1)/2]
∴　[(m+1)/2][(n+1)/2] ≦ [mn/3]
m,n とも奇数の場合は
　(m+1)(n+1)/4 ≦ mn/3,
　(m-3)(n-3) ≧ 12,
∴　m=3 または n=3 または (5,5) (5,7) (7,5) の場合は敷き詰め不可能。
0972１３２人目の素数さん垢版2021/06/14(月) 21:16:24.45ID:V4bBAB96
オレの答えと違うな
m×nの場合で(2)を同じ向きのSブロック2回までと拡張して

m×n (m≧n)が敷き詰め可能
⇔
n=2, m≠2,4 または
n=3, m:偶数 または
n=4, m≠4 または
n=5, m≠5, 7 または
n≧6

になった
0973１３２人目の素数さん垢版2021/06/18(金) 19:27:49.77ID:wKdBkQ65
　


エレガントで無くていいから


まず解けな



注目する点を間違ってるぞ
　




　
0986１３２人目の素数さん垢版2021/07/11(日) 22:12:01.41ID:eAUQRtpO
とりあえず概略

区間[λ,ρ]に対して中点録Mnを
M0 = {λ,ρ},
M1 = {λ,λ#ρ,ρ},
Mn = {λ,λ#(λ#ρ),λ#ρ,(λ#ρ)#ρ,ρ},
‥
とM0から始めて前のリストの隣接する2数の中点を追加して得られる有理数の集合を考える
あるMnの隣接する2点として現れる２つの有理数をIにおいてある時点で隣接すると呼ぶ
区間I=[b/a,d/c]が|ad-bc|=1の時よい区間と呼ぶ

命題　I=[q/p,s/r]、J=[b/a, d/c]がともによい区間の時
fIJ(x) = (b(rx -s) + d(px-q))/(a(rx-s)+c(px-q))
である
∵) 右辺をf(x)とおく
行列A = [[p,-q],[r,-s]], B=[[d,b],[c,a]]の引き起こす一次変換は格子点の間の全単射を引き起こす
また有理数v/uに対しBA[[v],[u]] = [[v'],[u']]の時f(v/u) = v'/u'であり、v/uが既約分数ならv'/u'も既約分数となる
よってv/u、t/sが既約分数でBA[[v],[u]] = [[v'],[u']]、BA[[t],[s]] = [[t'],[s']]の時BA[[v+t],[u+s]] = [[v'+t'],[u'+s']]でありv'/u'、t'/s'も既約分数で
f(v/u) # f(t/s)
= (v'+t')/(u'+s')
= f((v+t)/(u+s))
=f(v/u # t/s)
により主張が成り立つ

補題
I,Jを区間、λ,ρがある時点でIの隣接する2点でありfIJ(λ) = μ、fIJ(ρ) = νとするとき任意のx∈[λ,ρ]に対してfIJ(x) = f[λ,ρ][μ,ν](x)である
∵) 容易

補題
Jを区間でb/a∈Jが最大元でないとする
この時ある時点でb/aで右側に隣接するd/cが存在して|ad-bc|=1となる
∵)ある時点でb/aと右側で隣接するd/c全体の中で|ad-bc|が最小となるものをとり|ad-bc|>1と仮定する
ad-bcの素因子とすれば(a,b)と(c,d)はFp係数で平行だから正の数kを(c,d)+k(a,b)≡(0,0) (mod p)となるように取れる
d/cから始めてb/aとの中点を取る操作をk回行うと(bk+d)/(ak+c)でありg=(bk+d,ak+c)>0, c'=(ak+c)/g, d'=(bk+d)/gとおけばd'/c'はb/aと左側で隣接し|ad'-bc'|=|ad-bc|/gとなり矛盾する
0987１３２人目の素数さん垢版2021/07/11(日) 22:12:09.88ID:eAUQRtpO
主張
Iがよい区間、Jを一般の区間にとる
Iの点χが最大元でなければχと右側である時点で右側で隣接するξが存在してfIJは[χ,ρ]において一次分数関数である
同様の主張が最小元でない元の左側で成り立つ
∵) fIJ(χ)=b/aとしてb/aの右側である時点で隣接するd/cをとる
fIJ(ξ)=d/cとなるξをとればよい

主張
Iがよい区間、Jを一般の区間にとる
χ=v/uをIの内点にとりζ、ξ∈IをfIJが[ζ,χ],[χ,ξ]において一次分数関数となるようにとる
この時fIJのx=χにおける左側、右側微分係数は一致する
∵) fIJ = f とおく
I = [0,∞]、χ=1、ζ=0、ξ=∞として一般性を失わない
f(0) =b/a、f(1)=d/c、f(∞)=f/eとする
[0,1]においてf(x)=(b+(d-b)x)/(a+(c-a)x))、
[1∞]においてf(x)=(fx+(d-f))/(ex+(c-e))、
である
上の右辺をg(x)、下の右辺をh(x)とおくときg(1)=h(1)であるよって(log(g))'(1)=(log(h))'(1)を示せばよいが、ともに-/(cd)である
0988１３２人目の素数さん垢版2021/07/12(月) 11:50:52.10ID:SZPGMf+k
　　　


エレガントで無くていいから


まず解けな



注目する点を間違ってるぞ
　




　
0991１３２人目の素数さん垢版2021/07/12(月) 23:13:12.50ID:rkg/Cex9
>>990
要するにこの問題はそこがミソ
有理数b/aを座標平面の格子点(a,b)に対応させて考える
すると1/2と3/1の中点4/3は(2,1)と(1,3)の和(3,4)を対応させていることになる
なので“中点を保存する写像”とは座標平面上では“和を保存する写像”となりすなわち“一時変換”ということになる
なので考えている区間がたとえば[0/1,1/0]から[2/3,3/4]なら(1,0)を(3,2)に、(0,1)を(4,3)に写す線形写像だから行列[[3,4],[2,3]]で表される写像で、y/xを(2x+3y)/(3x+4y)に写す写像だからf(t)=(2+3t)/(3+4t)と求まる
この“一次分数関数”を“行列”で考えるテクニックは超頻出テクニックで最もよく使われるテクニック
有理数近似の理論とか連分数の理論とかで頻出
時々受験数学レベルでも出てくる
ただしこのテクニックがうまく機能するには出てくる行列の行列式が±1出ないとダメで不通その前提条件で考えるけど、この問題はその前提外したらどうなりますかというお話
このテクニック知ってる人間ならその“出題者の意図”が透けて見えるので考えるべきポイントもすぐわかる
逆にコレ知らないと中々手でないかもね
10011001垢版Over 1000Thread
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 1034日 21時間 53分 57秒
10021002垢版Over 1000Thread
5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。


───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────

会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。

▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/

▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php
レス数が1000を超えています。これ以上書き込みはできません。
ニューススポーツなんでも実況