- 1 名前：１３２人目の素数さん [2008/05/02(金) 21:53:23 ]
- 面白い問題、教えてください
- 445 名前：１３２人目の素数さん mailto:sage [2008/08/28(木) 21:45:53 ]
- X_aにおけるエレガントなプログラムのステップ数は多めに見積もって11以下。
何故なら定数をCと置いて
a=C-C
b=~C
b=b+C
a=a-b
により1を生成できるため。
- 446 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 07:03:47 ]
- >>445
a=C-C
b=~a
a=a-b
で1を生成できる。
よって、
X_aにおけるエレガントなプログラムのステップ数は10以下。
- 447 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 22:10:48 ]
- 今休刊になってる古いパズル雑誌の問題ですが
あなたは役人で７種類の通貨の単位を設定できる
(１円玉、２円玉、３０円玉など)
一度に使用する硬貨を三枚以内で(同じ額の硬貨複数使用も可能)で1円〜70円の70通りを表現できるように
硬貨を設定するには、７種類の単位をどうするべきだろう？
(考え中)
最低単位の１円玉は絶対必要。また、24円玉以上が一つはないと70円が表現できないですね
- 448 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 22:46:46 ]
- >>447
>>427の問題とかなり近い気がする。
- 449 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 23:16:33 ]
- >>447
ボトムアップでやっていけば解けないかな？
ちゃんと確かめてないけどイメージはこんな感じ。
for(i=1;i<=70;i++)
{
if(iを今までの硬貨３枚以内で表現できない)
{
iを通貨の単位として設定する。
}
}
- 450 名前：449 mailto:sage [2008/08/29(金) 23:30:48 ]
- ごめん、なんか全然駄目っぽい。
>>449は忘れて。
- 451 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 23:35:46 ]
- >>447
１円玉の次に低い単位が
２円玉か３円玉か４円玉かのどれかになるんですが
分岐が多くなりそうで
- 452 名前：１３２人目の素数さん mailto:sage [2008/08/29(金) 23:37:15 ]
- まぁ樹形図書いて二時間くらいしらみつぶしにやってればできるね。
うまい解法はなさそうだし。
- 453 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:03:21 ]
- ３５円玉は必要になる予感。
- 454 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:13:56 ]
- この流れで言ってしまってはミもフタもないが
たとえ造れたとしても現在流通している以外の貨幣（紙幣）って要らないよな
一と五のみで構成された金額体系は秀逸すぎる
だからこそ五万札や十万札でなく、二千札考えた奴にはポカーンとしてしまう
ミレニアムのしょぼい魔力にとり憑かれただけだろうな
- 455 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:23:14 ]
- >>454
> 一と五のみで構成された金額体系は秀逸すぎる
そろばんやってりゃ誰にでも思いつくと思う。
> だからこそ五万札や十万札でなく、二千札考えた奴にはポカーンとしてしまう
> ミレニアムのしょぼい魔力にとり憑かれただけだろうな
これには、同意。
- 456 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:52:25 ]
- >>447
1, 4, 5, 15, 18, 27, 34で作れるな．
また，多分これ以外では不可能．
1,1+1,1+1+1,4,5,1+5,1+1+5,4+4,4+5,5+5
1+5+5,4+4+4,4+4+5,4+5+5,15,1+15,1+1+15,18,1+18,5+15
1+5+15,4+18,5+18,1+5+18,5+5+15,4+4+18,27,1+27,1+1+27,15+15
4+27,5+27,1+5+27,34,1+34,18+18,5+5+27,4+34,5+34,1+5+34
5+18+18,4+4+34,4+5+34,5+5+34,18+27,1+18+27,5+15+27,15+15+18,15+34,1+15+34
15+18+18,18+34,1+18+34,27+27,1+27+27,4+18+34,5+18+34,4+27+27,5+27+27,15+18+27
27+34,1+27+34,18+18+27,15+15+34,4+27+34,5+27+34,15+18+34,34+34,1+34+34,34+18+18
- 457 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 00:57:07 ]
- >>456
エレガントな解法？
どう解いたかぜひ教えていただきたい。
- 458 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 01:10:37 ]
- >>457
期待させて申し訳ないが，全くエレガントでない．
プログラムを書いて探索した．
参考までにソースコード（C言語）：
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/7662.c
- 459 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 01:20:33 ]
- >>458
数学はもうコンピュータ無しでは立ち行かない時代になってしまったのだなぁ。（大げさか
- 460 名前：447 mailto:sage [2008/08/30(土) 01:25:21 ]
- 皆様ありがとうございました
- 461 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 07:58:06 ]
- >>454
全くだ。ユーロ圏に住んでるが
2セント、20セント、2ユーロコインは無駄すぎる
- 462 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 16:10:17 ]
- >>461
ユーロ圏で日本語版のWindowsだかMacintoshだかが使える事に驚いたわ
人間の行動そのものが無駄でしかない。損得勘定無しに動ける故の欠陥かね
- 463 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 16:38:28 ]
- そもそも無駄とは何か？
文学は無駄か？
芸術は無駄か？
- 464 名前：１３２人目の素数さん mailto:sage [2008/08/30(土) 22:38:00 ]
- >>427
適当に枝刈しながら、総当りでやってみた。
問題１の最悪のステップは 7
最悪のステップの例として、例えば 71 を求めるには。
1: a = ~1 [254]
2: b = a - 1 [253]
3: c = 1 - b [4]
4: d = c << c [64]
5: e = d + c [68]
6: f = e - b [71]
7: return f
ステップ数が 7 ぐらいなら数分で解けるから、問題２も２日ぐらいあれば
解けると思う。
- 465 名前：427 mailto:sage [2008/08/30(土) 23:09:31 ]
- >>464
解けましたか。乙です。
X_1における最悪の値になにか特徴は見出せますか？
もしかしてunsigned char じゃなくてunsigned shortでもいけそうですか？
- 466 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 02:23:21 ]
- >>464
ステップ数は6の間違い？
- 467 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 07:30:27 ]
- >>465
> X_1における最悪の値になにか特徴は見出せますか？
ぱっと見、特に特徴はなさそう。
各ステップの分布は以下の通り。
Step 1: 1
Step 2: 0, 2, 254
Step 3: 3, 4, 8, 127, 252, 253, 255
Step 4:5, 6, 7, 9, 10, 12, 16, 24, 31, 32, 63, 64, 125, 126, 128, 129, 130, 240, 244, 247, 248, 249, 250, 251
Step 5: 11, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 33, 34, 36, 40, 48, 60, 61, 62, 65, 66, 68, 80, 96, 120, 122, 123, 124, 131, 132, 160, 176, 190,
191, 192, 193, 194, 195, 196, 208, 216, 220, 223, 224, 225, 226, 228, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 241, 242, 243, 245, 246
Step 6: 35, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 67, 69, 70, 72, 73, 75, 76, 78, 79, 81, 82, 84, 85, 88, 90, 91, 92, 93, 94, 95,
97, 98, 99, 100, 101, 102, 104, 108, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 144, 152, 155, 156, 157, 158,
159, 161, 162, 163, 164, 165, 166, 168, 171, 172, 174, 175, 177, 178, 180, 181, 183, 184, 186, 187, 188, 189, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 209,
210, 211, 212, 213, 214, 215, 217, 218, 219, 221, 222, 227, 229
Step 7: 71, 74, 77, 83, 86, 87, 89, 103, 105, 106, 107, 109, 143, 145, 146, 147, 148, 149, 150, 151, 153, 154, 167, 169, 170, 173, 179, 182, 185
> もしかしてunsigned char じゃなくてunsigned shortでもいけそうですか？
俺の頭とマシンじゃとても無理。
- 468 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 07:33:21 ]
- >>466
どういう意味？
- 469 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 08:31:31 ]
- >>468
return文をステップ数にカウントするかどうかってことじゃない？
- 470 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 08:52:04 ]
- >>464
71 って 6 手で作れない？ビットシフトの仕様が違うのかしら。
1: a = ~1 [254]
2: b = 1 + 1 [2]
3: c = b << b [8]
4: d = a >> b [63]
5: e = c + d [71]
6: return e
- 471 名前：470 mailto:sage [2008/08/31(日) 10:33:53 ]
- 俺の手元の結果では >>467 のリストと
71 103 143 151 153 185 が違う（これらが6手で作れる）
あと，問題2は，最悪に対するステップ数最小は
使える定数が 29 67 98 99 101 163 226 227 の場合で，
そのステップ数は5手になった．
ちなみに最悪ステップ数最大は定数が 0 の場合で9手．
- 472 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 11:20:53 ]
- 右シフトの挙動ってunsignedとsignedで変化するからなぁ。
- 473 名前：>>467 mailto:sage [2008/08/31(日) 12:10:04 ]
- >>470-471
すまん、バグってて刈り込みすぎてた。orz
修正したら、>>471 の言う通りだった。
>>472
今回の場合は、unsigned が前提でしょ。
- 474 名前：427 mailto:sage [2008/08/31(日) 12:31:26 ]
- チャイティンさんの本によると、問題１の最悪の値はランダム性の高いビット列になるはずです。
半丁博打の親をやるとき最悪の値のビット列によって出す手を決めると負けにくいかもしれません。
そして使用するレジスタのビット幅を８から１６、３２と大きくしていって、レジスタ幅を無限大へ飛ばしたときの
最悪の値こそ真の乱数列と呼ばれるものにひょっとしたらなるかもしれません。
>>464さんの作成しているプログラムが完成したら、それは真の乱数検定アルゴリズムと呼べるかも？
万が一そうだとしたらちょっとすごいですね。
- 475 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 12:52:28 ]
- 乱数は定数とは違うだろ
乱数の種にルドルフ数を使おうとネイピア数を使おうと勝手だけど、それは乱数とは言いがたいと思われ
- 476 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 13:59:57 ]
- 何か誤解しているか、文章が不正確だと思う。とりあえず
> 問題１の最悪の値はランダム性の高いビット列になるはずです。
これは嘘。最悪の値 = 7 = 111b のランダム性は低い。
- 477 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 14:51:40 ]
- 最悪の値となる数値 (74, 77, 83, ...) も複数あるから、その並び順によって
ランダム性も違うし。
とにかく、>>474 はそのチャイティンさんの本の題名ぐらい示すべきかと。
- 478 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 15:04:18 ]
- どうでもいいけどステップ数の数え方を統一しようよ。
>>444はreturn文を数えてない。
>>427の5番目のルールを見る限り、return文は数えなくていい。
- 479 名前：474 mailto:sage [2008/08/31(日) 15:34:35 ]
- >>476-477
>>433に書きましたが知の限界という本です。
たしかにこの本の内容は私には難しめなので全部は理解してないし誤解があるかもしれません。
ランダム性の高いビット列といってるのは>>477の方の意味です。
- 480 名前：474 mailto:sage [2008/08/31(日) 15:43:06 ]
- 真の乱数というキーワードは刺激が強すぎてフレームの元かもしれませんね。
十分良い乱数、ぐらいに弱めておいたほうが無難でしょうか。
- 481 名前：474 mailto:sage [2008/08/31(日) 15:58:40 ]
- これです。
www.amazon.co.jp/知の限界-G-J-チャイティン/dp/443401238X/ref=sr_1_1?ie=UTF8&s=books&qid=1220165773&sr=8-1
- 482 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 16:28:01 ]
- >>479
>>477 に書いた通り最悪の値になる数値は複数あるからその並び順が問題になる
と思うが、そう言うことには言及してないの？
あと、そもそも 0 より 1 のビットの方が多いし。(0 は、89個、1 は 95個)
74: 01001010
77: 01001101
83: 01010011
86: 01010110
87: 01010111
89: 01011001
105: 01101001
106: 01101010
107: 01101011
109: 01101101
145: 10010001
146: 10010010
147: 10010011
148: 10010100
149: 10010101
150: 10010110
154: 10011010
167: 10100111
169: 10101001
170: 10101010
173: 10101101
179: 10110011
182: 10110110
- 483 名前：474 mailto:sage [2008/08/31(日) 16:41:43 ]
- >>482
乱数の種（プログラムに使用できる定数が0x01であること）が関係しているのかもしれません。
この定数は0x00のほうがよりふさわしいかもしれません。
あと演算もNOTを廃止してNORやNANDを追加したほうがより綺麗な議論になるかもしれません。
プログラムによって圧縮不能なビット列をランダムであると呼ぶ、と本に書いてありました。
もっともこの場合のプログラムはチューリング完全なプログラム言語での話なのですが。
私はX_1においても最小ステップ数の大きい値ほどランダムであると予想しました。
- 484 名前：474 mailto:sage [2008/08/31(日) 16:49:42 ]
- あと、真の乱数が複数あってもおかしく無いと思ってますし、
レジスタ幅が大きくなるほど0より1のビットのほうが多いといった誤差のようなものは小さくなっていくと期待しています。
どっちにしろ真の乱数は言いすぎですかね。
- 485 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 17:03:09 ]
- そこまで機能を限定したいなら、Malbolgeのcrzで同じ事をやろうか
- 486 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 17:03:54 ]
- >>484
真の乱数ってのは有限の状態から導き出せるのかい？
- 487 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 17:07:25 ]
- >>484
ビット数が 10 個ぐらいのところで chaitin の議論が適用できると思うのが間違い。
- 488 名前：474 mailto:sage [2008/08/31(日) 17:11:44 ]
- >>486
無限長の真の乱数を有限の状態から導き出すのは無理だと思います。
今回の方法でもレジスタ幅が有限のうちは破綻せずにプログラムを走らせられますが、
レジスタ幅を本当に無限にしてしまったら破綻してしまいます。
所詮は乱数列の長さが有限の場合に限って通用する方法だとは思います。
やっぱり真の乱数はフレームの元ですね。すいません。
- 489 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 17:47:25 ]
- 問題いい？
(1)平面上に4つ以上の幾つかの点を置く。
どの3点も1直線上になく、どの4点も同一真円周上になく、どの2つの点の距離も無理数である。
平面上には幾つ点が置けるか？
(2)もしも平面上に(1)の置き方で置ける点の個数に上限があるとき、立体に拡張したらどうなるか。
ただしどの5点も同一真球上にないものとする。
- 490 名前：489 mailto:sage [2008/08/31(日) 17:49:46 ]
- あぁ、書き忘れた。
どの点のx座標、y座標、存在するならz座標をとっても
その値は有理数であるものとする。
例えば(1,-3)はOK、(√3,1)、(5,π)等は駄目
- 491 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 18:08:38 ]
- >>489
(1)(n,n^2)で表される点(nは非負整数)を取っていけばいくらでも。
- 492 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 18:23:18 ]
- >>483
つまり >>474 の
> チャイティンさんの本によると、...
というのは嘘で
「『知の限界』を読んで427が考えたところ，...」
が正しいんだよな．しばらく探してしまった．
- 493 名前：474 mailto:sage [2008/08/31(日) 18:32:41 ]
- >>492
申し訳ないです…。
- 494 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 19:12:26 ]
- >>483
> 私はX_1においても最小ステップ数の大きい値ほどランダムであると予想しました。
この予想をちゃんと書くとどうなるかに依存するが，
厳密な意味で解釈すると，これが成り立たないことが示せる．
何より，こんな読み物読んで下手な予想をする前に，
ちゃんとした本を読んだほうがよい．
- 495 名前：474 mailto:sage [2008/08/31(日) 19:19:58 ]
- >>494
そうでしたか。すいません。
後学のためにどこがまずいのか解説していただけるとありがたいです。
たとえば、レジスタ幅が大きくなったとき０と１の割合が大体半々にならずに、
大きく違ってしまうといたことが起こるのでしょうか。
- 496 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 20:03:25 ]
- >>495
一番まずいのは言語がチューリング等価でないこと．
>>483 の予想を厳密に解釈し，それが成り立つと仮定すると
X_1 とチューリングマシンが等価になることが示せるが，それはない．
あと，マイナー（でもないが）な考え違いを指摘しておくと，
今の意味のランダム性には
> レジスタ幅が大きくなったとき０と１の割合が大体半々
という性質は不要。これは統計的（一様）ランダム性の条件だが，
情報論的ランダム性の条件ではない。
- 497 名前：474 mailto:sage [2008/08/31(日) 20:17:28 ]
- もうちょっと食い下がらせてもらいます。
X_1がunsigned charしか使えないのであればチューリング等価でないのは明らかです。
しかし、レジスタ幅が任意の有限長になることを許すならば私にはチューリング等価の可能性も捨て切れません。
そもそも論理回路はチューリング完全だと思っていました。
あと、統計的ランダム性と情報論的ランダム性は情報論的ランダム性のほうがずっと強い制約なのだと思っていました。
情報論的ランダム性を満たすならば、統計的ランダム性は当然満たされるはず、と思っていたのですが…。
- 498 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 20:45:07 ]
- 未だによく分からんのだけど、チューリング等価性の証明ってどうやるん？
- 499 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 20:46:09 ]
- >>497
関数も作れない、ジャンプも出来ない
どうやってループすんのさね
- 500 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 20:52:03 ]
- >>497
ねぇ、昔はどうやって8bitマイコンとかで32bit演算をやってたか知ってる？
あと、どうやってパソコンが負の数を扱ってるか知ってる？
X_1の場合、次の条件を満たせばunsigned intだろうが、signed intだろうが、
扱えるようになるでよ
・無数のレジスタがある
そう、これだけ。
どうしても分からなかったら「多倍長演算」とか「2の補数表現」とかでググってみなよ。
あぁ、この2つのキーワードは全く別物だから単体でね
- 501 名前：497 mailto:sage [2008/08/31(日) 21:12:51 ]
- たしかにループできませんね…。
ループが出来なければ任意の大きさの入力を捌くことは出来ないし…。
結局、事前に入力の大きさに上限がある必要がありますね。
- 502 名前：497 mailto:sage [2008/08/31(日) 21:32:49 ]
- しつこくてすいません。
もうちょっと教えてください。
出来ればこの問題はすっきり理解したい。
>X_1 とチューリングマシンが等価になることが示せるが
ここはどうやるのでしょう。
- 503 名前：497 mailto:sage [2008/08/31(日) 22:31:37 ]
- >>483 の予想を厳密に解釈し，それが成り立つと仮定すると
X_1 とチューリングマシンが等価になることが示せるが
すいません。引用が足りないですね。
正しくはこうですね。
- 504 名前：１３２人目の素数さん mailto:sage [2008/08/31(日) 23:05:54 ]
- >>503
アルゴリズム的情報理論の基礎事項。適当な本読め。
あといいかげんスレ違い。
- 505 名前：１３２人目の素数さん mailto:sage [2008/09/01(月) 07:19:08 ]
- n次空間上に2つの点A(a1,a2,...,an)点B(b1,b2,...,bn)がある。
・2点AB間の距離が超越数になる
・a1,...,an,b1,...,bnのいずれかは超越数である
は同値か？
- 506 名前：１３２人目の素数さん mailto:sage [2008/09/01(月) 09:19:14 ]
- 距離の定義はどれ？
- 507 名前：１３２人目の素数さん mailto:sage [2008/09/01(月) 09:47:48 ]
- >>505 n=1のとき、a=π+1,b=πとおくと
d(a,b)=1だがbは超越数である。よって命題は偽。
- 508 名前：１３２人目の素数さん mailto:sage [2008/09/01(月) 22:16:13 ]
- ちょー面白い問題だな
- 509 名前：１３２人目の素数さん mailto:sage [2008/09/02(火) 10:36:40 ]
- 次の( )にそれぞれｱﾗﾋﾞｱ数字(何桁でも可)を入れて文を成立させて下さい
漢数字やﾛｰﾏ数字等は不可(全通り答えて下さい)
｢この文には
０が( )個
１が( )個
２が( )個
３が( )個
４が( )個
５が( )個
６が( )個
７が( )個
８が( )個
９が( )個
含まれています｣
- 510 名前：１３２人目の素数さん mailto:sage [2008/09/02(火) 11:25:41 ]
- ｢この文には
０が( 1)個
１が( 11)個
２が( 2)個
３が( 1)個
４が( 1)個
５が( 1)個
６が( 1)個
７が( 1)個
８が( 1)個
９が( 1)個
含まれています｣
- 511 名前：１３２人目の素数さん mailto:sage [2008/09/02(火) 11:31:33 ]
- 頻出
- 512 名前：１３２人目の素数さん mailto:sage [2008/09/03(水) 05:18:34 ]
- 各辺の長さが１で底面が正三角形の三角柱ABC-DEFがある。
この三角柱をAEF,BDF,CDEをそれぞれ通る３つの平面で切断する。
問１
平面DEFを含む立体の体積を求めよ。
問２
平面DEFを含む立体の展開図を作図せよ。
- 513 名前：１３２人目の素数さん mailto:sage [2008/09/03(水) 05:57:25 ]
- 問２は平面ABCを含む立体の展開図の方が面白いかも。
- 514 名前：１３２人目の素数さん mailto:sage [2008/09/03(水) 06:10:43 ]
- >>510
これ以外に解はないの？
- 515 名前：１３２人目の素数さん mailto:sage [2008/09/03(水) 11:03:22 ]
- >>513
DEFのときとなにか違うのか？
- 516 名前：１３２人目の素数さん mailto:sage [2008/09/03(水) 20:45:02 ]
- 空間上に正三角柱をねじったような6つの頂点を持つ立体があり、
その頂点ABCDEFが次を満たすように並んでいる。
ABの長さは1
三角形ABCは正三角形
三角形DEFは正三角形
三角形ABDは正三角形
三角形BCEは正三角形
三角形CAFは正三角形
三角形ADFは正三角形
三角形BEDは正三角形
三角形CFEは正三角形
このとき、立体ABCDEFの体積を求めよ。
- 517 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 00:40:02 ]
- >>516
一辺の長さが２の正四面体から４つの角を取った形になるのかな？
- 518 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 00:43:50 ]
- であれば、一辺の長さが１の正四面体の体積をVとして>>516の答えは4V。
- 519 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 05:58:44 ]
- ( ﾟдﾟ)ﾎﾟｶｰﾝ
- 520 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 07:45:24 ]
- 一辺が２の正四面体の、４つの角からそれぞれ一辺が１の正四面体を切り取った形だよな。
それ以外の形で>>516を満たすものがあるのかもしれんが
- 521 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 09:46:45 ]
- 成分が０と１だけの３x３の行列Ａに対して行または列を任意にひとつ選び
０と１を入れ替える操作をＲとします。
任意回の操作Ｒで移りあう行列を「同値な行列」と言うことにすると、
２＾９個の可能な３x３行列のうち「同値でない行列」は何種類あるでしょうか？
- 522 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 12:48:43 ]
- >>516
△ABC を底面とすると、立体の高さは √(2/3)
底面からの高さ (√(2/3))t での断面積は
((√3)/4)(1+2t-2t^2) (0≦t≦1)
立体の体積は
√(2/3) * ((√3)/4) * ∫[0,1](1+2t-2t^2)dt
= (√2)/3
- 523 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 15:19:30 ]
- >>521
16通り。
略解：
[STEP1]操作Uiと操作Vjを次のように定義する。
U1：1行目の0と1を入れ替える
U2：2行目の0と1を入れ替える
U3：3行目の0と1を入れ替える
V1：1列目の0と1を入れ替える
V2：2列目の0と1を入れ替える
V3：3列目の0と1を入れ替える
次に、行列の各成分はZ/2Zの元であると見なす。こうすると、
1行目の0と1を入れ替える ⇔ 1行目の各成分に1を足す …＊
が成り立つことが分かる。他の行や列についての操作も同様である。
また、このことから、各操作の順番は可換であることが分かり、
また、同じ操作を2回繰り返すと「何もしない」のと同じである
ことが分かる。よって、任意の操作は
Uiを行うか否か(i＝1,2,3)
Vjを行うか否か(j＝1,2,3)
の6つを決めるだけで決まる。そして、T＝(u1,u2,u3)×(v1,v2,v3)∈(Z/2Z)^3×(Z/2Z)^3に対し、
ti＝1 ⇔ 「i行目の0と1を入れ替える」(i＝1,2,3)
uj＝1 ⇔ 「j列目の0と1を入れ替える」(j＝1,2,3)
という同一視を行うことで、任意の操作はTと同一視できる。
行列A＝(aij)と操作T＝(u1,u2,u3)×(v1,v2,v3)を任意に取るとき、
Aに操作Tを施した行列をTAと書くことにすると、＊より、
(TAのi行j列成分)＝aij＋ui＋vj
と書けることが分かる。
- 524 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 15:20:26 ]
- [STEP2]任意の行列に対し、適当な操作をすることで
000
0ab
0cd
という形に変形できるから、初めからこの形の行列だけを考えればよく、
この形の行列の中で、同値でないものの個数を求めればよい。実は、この形の
行列は全て同値でなく、よって答えは16通りとなる。そのためには、
A B
000 000
0ab 0ef
0cd 0gh
という2つの行列A,Bが同値であるとしたとき、A＝Bとなることを言えばよい。
STEP1を踏まえれば、AとBが同値 ⇔ あるT＝(u1,u2,u3)×(v1,v2,v3)に対しTA＝B
となるが、TAの各成分とBの各成分を実際に比較すると、u1＝u2＝u3＝v1＝v2＝v3
となることが分かるので、u1＝0であってもu1＝1であってもTA＝Aとなることが
分かり、A＝Bが従う。
- 525 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 15:22:23 ]
- ＞ti＝1 ⇔ 「i行目の0と1を入れ替える」(i＝1,2,3)
＞uj＝1 ⇔ 「j列目の0と1を入れ替える」(j＝1,2,3)
↓訂正
ui＝1 ⇔ 「i行目の0と1を入れ替える」(i＝1,2,3)
vj＝1 ⇔ 「j列目の0と1を入れ替える」(j＝1,2,3)
- 526 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 20:07:36 ]
- >>521
「行列が同値 ⇒ 行列Ａの任意の2x2小行列の中の１または０の個数の偶奇は不変」
なので３ｘ３行列の４隅の偶奇のパターンだけつまり、2^4=16種類存在する。
4x4行列の場合は独立な2x2小行列が何個あるのかな？４隅と真ん中の１個で2^5種類？
- 527 名前：１３２人目の素数さん mailto:sage [2008/09/04(木) 23:52:23 ]
- ここでちょっと雑談を。
なんで数学の問題を面白いと感じたり詰まらないと感じたりするんだろう。
面白い問題と詰まらない問題の間にはどんな差があるのか？
- 528 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 00:05:48 ]
- つまらない問題
解法が自然に分かる、総当りで解ける、問題文がやけに長い
面白い問題
解法が非自明、視点を変えるとあっさり解ける、問題文が簡潔
こんなところか
- 529 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 00:25:09 ]
- ただ、問題の「良い」解き方、汎用性の高い解き方、
というのはアクロバティックな解き方じゃなくて、
少々証明が長くなっても非自明な命題を自明なステップに分解して
こつこつ進んでいく「詰まらない」解き方だったりするんだよね。
- 530 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 00:35:27 ]
- こつこつ進んでいくって言うのは自分の手持ちの思考方法が通用してる間の場合だよね。
自分の手持ちの思考方法がどれ一つ全然通用しなくなってこれ以上一歩も進めなくなったときこそ
数学者としての真価が問われるというか。
- 531 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 01:02:04 ]
- >>521
こういう問題は掃き出し法で機械的に解けるのだ。
- 532 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 01:16:12 ]
- >>530
つまり俺には数学をやる資格がないんですね、分かります
- 533 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 02:23:42 ]
- > 総当りで解ける
総当たりで解けることはわかっていても
そうでない方法で解けるかもしれなさそうな問題は面白いぞ。
- 534 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 03:00:02 ]
- 総当りで原理的には解けるけど
実際は計算時間的にほとんど無理、みたいな問題もあるよね。
ルート2の10進小数展開の小数第 1 位から 100,000,000 桁までに
60,00,000 桁以上同じ数字が連続して並ぶことは無いことを
（電子計算機を使わずに）示せ、とか。
- 535 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 03:07:04 ]
- このスレに良く出てくる虫食いみたいな奴のことを言ってるんじゃないの？
- 536 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 07:51:59 ]
- >>526
4×4の場合は2^9通り。523〜524と同じ方法が使える。
というか一般のn×nでも使えて、2^{(n−1)^2}通りになる。
- 537 名前：１３２人目の素数さん mailto:sage [2008/09/05(金) 10:24:04 ]
- >>526
n×n 行列を F_2 上の n^2 次元ベクトル空間と考える。
与えられた U1,...,Un,V1,...,Vn を生成系とする部分空間 W がこのベクトル空間に作用すると考える。
U1+...+Un+V1+...+Vn=0 だから、部分空間 W の次元は 2n-1 以下。
一方、n×n 行列の 1 行目と 1 列目のなす部分空間の次元は 2n-1 で、
W はこの部分空間に可移に作用しているので、W の次元は 2n-1 以上。
よって、2^(n^2)/2^(2n-1)=2^((n-1)^2) が求める同値類の数。
- 538 名前：１３２人目の素数さん mailto:sage [2008/09/07(日) 22:27:32 ]
- M 個の石の山と N 個の石の山がある。
二人で交互に一度ずつ石を取っていく。
片方の山から石を取るか、或いは両方の山から同数ずつ石を取れ、
最後の石を取ったほうが負けとなる。
後手必勝となるのはどのような場合か？
- 539 名前：１３２人目の素数さん mailto:sage [2008/09/08(月) 16:13:22 ]
- M〜Nがある数値の時
- 540 名前：１３２人目の素数さん mailto:sage [2008/09/08(月) 18:19:20 ]
- M〜Nって何？M-Nなら分かるが。
- 541 名前：１３２人目の素数さん mailto:sage [2008/09/08(月) 20:48:16 ]
- MとNで大きい方から小さい方を引く
- 542 名前：１３２人目の素数さん mailto:sage [2008/09/08(月) 23:17:32 ]
- 違う。(0,1)は後手必勝なので、
(M,M+1) (M, 1) (1, M)但し M ≧ 1 は先手必勝。
そうすると(2,2)はそこからどのような手をとっても
次の手番に先手必勝の状態にしかならないので後手必勝。なので
(M+2, M+2) (M+2, 2) (2, M+2)は先手必勝。
そうすると(3, 5) (5. 3)はそこからどのような手をとっても
次の手番に先手必勝の状態にしかならないので後手必勝。なので（以下略
- 543 名前：１３２人目の素数さん [2008/09/08(月) 23:20:18 ]
- 一応ageて宣伝してみよう
- 544 名前：１３２人目の素数さん mailto:sage [2008/09/09(火) 04:10:32 ]
- N, M ≦ 100 の範囲で後手必勝になるものの一覧：
(0,1) (1,0) (2,2) (3,5) (4,7) (5,3) (6,10) (7,4) (8,13) (9,15)
(10,6) (11,18) (12,20) (13,8) (14,23) (15,9) (16,26) (17,28) (18,11) (19,31)
(20,12) (21,34) (22,36) (23,14) (24,39) (25,41) (26,16) (27,44) (28,17) (29,47)
(30,49) (31,19) (32,52) (33,54) (34,21) (35,57) (36,22) (37,60) (38,62) (39,24)
(40,65) (41,25) (42,68) (43,70) (44,27) (45,73) (46,75) (47,29) (48,78) (49,30) (50,81) (51,83) (52,32) (53,86) (54,33) (55,89) (56,91) (57,35) (58,94) (59,96)
(60,37) (61,99) (62,38) (65,40) (68,42) (70,43) (73,45) (75,46) (78,48) (81,50)
(83,51) (86,53) (89,55) (91,56) (94,58) (96,59) (99,61)
- 545 名前：544 mailto:sage [2008/09/09(火) 04:12:19 ]
- × ≦ 100
○ ＜ 100
|
 |
