[表示 : 全て 最新50 1-99 101- 201- 301- 401- 501- 601- 701- 801- 2chのread.cgiへ]
Update time : 10/02 13:20 / Filesize : 322 KB / Number-of Response : 887
[このスレッドの書き込みを削除する]
[＋板 最近立ったスレ＆熱いスレ一覧 : ＋板 最近立ったスレ／記者別一覧] [類似スレッド一覧]

↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

面白い問題おしえて〜な 十九問目

1 名前：１３２人目の素数さん [2011/11/03(木) 00:12:57.26 ]
過去ログ
www3.tokai.or.jp/meta/gokudo-/omoshi-log/
まとめwiki
www6.atwiki.jp/omoshiro2ch/

1 cheese.2ch.net/test/read.cgi/math/970737952/
2 natto.2ch.net/test/read.cgi/math/1004839697/
3 science.2ch.net/test/read.cgi/math/1026218280/
4 science.2ch.net/test/read.cgi/math/1044116042/
5 science.2ch.net/test/read.cgi/math/1049561373/
6 science.2ch.net/test/read.cgi/math/1057551605/
7 science2.2ch.net/test/read.cgi/math/1064941085/
8 science3.2ch.net/test/read.cgi/math/1074751156/
9 science3.2ch.net/test/read.cgi/math/1093676103/
10 science4.2ch.net/test/read.cgi/math/1117474512/
11 science4.2ch.net/test/read.cgi/math/1134352879/
12 science6.2ch.net/test/read.cgi/math/1157580000/
13 science6.2ch.net/test/read.cgi/math/1183680000/
14 science6.2ch.net/test/read.cgi/math/1209732803/
15 science6.2ch.net/test/read.cgi/math/1231110000/
16 science6.2ch.net/test/read.cgi/math/1254690000/
17 kamome.2ch.net/test/read.cgi/math/1284253640/
18 kamome.2ch.net/test/read.cgi/math/1307923546/

513 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 00:43:11.33 ]
プログラムを組むと確かに、n≧5の場合に解は存在しなかった。
2^x+5^z=3a 3^y+5^z=2b 2^x+3^y=5c から
2^x=(3a-2b+5c)/2, 3^y=(-3a+2b+5c)/2, 5^z=(3a+2b-5c)/2で意味不明w

514 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 01:07:33.14 ]
n≧5の場合に解は存在しないことを
高校生にも分かるように証明お願いします

515 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 04:48:55.84 ]
>>514
Andrew John Wilesにでも会ってこい

516 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 04:49:39.32 ]
あ、すまんフェルマーの最終定理の話じゃなかったのか
515は忘れてくれ

517 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 05:04:45.31 ]
それもまた好々

518 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 14:44:19.74 ]
>>513 追加
(3a-2b+5c)/2>=2, (-3a+2b+5c)/2>=3, (3a+2b-5c)/2>=5
を満たす整数a,b,cの組み合わせは7個、その全てでx=log[2]((3a-2b+5c)/2)が整数に
ならずに不適。

519 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 14:55:42.37 ]
>>518　はx>0,y>0,z>0の場合

520 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 19:56:21.99 ]
>>514
kは非負整数とする
mod 8において、3^2≡1，5^2≡1より
　3^(2k)≡1，3^(2k+1)≡3
　5^(2k)≡1，5^(2k+1)≡5
mod 3において、2^2≡1，5^2≡1より
　2^(2k)≡1，2^(2k+1)≡2
　5^(2k)≡1，5^(2k+1)≡2
mod 5において、2^4≡1，3^4≡1より
　2^(4k)≡1，2^(4k+1)≡2，2^(4k+2)≡4，2^(4k+3)≡3
　3^(4k)≡1，3^(4k+1)≡3，3^(4k+2)≡4，3^(4k+3)≡2

n≧5とすると
n!≡0 (mod 8)，n!≡0 (mod 3)，n!≡0 (mod 5)

x,y,zがいずれも負の整数とならないことの証明はここでは省略して
以下いずれも非負整数とする

(i) x≧3のとき
2^x≡0 (mod 8)より、3^y+5^z≡0 (mod 8)
この条件を満たすのはyもzも奇数の場合のみ
yが奇数で0ではないので3^y≡0 (mod 3)、zは奇数なので5^z≡2 (mod 3)より、
2^x≡1 (mod 3)となり、xは偶数
zが奇数で0ではないので5^z≡0 (mod 5)より、2^x+3^y≡0 (mod 5)
しかし、xが偶数、yが奇数だと、この条件を満たすことができない
よって、このとき与式を満たすx,y,zの組は存在しない
（続く）


