☆郵便切手の問題☆

☆郵便切手の問題☆ at MATH

274:１３２人目の素数さん
09/03/06 08:25:07
290

275:１３２人目の素数さん
09/03/10 15:13:50
age

276:１３２人目の素数さん
09/03/10 19:30:48
これって左端が一番上としているけど
それをどうでもよくした場合
かんたんになりますか？

277:１３２人目の素数さん
09/03/10 19:54:46
ならんような気はするな。

278:１３２人目の素数さん
09/04/26 00:35:36
236

279:１３２人目の素数さん
09/06/03 05:57:44
>>277
反論と言うわけではないんだけど
どうして自由に折り曲げるのではなくて
端をいちばん上にしたものだけを特別視するんだろう？

もし同じくらいの難易度ならば、端が上かどうかをどうでもよくしたほうが
（つまり制約が少ないほうが）いい問題のように思えるんだ。

280:１３２人目の素数さん
09/07/10 09:00:08
678

281:１３２人目の素数さん
09/08/10 11:40:35
これ、なんのスレッドなの？

282:１３２人目の素数さん
09/08/10 12:42:26
１から嫁

283:１３２人目の素数さん
09/09/02 20:29:27
切手も紙くずになるんですね。切手がペリカンと統合で郵パックで使えなくなるらしいですよ・・・
10月からしいですが、郵パック用に購入した大量の切手、郵便局のほうで
買取とかしてくれるんでしょうか?

284:１３２人目の素数さん
09/09/07 05:27:10
六年。

285:１３２人目の素数さん
09/09/17 01:12:49
探索アルゴリズムすらも書かれてないようなのでひとつ考えてみよう。

これ、>>39 の図のように
「折り目も縦辺としての１手」と考えた方が判りやすい気がした。
つまり >>39 を９手後の図と考える。
すると探索アルゴリズムは少し単純化される。

始点の座標を (0, 0)、y の正が上方向、
k 番目の横辺の始点の x 座標を x[i]、
k 番目の縦辺の始点の y 座標を y[i] とする。

すると以下の拘束条件が導ける：
(1) 全ての i, j において x[2i] < x[2j+1] (「一枚の切手の上に全て折り込む」の法則)
(2) 全ての i, j において {
　　x[2i] < y[2j] < x[2i+1] なら {
　　(y[2j] > y[2i] かつ y[2j+1] > y[2i])、または
　　(y[2j] < y[2i] かつ y[2j+1] < y[2i])
　}
}(縦辺と横辺が交わらない法則)
(3) 全ての i において y[i]<0（「左端の切手が一番上」の法則）

この３つの拘束条件を満たす全ての図形の横辺だけを取り出ししたものは
全て「切手問題の解」の形に変換できるだろう。(*1)
かつそれは切手問題の解の全パターンを含むだろう。 (*2)

（つづく）

286:１３２人目の素数さん
09/09/17 01:13:51
(>>285 のつづき)

次に、x,y ∈ R のままでは無限の重複があるので、
x は互いに重複なしの整数の組み合わせ (N/2)! 通りのパターン、
y は互いの重複を許す整数の組み合わせ 2^(N/2-1) 通りのパターンを考えて、
その直積の (N/2)!×2^(N/2-1) 通りを刈り込み前の図形と考えれば
刈り込み後の図形の全ては、「切手問題の全解」と一対一対応するだろう (*3)

まずは (*1), (*2), (*3) が正しいかどうかをチェックして欲しい。
それをとりあえず呑み込んで一般解を導出してもらってもいい。
自分はその間にちょっと探索プログラムでも組んでみようかな…。

287:285
09/09/17 01:27:39
２つもミスった。

――
>>285 の訂正: (添え字の奇遇は問わなかった)
(2) 全ての i, j において {
　　x[i] < y[j] < x[i+1] なら {
　　(y[j] > y[i] かつ y[j+1] > y[i])、または
　　(y[j] < y[i] かつ y[j+1] < y[i])
　}
}(縦辺と横辺が交わらない法則)
――
>>286 の訂正:(x と y が逆だった)
y は互いに重複なしの整数の組み合わせ (N/2)! 通りのパターン、
x は互いの重複を許す整数の組み合わせ 2^(N/2-1) 通りのパターンを考えて、
――

あと、例も書いておくと、
>>39 の図形は >>286 でいうと
上の図形: x=[0,3,1,2,0], y=[0,-3,-2,-1,-4]
下の図形: x=[0,3,1,3,0], y=[0,-2,-3,-4,-1]
に相当する。（最後の辺の終端も数列に入れるかがちょっと微妙だが…）

288:コールセンターのβ
09/09/17 23:53:57
1,2^0
1,2^0
2,2^1
4,2^2
10,2^3+2^1
24,2^4+2^3
66,2^5+2^5+2

289:１３２人目の素数さん
09/09/18 00:58:07
(*3) を満たすにはまだ拘束条件が足りなさそうだ。
(4) 横辺の終点は縦辺に当たるところ（or 一番外部）まで伸ばさないといけない
これを入れないと、
Σの形の切手は１パターンだが、それに対応する >>39 式図形は
左にある２つの折り目を表す縦線のどちらがより左にあるか（もしくは同一か）
によって３パターンに分岐してしまう。

290:１３２人目の素数さん
09/12/04 08:43:56
421

291:１３２人目の素数さん
10/01/26 23:12:55
URLﾘﾝｸ(auok.auone.jp)

292:猫は淫獣 ◆ghclfYsc82
10/01/28 13:14:58
去年の秋にワシの友人が出した郵便物がやなァ、
つい先日に約二ヵ月半遅れで先方に届いたっちゅう電話が
あったらしいんですワ。ほんでナ、コレはイカンっちゅう
てやナ、郵便局に調査をして貰うたらやナ、もう封筒が回収
出来へんさかい調査不能っちゅう電話連絡を貰うたんや
所がその直後に問題の封筒が先方から出て来てやね、
ほんで件の郵便局に電話をしたらやね、郵便局側の言い分では
「自分達は嘘は言ってない。彼等は調べても発見出来なかった。」
と回答しましてん。まあ役人っちゅうんは何時もこんな感じ
ですワ。そやし次回はその回収した封筒を弁護士さんの同席と
共に郵便局で交渉っちゅうか議論になるんですかねぇ
切手が80円しか貼ってなかったら2ヶ月以上を要する事もある
っちゅう教訓ですな。

まあ世の中は厄介やなァーーー

猫

293:１３２人目の素数さん
10/03/10 16:31:27
749

294:１３２人目の素数さん
10/05/07 18:29:23
607