-
- いいね！2
まる
@ps_maru
P(16,9)→(A2 B5 C1 D1 E4 F3)でABCD,AEF,BE,BCF,CDEF P(23,13)→(A3 B7 C2 D1 E6 F4)でABCD,AEF.BE,BCF,CDEF あたりのアルゴリズムが常に5回のヒントかも？ #プリクラ問題
2015-01-10 10:25:30
小金井ささら | ユキちゃんかわいい
@kgneissr
@ps_maru ( am(m-1)+m^2-m+1=(a+1)m^2-(a+1)m+1だから am^2-am+mとAm^2-Am+1になる……？ ) #プリクラ問題
2015-01-10 13:49:09
まる
@ps_maru
@kgneissr そうです。先に後者の形で予想が立って(今のところ全成立)、aを0以上の整数に統一して前者の書き方になりました。 #プリクラ問題
2015-01-10 13:54:01
まる
@ps_maru
r≦7/4のとき、B≒m/4 C≒m/4 D≒m/4 E≒m/2 F≒m/2と分ければBCF,BDE,CDE,BDF,EFの5回でいけることがわかったけど、5回の上限ってr≦9/5だからもうちょっといけるんだよなあ……。 #プリクラ問題
2015-01-10 14:00:08
まる
@ps_maru
@kgneissr 予想が正しければ、その2通りで成立することは巡回群のようになってmodをうまいこと使えば示せるような雰囲気がありますが、それ以外では成立しないことを示すのはかなり難しそうです:;(∩´﹏`∩);:むしろ今まで巡回群を使わずに済んだのが恐ろしい… #プリクラ問題
2015-01-10 14:09:43
まる
@ps_maru
r=9/5で成り立てばいいのだが、r=9/5で参考にできるのがP(9,5)の場合しかなくて、 (A1 B1 C1 D2 E2 F2)で組を分けてABCD、AEF、BEF、CDE、CDFの5回あればできる。これをr≦9/5に一般化しようとしてるなう。誰かへるぷ。。。 #プリクラ問題
2015-01-10 14:20:57
まる
@ps_maru
5/3＜r≦9/5のとき A≦B≦C≦D≦E≦F、A≒m/5 B≒m/5 C≒m/5 D≒2m/5 E≒2m/5 F≒2m/5となるよう分けると、ABCD,AEF,BEF,CDE,CDFの5回でいける！！これだ！！ #プリクラ問題
2015-01-10 14:34:43
まる
@ps_maru
@kgneissr 端数処理はnの偶奇でAを0か1に調整してできそうな雰囲気です。それよりも、今回はnが9m/5を1でも超えた場合にできないことの証明が大変そうです……。 #プリクラ問題
2015-01-10 19:25:03
小金井ささら | ユキちゃんかわいい
@kgneissr
#プリクラ問題 5/3＜r(=n/m)≦9/5のときA:B:C:D:E:F=1:1:1:2:2:2の6グループに分けるやり方を具体的に示そう。 n/m=9/5のときできることを示せばいい。
2015-01-10 19:38:21
小金井ささら | ユキちゃんかわいい
@kgneissr
#プリクラ問題 m=5kのときn≦9k、それぞれk:k:k:2k:2k:2k以下(以下同様) m=5k+1のときn≦9k+1、k:k:k+1:2k:2k:2k m=5k+2のときn≦9k+3、k:k:k+1:2k:2k+1:2k+1
2015-01-10 19:47:03
小金井ささら | ユキちゃんかわいい
@kgneissr
#プリクラ問題 m=5k+3のときn≦9k+5、k+1:k+1:k+1:2k:2k+1:2k+1 m=5k+4のときn≦9k+7、k+1:k+1:k+1:2k+1:2k+1:2k+2 これで確かに撮れる。
2015-01-10 19:47:09
まる
@ps_maru
3回のときはA:B:C≒1:1:1でA=floor(m/2),C=m-Aの順で決めてB≦m/2。4回のときはA:B:C:D≒1:1:1:2でやはりA=floor(m/3),C=m-Aの順で一番下と一番上を決めたあと、B=floor(2m/3)を決めてC≦2m/3。 #プリクラ問題
2015-01-10 19:55:50
まる
@ps_maru
4回までは重複がないのでrが上限を超えるとその回数ではできないということが判明していますが、5回からはアルゴリズムでも重複が出てしまうので、それ以外にもっと少ない回数でできるかどうかは示せていません……。このままではP(46,25)も上界6を与えるにとどまりそう。 #プリクラ問題
2015-01-10 19:58:16
小金井ささら | ユキちゃんかわいい
@kgneissr
そういえば、だけど 一般の正の有理数kではP(n,m)=P(kn,km)は不成立なんだよね確か #プリクラ問題
2015-01-10 20:10:31
小金井ささら | ユキちゃんかわいい
@kgneissr
#プリクラ問題 特定の回数で撮れることを示すには実際に撮り方を提示すればいいけど、特定の回数で撮れないことを示すのは大変だ……
2015-01-10 20:15:18
小金井ささら | ユキちゃんかわいい
@kgneissr
#プリクラ問題 n/m＞9/5として、m mod 5で場合分けして順次P(n,m)≧[(n/m)[(n-1)/(m-1)]]に当てはめてみよう。 m=5kのときn＞9k、P(n,m)＞[(9k/5k)[(9k-1)/(5k-1)]]≧4 ……あれ？
2015-01-10 20:27:50
小金井ささら | ユキちゃんかわいい
@kgneissr
単純にn/mで分類するのがうまくいかない場合があるのは、下界[(n/m)[(n-1)/(m-1)]]がn/mの繰り上がりと(n-1)/(m-1)の繰り上がりのタイミングが微妙に違うせいで2段階で繰り上がるからか n/mより(n-1)/(m-1)のほうが僅かに早い #プリクラ問題
2015-01-10 20:43:50
小金井ささら | ユキちゃんかわいい
@kgneissr
#プリクラ問題 とりあえずさっきの表の「1」の分布について、 縦にa個並ぶ→1行0が入る→a個並ぶ→0が入る→……といった具合で1が並んでる a=1のライン、a=2のライン、……と何本もの線が描かれてる
2015-01-10 22:16:04
小金井ささら | ユキちゃんかわいい
@kgneissr
@ps_maru 式で表すと[(n/m)[(n-1)/(m-1)]]-n(n-1)/m(m-1)の表ですっ 繰り上がりのタイミングのずれを表にしてみようとしたものですっ #プリクラ問題
2015-01-10 23:11:11