521 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 19:57:37.88 ]
（続き）
(ii) x=2のとき
2^x≡4 (mod 8)より、3^y+5^z≡4 (mod 8)
この条件を満たすのはyが奇数、zが偶数の場合のみ
2^x≡1 (mod 3)、yが奇数で0ではないので3^y≡0 (mod 3)より
5^z≡2 (mod 3)となるが、これはzが偶数であることと矛盾
よって、このとき与式を満たすx,y,zの組は存在しない

(iii) x=1のとき
2^x≡2 (mod 8)より、3^y+5^z≡6 (mod 8)
この条件を満たすのはyが偶数、zが奇数の場合のみ
2^x≡2 (mod 5)、zが奇数で0ではないので5^z≡0 (mod 5)より
3^y≡3 (mod 5)となるが、これはyが偶数であることと矛盾
よって、このとき与式を満たすx,y,zの組は存在しない

(iv) x=0のとき
2^x+3^y+5^zは奇数、n!は偶数なので矛盾
よって、このとき与式を満たすx,y,zの組は存在しない




522 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 20:16:51.43 ]
結局答えは
(n,x,y,z)=(3,2,0,0),(3,1,1,0),(4,4,1,1)
の３通りのみ


523 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 20:26:04.23 ]
>>518
＞　(3a-2b+5c)/2>=2, (-3a+2b+5c)/2>=3, (3a+2b-5c)/2>=5
＞　を満たす整数a,b,cの組み合わせ
(a,b,c)が１組でも見つかれば、
(ka,kb,kc)（kは自然数）も不等式を満たすはずなので、
７個だけというのは意味不明

524 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 20:48:06.39 ]
>>523
3つ不等式を満たす整数の点は、3平面がなす四面体の内部の点であり
(a,b,c)=(454, 543, 334),(454,542,334),(453,546,335),
(453,544,334),(453,547,335),(453,545,334),(453,543,333)

525 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 21:07:49.59 ]
四面体ではなく無限に続く三角柱だから、>>518と>>524は間違だった。

526 名前：１３２人目の素数さん mailto:sage [2012/05/13(日) 23:59:26.40 ]
×無限に続く三角柱
○3つの平面により区分けれた領域

527 名前：１３２人目の素数さん mailto:sage [2012/05/18(金) 15:30:16.03 ]
(・3・)

528 名前：１３２人目の素数さん [2012/05/19(土) 11:11:34.19 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

529 名前：１３２人目の素数さん mailto:sage [2012/05/19(土) 22:06:58.43 ]
>>435
　Sが最大のとき、　a,b,c････の差は高々1

(略証)
背理法による。
a,b,････ の中に差が2以上のものがあると仮定する。たとえば
　b-a-1 > 0,
とすると
　(a+1)(b-1) = ab + (b-a-1) > ab,
これは、Sが最大であることと矛盾する。（終）

530 名前：１３２人目の素数さん mailto:sage [2012/05/19(土) 22:47:42.27 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

531 名前：１３２人目の素数さん [2012/05/23(水) 08:14:45.57 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/




532 名前：１３２人目の素数さん mailto:sage [2012/05/24(木) 23:58:06.24 ]
ふむ

533 名前：１３２人目の素数さん mailto:sage [2012/05/25(金) 03:38:28.60 ]
平面R^2をジョルダン閉曲線で過不足無く覆うことは可能か？
ただし「過不足無く」とは、R^2上の任意の点に対しその点を通るものがただ1つある場合をいう。

534 名前：１３２人目の素数さん mailto:sage [2012/05/25(金) 03:40:15.06 ]
>>533の補足。
1個の閉曲線で覆うのではなく、閉曲線の集合を考え、その全体で覆うものとする。

535 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 06:53:09.23 ]
{x^2+y^2=r^2 | r∈R}

536 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 07:32:24.60 ]
{y=(x^3-x+a | a∈R}

537 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 07:46:55.58 ]
>>536は馬鹿

538 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 11:21:16.73 ]
>>536は閉曲線ではなかったので
{x^2/a^2+y^2/(ca)^2=1 | a,c∈R, cは一定}

539 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 11:28:55.12 ]
{x^(2n)+y^(2n)=r^(2n) | n∈N, r∈R, nはn≧1で一定}

540 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 11:35:34.48 ]
点は閉曲線と認めるか

541 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 12:47:42.68 ]
え、これって、どうやっても少なくとも１点は残ってしまうことを
いかにうまく証明するかという話じゃないの？



542 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 13:04:28.08 ]
蚊取り線香とか見たこと無いのか

543 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 13:11:22.88 ]
─┐┌─
┌┘└┐＜呼ばれた気がした
│┌┐│
└┘└┘

544 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 22:19:37.86 ]
（ペアノ君には用はありません）

545 名前：１３２人目の素数さん mailto:sage [2012/05/26(土) 22:28:06.97 ]
(用がないのに来ないでくださいね) ＞ 多くの人々

546 名前：１３２人目の素数さん mailto:sage [2012/05/27(日) 00:26:27.20 ]
せめて、Wikipediaでもいいから、ジョルダン曲線の定義と、
ジョルダン曲線定理の内容ぐらい見てから書き込めばいいのに…

547 名前：１３２人目の素数さん mailto:sage [2012/05/27(日) 02:02:38.63 ]
>>541
ああ、そういう意味か
一点が残ってしまうどころか
ミスると可算無限個の穴ができて
消せなくなったりもするな

548 名前：１３２人目の素数さん mailto:sage [2012/05/27(日) 02:29:03.03 ]
二次元の平面上の原点に蛙がいる。
この蛙、ひょんなことに、有理数度の角度に
有理数 cm の距離を飛ぶことしか出来ない。
この蛙が到達出来ない点の集合は？

549 名前：１３２人目の素数さん mailto:sage [2012/05/27(日) 02:30:28.86 ]
>>547
まあ、１点だけ残る例なら >>535 でr>0とすれば構成できるけど、
必ず１点は残ることをきちんと証明しようとすると、
非可算無限を扱うのでいろいろ工夫がいりそう

自明に思えることがなかなかうまく証明できないという

550 名前：１３２人目の素数さん mailto:sage [2012/05/27(日) 02:43:30.27 ]
>>548
その平面をガウス平面とみなすと、
いかなる円分体にも含まれない点の集合が求める点の集合であろうことはわかるが
それ以上はわからん

が、蛙には大きさがあるので、たぶんどこにでも行けるだろう

551 名前：１３２人目の素数さん mailto:sage [2012/05/27(日) 04:01:00.02 ]
「蛙」という名前のついた「点」、というのが落ちだろうな。



552 名前：１３２人目の素数さん mailto:sage [2012/05/27(日) 05:56:51.79 ]
根性 根性 de 根性 ♪

553 名前：１３２人目の素数さん mailto:sage [2012/05/27(日) 06:03:08.93 ]
>>549
背理法だろ

554 名前：１３２人目の素数さん [2012/05/27(日) 07:34:29.76 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

555 名前：１３２人目の素数さん [2012/05/29(火) 04:32:20.22 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/

556 名前：１３２人目の素数さん mailto:sage [2012/05/29(火) 04:50:24.77 ]
ハイリ ハイリ フレ ハイリ ホー ハッハッハ ハイレ ハイレ フレー ホーホー

557 名前：１３２人目の素数さん mailto:sage [2012/05/29(火) 23:35:27.52 ]
低次元に落としてみれば？

558 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 05:38:05.52 ]
>>533
不可能であることが言えた( ＾o＾)

解答のイメージ：
p∈R^2を1つ取る。
このpを通るジョルダン閉曲線が1つだけ存在する。
この閉曲線の内部から別の点pを1つ取る。
このpを通るジョルダン閉曲線が1つだけ存在する。
この閉曲線の内部から別の点pを1つ取る。
このpを通るジョルダン閉曲線が1つだけ存在する。
……これを繰り返すことで、ジョルダン閉曲線が
内部にどんどん作られていき、「切り株の年輪」のような
模様が作られる。ジョルダン閉曲線を "十分多く作れば" 、
区間縮小法のような感じで、年輪は一点に収束する(本当は
一点とは限らないが、一点の方がイメージしやすいので)。
その点を再びpと書くと、この点を通るジョルダン閉曲線が
存在するはずだが、この閉曲線は他の閉曲線と交わって矛盾する。


年輪を帰納的に構成しようとしたが、可算無限回では終わらず、
超限帰納法が必要になりそうだった。自分のスキルでは超限帰納法が
うまく使えないので、かわりにツォルンの補題を使うことにした。
従って、証明が冗長な感じになった( ＾o＾)

(続く)

559 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 05:40:20.56 ]
(続き)

記法：
A⊂R^2に対して、Aの内部をA^iと書くことにする。
R^2内のジョルダン閉曲線γに対して、
「γの内部またはγ上の点」全体の集合をF(γ)と表すことにする。
明らかに、F(γ)はコンパクトである。また、F(γ)^i≠φが成り立つ。


実際の解答：
>>533が不可能であることを背理法で示す。
題意を満たすジョルダン閉曲線の族があったとして、その集合をΓと置く。
集合族Mを次のように定める。

M＝{ F(γ)｜γ∈Γ}

Γの定義から、任意のF1, F2∈Mに対して、

・F1＝F2
・F1⊂F2, F1≠F2
・F1⊃F2, F1≠F2
・F1∩F2＝φ

のいずれかが成り立つことが分かる。
このMに、次のようにして半順序≦を定義する(包含が逆向きになっているが、それでいい)。

F1≦F2 ⇔ F1⊃F2

(続く)

560 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 05:44:19.69 ]
(続き)

まず、上記の半順序集合(M,≦)には極大元が存在しないことを示す。

もし極大元が存在するならば、F1∈Mが極大元だとすると、
Mの定義から、F1＝F(γ1)なるγ1∈Γが取れる。
F(γ1)^i≠φだから、p∈F(γ1)^i を1つ取る。Γの定義から、このpを通る
γ∈Γが存在する。再びΓの定義から、F(γ)⊂F(γ1)^iが成り立つことが分かる。
特にF(γ)≧F(γ1)かつF(γ)≠F(γ1)となる。すると、

F(γ)∈M, F(γ)≧F(γ1), F(γ)≠F(γ1)

ということになるので、F1＝F(γ1)がMの極大元であることに矛盾する。
以上より、(M,≦)には極大元が存在しない。

よって特に、(M,≦)は帰納的でない。なぜなら、もし(M,≦)が帰納的ならば、
ツォルンの補題が使えて、(M,≦)には極大元が存在することになってしまうので。

(続く)

561 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 05:52:10.07 ]
(続き)

さて、(M,≦)は帰納的でないのだから、ある空でない全順序部分集合A⊂Mが存在して、
(A,≦)は(M,≦)の中に上界を持たないことになる。このようなAを1つ取っておく。

Aは全順序部分集合だったから、任意のF1, F2∈Aに対して、
F1⊂F2 または F1⊃F2 が成り立つ。
特に、集合族Aは有限交叉性を持つ。… (*)

任意のF∈Aはコンパクトだから、これと(*)より、∩[F∈A] F ≠φ
が成り立つことになる。そこで、p∈∩[F∈A] F …(**) を1つ取る。
Γの定義から、このpを通るγ1∈Γが存在する。
F1＝F(γ1)と置いておく。明らかに、p∈F1 かつ F1∈M である。
(A,≦)は(M,≦)の中に上界を持たなかったから、あるF∈Aが存在して、
F≦F1が成り立たない。すなわち、F⊃F1が成り立たない。これと>>559から、
・F1⊃F, F1≠F
・F1∩F＝φ
のいずれかが成り立つ。(**)に注意して、p∈Fだから、これとp∈F1より、
後者は成り立たない。よって、前者が成り立つしかない。
F＝F(γ)なるγ∈Γを取っておく。このとき

F(γ1)⊃F(γ), F(γ1)≠F(γ), p∈F(γ1), p∈F(γ), p∈Im(γ1)

ということだから、Γの定義から矛盾する(γとγ1の図を描くと分かりやすい)。
以上より、>>533は不可能である。


……ジョルダン閉曲線の性質を証明せずに、"Γの定義より" で
済ませている部分が多々あるので、厳密性に欠けるような( ＾o＾)



562 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 08:21:24.51 ]
ジョルダン閉曲線の内側の面積は0より大きい。
内側の面積が最小であるジョルダン閉曲線の内側には
別のジョルダン閉曲線は存在しえない。
故にジョルダン閉曲線で覆われていない領域が存在する。

563 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 14:56:14.23 ]
>>562
ジョルダン閉曲線が交わる場合は、その限りじゃないんじゃない？

564 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 18:09:02.46 ]
ジョルダン閉曲線の族が与えられたとき、
それらのジョルダン閉曲線における、

内側の面積が「最小である」ジョルダン閉曲線

は必ずしも存在しない。下限はいつでも存在するが、
それは0である可能性があり、その場合、
>>562の論法は破綻する。

565 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 18:33:58.68 ]
>>563
＞ 内側には
交わってるものは内側とは言わんだろ。 


566 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 22:03:05.45 ]
>>565
「内側」と言っている時点で、内包するものだけに
限定してしまっていて、互いに交わる場合が考慮されていない、
と言いたいのだ。



567 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 22:06:21.20 ]
なんか、アレフ１のR^2と、ジョルダン曲線とジョルダン曲線上の一周を[0,2π)とした位相の直積が一対一対応しないのが不思議。連続体仮説が崩れてる気が。

568 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 22:13:45.64 ]
>>567
連続と限らなければ一対一対応が作れる。

569 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 22:48:25.54 ]
www.astroarts.co.jp/shop/showcase/pzl_great/index-j.shtml
こういう感じの5x5の真っ白なジグソーパズルがあるとする。
ピースの繋ぎ目は全てユニークで間違った並べ方をすると必ず噛み合わず、
また実際に合わせてみないと隣り合うか分からない。
ピースの照合一回を一手とすると、
最善手の最長手数はいくらか。

570 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 23:13:13.17 ]
縁は直線？

571 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 23:13:43.97 ]
面積に注目するのイイですね。
その方針でも証明できた( ＾o＾)
今度はツォルンの補題が必要なくなった。

でも>>558-561より長い証明になってしまった。
構成的に議論するから、当たり前か。

まあ、書かなくてもいいよね(＾o＾)



572 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 23:13:57.88 ]
裏返しも区別がつかないの？

573 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 23:49:24.01 ]
よくわからんときは問題を簡略化して考えてみようと思った

・表裏の区別はつく、というか裏返せない
・縁と縁でないものの区別はつく
・凹と凸の区別などはつかない
・ジグゾーパズルの大きさは２ｘ２

574 名前：１３２人目の素数さん mailto:sage [2012/05/30(水) 23:54:04.28 ]
すると最善最悪は３回の照合で配置解明、＋４回の連結で完成か
…これかなり難しそうだなあ、２ｘ２でこれか

３ｘ３…すでに投げ出したい

575 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 00:17:08.08 ]
３ｘ３は中央が固定。
その上下左右は最悪４＋３＋２回
角も最悪４＋３＋２回

ある場所にある向きで必ず入るとわかっているピースを差し込むのは
照合というのか？  照合でないとしたら、１手に数えないのか？

576 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 00:32:53.20 ]
とりあえず確定済みの連結作業については
照合回数に含めない方向で考えてみないか？

まあ>>569など不満があるなら反対してくれると期待

577 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 13:57:09.54 ]
３×３の場合
（１）各辺のピースを中央のピースに合わせる　最悪で（３＋２＋１＋０）＝６回
（２）角のピースを合わせる　最悪で（３＋２＋１＋０）＝６回
よって６＋６＝１２回

４×４の場合
（１）各辺のピースに対して対応する中央のピースを見つける
最悪で（４×４−１）＋（４×３＋２×１−１）＋（４×２＋２×２−１）＋（４×１＋２×３−１）＋（２×４−１）＋（２×３−１）＋（２×２−１）＋（２×１−１）＝６４回
（２）角のピースを合わせる　最悪で（３＋２＋１＋０）＝６回
（３）２×２の場合に帰着　最悪で３回
よって６４＋６＋３＝７３回

これが最善手かどうかはわからんが

578 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 18:52:19.13 ]
実際に配置する話と情報を獲得する話がごっちゃに議論されるとわかりにくいので
「照合」とはあくまでも１つの辺と１つの辺がかみ合うかどうかをチェックする
作業を指すものだという設定にしたほうがよいかもしれない。

たとえば既に判明しているかみ合わせから部分的な配置が確定したところに存在する
１ピース分の穴に実際にピースを置いて確認する操作をすると、それは
同時に４組の辺と辺のかみ合わせをチェックしていることになるが、
上記考え方ではそのように実際に配置した所でチェックするのではなく
あくもでも個々の辺と辺のかみ合わせだけをチェックするのであって、
今回の例では、穴の周囲４辺のうちのどこかと別のピースのある辺がマッチした
時点で、他の３辺についてもマッチすることは推論による帰結として判明する
と考える。

579 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 21:32:29.35 ]
N×N の場合でも、次の方針でできるんじゃないの？

(1) 外枠を作る
(2) Pを残りのピースとする
(3) 以下の処理をして内側を埋める
for(c=2; c<N; c++){
＿for(r=2; r<N; r++){
＿＿r-1行c列目のピースとPのピースを照合し、
＿＿マッチしたピースpをPから取り出してr行c列目にはめる。
＿}
}

この場合の照合回数もすぐ出るでしょ。

580 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 22:25:27.52 ]
最善である証明どうやりゃいいんだか

581 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 22:34:02.85 ]
外枠を作るのに何回かかるか公式化できる？
ちなみに３×３だとある角のピースから時計回りにつなげると３＋２＋２＋１＋１回
それに中央のピースの回転を合わせるのに３回で計１２回、>>577と同じになる

>>577のやり方も一般化できるよ。しかも公式化できる。
n×n (n≧4)の場合、求める回数をP(n)とする
（１）各辺のピースに対して対応する中央のピースを見つける
最悪で(4*n-1)+(4*n-3)+...+3+1=4*n^2回
（２）角のピースを合わせる　最悪で3+2+1+0=6回
（３）(n-2)×(n-2)の場合に帰着　最悪でP(n-2)回
よってP(n)=4*n^2+6+P(n-2)




582 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 22:38:34.16 ]
>>581
ごめん、（１）の回数が間違ってるわ。スルーして

583 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 22:48:30.55 ]
>>581
n×n (n≧4)の場合
辺のピースの個数e:=4*(n-2)
中央のピースの個数c:=(n-2)*(n-2)
だから（１）の回数は
(4*c-1)+(4*c-3)+...+(4*c-2*(e-1)-1)回に訂正
これでいけるはず

584 名前：１３２人目の素数さん mailto:sage [2012/05/31(木) 23:53:43.34 ]
ある場所にピースが置けるかどうかは
隣のピースとの合致を総当りで見るしかない

順番に埋めていく限りはどの順番で当てはめても
1辺ずつの照合になるから最悪手はおよそ4*N!だろう

ちょっと問題を変えて、4つのピースを十字型に
並べてから真ん中に5つ目を当てはめると言う手順で
同時に4辺の合致判定をしたと認めるならば
4乗根くらい探索効率があがるはずだがどうかね

585 名前：１３２人目の素数さん mailto:sage [2012/06/01(金) 07:48:15.88 ]
>>584
自己レスだが計算が適当すぎた

586 名前：569 mailto:sage [2012/06/03(日) 19:32:14.86 ]
意外に厳密なルール設定が必要だったな。
照合に関しては >>578 がいいかな。
安楽椅子探偵が別部屋のパズルを
「◯番のピースの{左, 右, 上, 下} 辺に△番のピースはマッチするか？」の形式の
質問に対する「Yes/No」だけで解いてるイメージで。
>>584 はピースの照合が目的なら４手。

SAT充足判定問題を反復深化させると解けるかな。

587 名前：569 mailto:sage [2012/06/03(日) 19:38:19.87 ]
話がズレるが実際のジグソーパズルのユニークな切り口ってどうやって作ってるんだろうね。
多分凸の部分の大きさが線形に並んでるんだろう。
ってことはリアルジグソーも凸の大きさであらかじめソートしてやれば
二分探索が出来て早くなるのかもね

588 名前：１３２人目の素数さん mailto:sage [2012/06/03(日) 19:40:20.12 ]
Flashのジグソーパズルなら
ピースをほとんど重ねてしまって照合作業をCPUに任せるという
卑怯な手がある

589 名前：１３２人目の素数さん [2012/06/03(日) 20:26:30.14 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

590 名前：１３２人目の素数さん mailto:sage [2012/06/03(日) 21:50:23.58 ]
「◯番のピースの{左, 右, 上, 下} 辺に△番のピースの{左, 右, 上, 下}はマッチするか？」

だった

591 名前：１３２人目の素数さん mailto:sage [2012/06/03(日) 22:24:18.64 ]
ジグソーパズルを NxM とすると、
4個のコーナーピースは (位置の組み合わせ)=4!=24通り、
2(N+M)-8個のエッジピースは (位置の組み合わせ)=(2(N+M)-8)! 通り、
(N-2)(M-2)個のセンターピースは (位置の組み合わせ)×(向きの組み合わせ)
=(((N-2)(M-2))!)(4^((N-2)(M-2))) 通りの組み合わせがある。
全体の正解の組み合わせは、
N≠Mのとき、これらの積の1/2（180度回転対称はどちらも正解なので）
N=Mのとき、これらの積の1/4（90度回転対称はどちらも正解なので）
となる。

2x2のとき、6 通り。
3x3のとき、576 通り。
4x4のとき、1486356480 通り。
4x5のとき、128421199872000 通り。
5x5のとき、273395378722701312000 通り。



592 名前：１３２人目の素数さん mailto:sage [2012/06/03(日) 22:53:44.38 ]
2x2 を minimax の全探索で行ってみよう。
ピースを a,b,c,d として a を左上に置く。
答えは abcd, abdc, acbd, acdb, adbc, adcb のどれかだ。
（左上、右上、右下、左下の順で表現した）
「a の右隣りは b か」を問うとする。
__ 答 YES → 候補 abcd, abdc より２手詰み。
__ 答 NO → 候補 acbd, acdb, adbc, adcb。
____「a の右隣りは c か」を問うとする
______ 答 YES → 候補 acbd, acdb より３手詰み。
______ 答 NO → 候補 adcb, adbc より３手詰み。
____「b の右隣りは a か」を問うとする
______ 答 YES → 候補 acdb, adcb より３手詰み。
______ 答 NO → 候補 acbd, adbc より３手詰み。
____「c の右隣りは a か」を問うとする
______ 答 YES → 候補 adbc より２手詰み。
______ 答 NO → 候補 acbd, acdb, adcb より３手以上必要。
____「c の右隣りは d か」を問うとする
______ 答 YES → 候補 acdb より２手詰み。
______ 答 NO → 候補 acbd, adbc, adcb より３手以上必要。

よって2x2に対する「最悪手を最小にする最善手」の
最悪手は３手。最良手は２手。確率平均的には、8/3=2.666手。
これ以上はちょっと計算機の力が必要か。

593 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 07:03:47.87 ]
01 02 04 07 11
03 05 08 12 16
06 09 13 17 20
10 14 18 21 23
15 19 22 24 25
の順番で照合するとする。
01を置いた後、残りの
2辺が直線のピースは3個
1辺が直線のピースは12個
0辺が直線のピースは9個
よって照合回数の最大数は
(2+1)+(11+10+...+2+1)+(8+7+...+2+1)=120回
各順番で高々残りピースの数-1と同じ回数だけ照合すればいいという訳だから、単純に足してみた

594 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 07:22:09.78 ]
同じ方法で
1*1は0回
2*2は1回
3*3は9回
4*4は36回
n*nは3+(4n-7)(4n-6)/2+((n-2)^2-1)((n-2)^2)/2

595 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 07:24:29.01 ]
n>1が抜けてた

596 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 07:27:24.55 ]
>>593
細かいが、各()の中で最後に1を足す必要は無いぞ

597 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 07:30:01.53 ]
すまんミスりまくりだ

同じ方法で
1*1は0回
2*2は3回
3*3は9回
4*4は37回
n*nは3+(4n-9)(4n-8)/2+((n-2)^2-1)((n-2)^2)/2回

598 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 07:34:45.90 ]
>>596
+1の項は残りピース2個の時だから要ると思う
わかりにくくてすまん

599 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 07:38:05.32 ]
>>587
普通のジグソーパズルなら凸の位置や形状、
辺の曲がり方なんかも変えてある
大きなパズルを解くときは事前にピースの色と
形状パラメータで分類してから始めるというのは
慣れてる人ならみんなやってると思う

600 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 07:45:37.43 ]
>>599で思い出したけど、普通のジグソーパズルなら
凸と凸のマッチングとか絶対見ないし、4辺凸型とか
周りの情報で探索を絞れる形もあるな

今の全探索型の解は実際の2倍くらいの見積もりか

601 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 10:27:23.26 ]
>>600
そっかじゃあ例えば左と上が凹、右と下が凸になってたら、上下がわかるのか
そうなると4つの角は自動的に決まるし、枠だってすぐ決まるな

と思って>>569見たら上下と左右が対称だった




602 名前：１３２人目の素数さん mailto:sage [2012/06/04(月) 22:09:29.26 ]
>>601
ばらけたピースの左端のやつは3辺が凸の形に見える

603 名前：１３２人目の素数さん [2012/06/05(火) 13:34:44.79 ]
>>593
中央のピースは回転も考慮に入れないといけないのでは？

今日東急ハンズで実物見てきたけど
・９×１１と１２×１７の２タイプ
・表裏の区別はおそらく可能
・中央のピースはすべて上下凸左右凹（上下凹左右凸）型
・辺のピースは上凸左右凹型か上凹左右凸型のどちらか
だった

604 名前：１３２人目の素数さん mailto:sage [2012/06/05(火) 13:48:44.57 ]
>>603
ちゃんと買ってこいよ、乞食が！

605 名前：１３２人目の素数さん mailto:sage [2012/06/05(火) 14:55:42.97 ]
>>603
確かにそうだ

ていうか>>569を改めて見る限り、目視も照合回数に含まれると考えていいんじゃね？

とすると中央ピースは×3して192回か？

606 名前：１３２人目の素数さん [2012/06/05(火) 15:02:53.51 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

607 名前：１３２人目の素数さん [2012/06/05(火) 20:39:57.38 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

608 名前：１３２人目の素数さん [2012/06/06(水) 00:04:40.42 ]
>>605
中央ピースは{(4*9-1)+(4*8-1)+...+(4*2-1)+(4*1-1)}になるんじゃね？

609 名前：１３２人目の素数さん mailto:sage [2012/06/06(水) 00:21:07.96 ]
端から１個ずつやるのは損では？

残ってるピースがすべてバラバラの１個だと、
残ってるもの全部候補になっちゃうから全部試さないといけない。
あらかじめ２個以上のをくっつけてピースを大きくしとくと、
明らかにぶつかって試しても意味ないところがもっと枝刈りできる気がするが。
たとえば３ｘ２のすでにくっ付いたピースと２ｘ２の隙間があるとすると、
そのピースはその隙間には入らないことは照合しなくてもわかるわけで。


610 名前：１３２人目の素数さん [2012/06/06(水) 00:21:27.57 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
　　　 |　　　/:::::::::::::::::::::::::::::::::|:::::::::::::::::::::Ｏ::|::|::::::|:::::::::::::::/

611 名前：１３２人目の素数さん [2012/06/08(金) 10:15:14.01 ]
>>609
求める手数はピースの照合の仕方によらない



612 名前：１３２人目の素数さん mailto:sage [2012/06/08(金) 13:06:52.34 ]
>>611
どうして？ 

613 名前：１３２人目の素数さん mailto:sage [2012/06/08(金) 14:19:57.54 ]
　　　　　　　　　　__ﾉ)-'´￣￣`ｰ- ､_
　　　　　　　 ,　'´　　_. -‐'''"二ニﾆ=-`ヽ、
　　　　　　／　　 ／:::::; -‐''"　　　　　 　 `ｰノ
　　　　　/　　　／:::::／　　　　　　　　　　　＼
　　　　 /　 　 /::::::/　　　　　　　　　 |　|　|　 |
　　　　 |　　　|:::::/　/　　　　　|　　|　|　|　|　 |
　 　 　 |　　　|::/　/　/　|　　| ||　 |　| ,ﾊ .| ,ﾊ|
　 　 　 |　　　|/　/　/　/|　,ﾊﾉ|　/|ﾉﾚ,ﾆ|ﾙ'　
　　　　 |　　　|　 |　/　/ ﾚ',二､ﾚ′ ,ｨｲ|ﾞ/　　　私は只の数ヲタなんかとは付き合わないわ。
.　　　 　|　　　＼ ∠イ　 ,ｲイ|　　　 ,`-' |　　　　　　頭が良くて数学が出来てかっこいい人。それが必要条件よ。
　　　　 | 　　　　l＾,人| 　` `-' 　 　 ゝ　 |　　　　　　　　さらに Ann.of Math に論文書けば十分条件にもなるわよ。
　 　 　 | 　　　　 ` -'＼　　　 　 　ｰ' 　人　　　　　　　　　　一番嫌いなのは論文数を増やすためにくだらない論文を書いて
　　　　|　　　　　　　 /(l 　　 　＿＿／　 ヽ、　　　　　　　　　　　良い論文の出版を遅らせるお馬鹿な人。
　　 　 |　　　　　　　（:::::`‐-､__ 　|::::`､ 　 　 ﾋﾆﾆヽ、　　　　　　　　　あなたの論文が Ann of Math に accept される確率は?
　 　　|　　　　　　／ `‐-､::::::::::`‐-､::::＼　　 /,ﾆﾆ､＼　　　　　　　　　　　　それとも最近は Inv. Math. の方が上かしら？
　　　|　　　　　　|::::::::::::::::::|` -､:::::::,ﾍ￣|'､　 ﾋﾆ二、　＼
.　　 |　　　　　　/::::::::::::::::::|::::::::＼/:::Ｏ`､::＼ 　 |　'､　　 ＼
　　 |　　　　　 /:::::::::::::::::::/:::::::::::::::::::::::::::::'､::::＼ﾉ　　ヽ、　 |
　　|　　　　　 |:::::／:::::::::/:::::::::::::::::::::::::::::::::::'､',::::'､ 　/:＼__/‐､
　　|　　　　　 |／:::::::::::/::::::::::::::::::::::::::::::::::Ｏ::| '､::|　く:::::::::::::￣|
　　 |　　　　 /_..-'´￣`ｰ-､:::::::::::::::::::::::::::::::::::|/:/`‐'::＼;;;;;;;＿|
　　　|　　　　|／::::::::::::::::::::::＼:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/




[ 続きを読む ] / [ 携帯版 ]
前100 次100 最新50 ▲ [ このスレをブックマーク！ 携帯に送る ] 2chのread.cgiへ
[＋板 最近立ったスレ＆熱いスレ一覧 : ＋板 最近立ったスレ／記者別一覧]（；´∀｀）＜322KB

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef