面白い問題おしえて～な十五問目

面白い問題おしえて～な十五問目 at MATH

[前50を表示]
350:１３２人目の素数さん
09/05/10 14:42:38
問題：以下の命題を反証し、その反例を示せ。

命題：3次元空間上に4つの点ABCDがあり、そのx座標、y座標及びz座標は整数である。
この4つの点について3字のベジェ曲線を引いた時、その長さをf(A,B,C,D)とする。
f(A,B,C,D)が整数となるような自明でない点の組は存在しない。

351:１３２人目の素数さん
09/05/10 14:43:28
3字の→3次の

352:１３２人目の素数さん
09/05/11 04:49:58
>>350
その場合の、「自明でない」とは、どういう事を指すのか？

353:１３２人目の素数さん
09/05/11 04:51:20
>>349
数学的には12個も未解決だろう。

354:１３２人目の素数さん
09/05/13 23:07:33
有名かな・・・？

536870912人が集まり、テニスのトーナメント戦を行おうとしたが、
そのうちの１人が病欠し、その結果１人が不戦勝となった。

優勝者が確定するまでに、何回試合が行われるか。

ただし、等差数列や等比数列の総和の公式を用いずに求めること。

なお、536870912 = 2^29 である。

（シングルスです。引き分けはあり得ないとします。不戦勝のぶんはカウントしません。
　３位決定戦などは不要で、単に、優勝者を決めるだけのトーナメント戦です）

=====
答えがわかった人、解くのにどのくらい時間かかったか教えてくださいまし。

355:１３２人目の素数さん
09/05/14 04:43:05
問題を読むのに３分くらいかな。
中学で習ったよ。

356:１３２人目の素数さん
09/05/14 17:04:55
トーナメントの試合数は最初中学で数学ではなく保険体育の時間に習った。

357:１３２人目の素数さん
09/05/14 18:27:47
最初の二行読み終わったら分かったな

358:１３２人目の素数さん
09/05/14 18:37:57
有名かな？
既出かな？

の人が書くのは全部有名で既出と決まっているので一行目でスルー
俺を含めてもう４人も釣れたな

359:１３２人目の素数さん
09/05/14 23:34:21
>>358
> 有名かな？
> 既出かな？
> の人が書くのは全部有名で既出と決まっているので一行目でスルー

あー確かに
なんていうか、算数にロマンを感じて、背伸びして受験数学を理解しようと
必死こいてるモッサンって感じがプンプンしますな～

360:１３２人目の素数さん
09/05/15 02:17:22
>>357
問題文を最後まで読まないせいで間違えたことは何度くらいある？

361:１３２人目の素数さん
09/05/15 03:12:32
この人数でテニスのトーナメント戦をして生きてるうちに優勝が決まるのを想像したら感動で涙が止まらなくなった

362:１３２人目の素数さん
09/05/15 03:12:55
>>360
お前は今までに食べたパンの枚数を覚えているのか？

363:１３２人目の素数さん
09/05/15 03:16:40
>>361
会場さえたくさんあれば、そんなに時間はかからないのだが

364:１３２人目の素数さん
09/05/15 03:26:12
会場が2^28もあれば楽勝

365:１３２人目の素数さん
09/05/15 03:27:59
>>364
審判の数は足りるのか?

366:１３２人目の素数さん
09/05/15 03:30:07
中国かインドから連れてくるか

367:１３２人目の素数さん
09/05/15 04:41:40
会場が10000もあれば、2セット1時間で1試合終了として寝ず休まずで6年～7年もあれば終わるか。会場数が1000だと辛いな。

368:１３２人目の素数さん
09/05/15 13:08:04
それよりも世界のテニスの競技人口が1億もいないような

369:１３２人目の素数さん
09/05/15 18:35:33
>>354
この人数なら「勝ったものの負傷等で次戦以降棄権」が相当数出そうだから総試合数は上限しか算出できまい。

370:１３２人目の素数さん
09/05/16 01:27:33
世界のスポーツの競技人口(自称も含む)

１チェス 5億
２象　棋 5億
３バスケ 4億5000万
４蹴　球 2億4000万
５クリケット不明
６卓　球不明

(１２は逆の説あり)
以下は順位不明

ビリヤード 1億
ゴルフ 6000万
テニス 5000万
バドミントン 5000万
ソフトボール 5000万
テコンド 5000万
囲　碁 4200万
ボウリング 4000万
ハンドボール 3100万
アメフト 2300万
トライアスロン 2000万
スカッシュ 1500万
野　球 1200万
柔　道 1000万
ビーチバレー 1000万
ラグビー 424万
ラクロス　60万
近代五種　 3万

室内のバレーはビーチよりは多そう

371:１３２人目の素数さん
09/05/16 01:56:21
>>362
すまない、そんなにだとは思っていなかったんだ。
ほんとにすまない。

372:１３２人目の素数さん
09/05/16 02:15:56
>>371
半斤8枚きりとして、一日2枚がおれの朝食。
小学校に入る前、幼稚園の年中組が終ったあの日から、いつも朝はそれだった。
自慢じゃないが、朝食を抜いたことは一度もない。旅行で家を離れたこともない。
だから、食べた枚数は確実に計算できる。閏年も勘定に入れてよい。
一枚の誤差も無い。高校に入った時には、３枚にして欲しいとは思ったが、家計が許さなかった。
だから、今はそれが幸いして、これまでに食べた食パンの枚数を答えることができる。

373:１３２人目の素数さん
09/05/16 03:49:33
象　棋
をやってみたいのだが、どういう競技なんだろう。
簡単に説明してくれ。

374:１３２人目の素数さん
09/05/16 04:14:58
象象象象象象象象象
　角　　　　　　　　　飛
香桂銀金王金銀桂香車

375:１３２人目の素数さん
09/05/16 06:25:25
>>373
象棋(シャンチー)については中国人に聞くと良い。俗に日本では中国将棋と言ったりするから、どんなもんかは大体想像がつくだろう。競技人口が多いのは中国人がやってるから。
ちなみに他のチェスライクゲームでの競技人口は日本の将棋が1500万、韓国のチャンギは700万、タイのマックルックは500万だそうだ。この五つが世界の五大チェスになるらしい。

376:１３２人目の素数さん
09/05/16 06:31:09
一応参考に

URLﾘﾝｸ(www.snowdolphin.net)

377:１３２人目の素数さん
09/05/16 11:58:25
>>354

普通に答えちゃっていいのかな・・・？
間違ってるかもしれんけど。

536870912人から一人抜けて536870911人。

トーナメントは一試合で一人負けて減るから、
最後の一人が決まるまでの試合数は536870911-1で
536870910試合　以上。

378:１３２人目の素数さん
09/05/16 13:01:03
ダブルスでやれば１試合でふたり負けて
倍の効率

379:１３２人目の素数さん
09/05/16 13:03:34
5億人近くに教えるのも手間かかるな。テニスでまだ良かった。

380:１３２人目の素数さん
09/05/16 13:03:42
>>372
給食は食べさせて貰えなかったのか？

381:１３２人目の素数さん
09/05/16 13:29:25
パンは危険な食べ物です
のコピペが頭に浮かんだ

382:１３２人目の素数さん
09/05/16 16:33:20
千円乞食のごとく週末に湧いてくるなこいつら

383:１３２人目の素数さん
09/05/16 20:06:17
昔吸う蝉で見た問題

自然対数eを予備知識を持たない人（小学生など）に出来る限り分かりやすく説明しなさい。

384:１３２人目の素数さん
09/05/16 20:14:07
数学の問題になっていない

385:１３２人目の素数さん
09/05/16 20:19:28
xの多項式f(x)について、その項数をQ(f(x))とおく。
例）　Q(x^3 - 5) = 2、　Q(x^10 + x^8 - 7x + 2) = 4、など

このとき、Q( f(x)^2 ) ＜ Q(f(x)) を満たすf(x)を一つ求めよ。

386:１３２人目の素数さん
09/05/17 04:12:25
>>385
そんなもんあるの？
あったら素直にスゴイと思うけど。

387:354
09/05/17 04:43:19
>>377

そうそうそれ。お見事。

なお、マイクロソフトの面接問題（筆記試験ではない）です。
（桁数はもっと小さいけど）

でも、面接でストレスになってるときに、これ言われたら、
すぐに答えられないかもなー・・・・・と、ある本に書いてました。

388:１３２人目の素数さん
09/05/17 04:56:33
>>385

複素数使ってもいいの？

389:１３２人目の素数さん
09/05/17 04:56:34
>>385
　f(x) = 1 ±(√2)x -x^2 ±(√2)x^3 + x^4,
　f(x)^2 = 1 ±(2√2)x +7x^4 ±(2√2)x^7 + x^8,
ぢゃだめぽ･････ orz

390:１３２人目の素数さん
09/05/17 05:09:54
ゲーセンにあるAnswer×Answer（全国のゲーセンをオンラインで結んだクイズゲーム
・・・QMAことクイズマジックアカデミーのほうが有名だけどね・・・）で、
どーも、おなじ人となんどもあたったり、
同じ問題が何回も出題されるから、
「プレイ人数少ない＆問題数少ない」のか、ゲーム作ってるセガのプログラミングが悪いのか・・・と思って、
Answer×Answerの仕様通りに、

総問題数をQとして
１日にｎ回ゲームをしたときに、
「今日、さっきみた」っていう問題が出現する回数の期待値とか、だぶった問題の種類の数の期待値とかを、求めようと思ったら、
こんがらがった。
（仕様だと、４人がいっしょに戦って、予選と決勝があって、予選の問題数が約問（<=経験則。正確には違うけど）、
予選の上位二人が決勝に進んで、決勝の問題数が６問（<=経験則で約6問）
（いやほんとは間違えると-10点とか30点とると優勝とかこまかいことあるんだけど）

391:390
09/05/17 05:11:42
誤：予選の問題数が約問
正：予選の問題数が8問

392:354
09/05/17 05:29:21
じゃあまあ、

数学だか数学じゃないんだかわからないところで・・・

==============================================================
10進法における1から10までの整数を、マイナス２進法で数えなさい。
ただし、「マイナス２進法」は自分でなるべく論理的に定義すること。
==============================================================

393:１３２人目の素数さん
09/05/17 07:15:28
00000001
00000110
00000111
00000100
00000101
00011010
00011011
00011000
00011001
00011110

394:１３２人目の素数さん
09/05/17 10:05:03
>>385
URLﾘﾝｸ(mathworld.wolfram.com)

395:１３２人目の素数さん
09/05/17 18:46:49
>>387
ストレス下での回答を見るためのテストは2chに向かないと思うが……
面接時に回答できなかった人も、2chでは回答できるような問題だろ？
それって、ここで聞く内容じゃないべ

396:１３２人目の素数さん
09/05/17 19:27:02
>>394
どうやって見つけたんだこれ……
いや、ぐぐったとかはなしね。

397:１３２人目の素数さん
09/05/17 19:43:47
>>394
㌧クス
URLﾘﾝｸ(mathworld.wolfram.com)
もあった･･･

398:１３２人目の素数さん
09/05/17 19:50:34
少し変えて

xの多項式f(x)について、その項数をQ(f(x))とおく。
例）　Q(x^3 - 5) = 2、　Q(x^10 + x^8 - 7x + 2) = 4、など

f(x) が Q( f(x)^2 ) ＜ Q(f(x)) を満たす時、Q(f(x))の最小値を求めよ。

----

うん、思い付きだ。俺も答え知らない……

399:１３２人目の素数さん
09/05/17 19:56:24
おろ？　新たなネタがきてる
>>397
読ませてもらおうか！

400:１３２人目の素数さん
09/05/18 05:06:58
>>398
13と >>397 に書いてあるように見えるが

401:１３２人目の素数さん
09/05/18 05:17:38
>>396
いくつかの例はErdosとかの時代に（試行錯誤的に）知られてたんだと。
現在では計算代数の手法を用いて具体的に構成できる。

402:１３２人目の素数さん
09/05/18 14:00:48
解けるわけじゃないので、偉そうなこと言えないが釈然としない解決だ。

403:１３２人目の素数さん
09/05/18 14:24:19
>>402
なんか綺麗な構造を発見できたら現在でも論文にできるよ。

404:１３２人目の素数さん
09/05/18 14:53:40
要するに未解決問題とほぼ同レベルなのね

405:１３２人目の素数さん
09/05/19 01:13:26
これの3乗版とかないの？

406:１３２人目の素数さん
09/05/19 01:31:02
・3乗だと存在しないけど4乗だと存在する。
・むしろ2^n乗のときのみ存在する。

……みたいになってたら面白いだろうな。

407:１３２人目の素数さん
09/05/19 01:57:20
今のところ、どうなってるか分からん。
マジで分からんとしか、言いようがないわけだが……
誰か類似の結果知ってる奴いないか？

408:１３２人目の素数さん
09/05/19 02:06:09
つーか、3乗くらいならmathematicaに計算させてみたらどうか

409:１３２人目の素数さん
09/05/19 05:08:24
本気かネタ振りかわからんな

410:１３２人目の素数さん
09/05/19 06:32:29
麻雀のテンホーとチーホーは、どちらがあがりやすいか

411:１３２人目の素数さん
09/05/19 07:41:57
一巡目はジハイが出やすい。

412:１３２人目の素数さん
09/05/19 07:48:55
おまえは雀鬼会を敵に回した。

413:１３２人目の素数さん
09/05/19 14:39:52
>410　天和

414:１３２人目の素数さん
09/05/19 17:39:18
有界で凸な立体Tは、どの平面に正射影しても、その面積が一定である。
このとき立体Tは球であると言えるか。

415:１３２人目の素数さん
09/05/19 21:21:39
テンホーとチーホーが同時に入った場合、あがれるのはテンホーのほうだからな。
しかしそれがどれほどの差というのかｗｗｗ

416:１３２人目の素数さん
09/05/19 22:53:05
>>414
言えるが、どう証明したものか…

417:１３２人目の素数さん
09/05/19 23:11:45
>>415
親はランダムに切るわけではなく、あくまでの自分の不要牌しか切らないので
そんな単純な話じゃない

418:１３２人目の素数さん
09/05/19 23:18:52
>>416
本当に言えるんかな？
正三角形をふくらませたような図形で高さが一定なのがあるけど、
あれって正射影させると長さが一定だろ？
あれの立体版みたいなのってないのかな？

419:１３２人目の素数さん
09/05/19 23:51:37
定幅曲線ね

420:１３２人目の素数さん
09/05/20 00:07:03
>>389 の根を求む。

421:１３２人目の素数さん
09/05/20 00:17:12
>>418
「正射影の面積一定」ではなく、
「幅一定」ということであれば、
ルーローの三角形に似た四面体っぽい図形が作れる。
（ただし、単に４点を中心とした球の交わりではなく、エッジ部分を削って調整する必要あり）
面積一定だと、制約がきつ過ぎるから、球しかなさそうだが、証明は知らん。

422:１３２人目の素数さん
09/05/20 00:17:21
>>420

x + 1/x = t とおくと、x^2 -1 + 1/x^2 = t^2 -3,

1 +(√2)x -x^2 +(√2)x^3 + x^4 = (x^2){t^2 +(√2)t -3},
　t = (-1±√7)/√2,
　x = -(1+√7)/2 ±(1/2)7^(1/4),

　1 -(√2)x -x^2 -(√2)x^3 + x^4 = (x^2){t^2 -(√2)t -3},
　t = (1±√7)/√2,
　x = (1+√7)/2 ±(1/2)7^(1/4),

近似値　0.475679456437866… と　2.10225601813565…

423:１３２人目の素数さん
09/05/20 01:24:20
>>415
本来のチーホーか今風かによるかも

424:１３２人目の素数さん
09/05/20 03:44:45
>>415
地和が成立しないのは、なにも親が天和したときだけに限らない。

425:１３２人目の素数さん
09/05/20 04:03:58
どうでもいいが、役満がらみのローカルルールって、洒落にならんよな。
事前に全部確認なんてほぼ不可能だし。

「ロン！人和！」
「そんな役ねーよ。なんだそれ役なしじゃん。チョンボね」

426:１３２人目の素数さん
09/05/20 04:07:33
>>425
雀荘なら事前に確認できるようになってるだろ。
個人でやる場合は知らん。　

実施に打つと
役満がらみじゃないローカルルールのほうが
はるかに洒落にならん。

427:１３２人目の素数さん
09/05/20 18:08:11
>>414
未解決問題？

428:１３２人目の素数さん
09/05/20 18:36:42
>>421
> （ただし、単に４点を中心とした球の交わりではなく、エッジ部分を削って調整する必要あり）

( ﾟ∀ﾟ)＜詳しく聞こうか！

429:１３２人目の素数さん
09/05/20 19:59:15
>>428
このへんで発見
URLﾘﾝｸ(www.geocities.co.jp)

430:１３２人目の素数さん
09/05/21 14:57:29
ある有界で凸な立体Tは、どの平面で断面図をとっても、断面が相似である。（ただし、点になる場合や、断面が存在しないケースは除いて考える）
このとき、立体Tは球であると言えるか。

431:１３２人目の素数さん
09/05/21 22:57:33
>>429
( ﾟ∀ﾟ) ＜かたじけのうござる！

432:１３２人目の素数さん
09/05/24 16:51:28
>>309
1963年度京大に似たような問題が出されてたな。

433:１３２人目の素数さん
09/05/24 22:38:32
随分昔の話だな。

いろんな意味で。

434:１３２人目の素数さん
09/05/25 00:35:44
>>432->>433
詳しく！

その昔、「大学への数学」の東京出版が、CD-ROMで、
東大と京大の数学の過去問を出してたけど、また出してくれんかな～

435:１３２人目の素数さん
09/05/25 03:46:14
ずっと昔に作ったままお蔵入りにしてたやつ。

Ｗ氏は自然数を1から順に次のルールに沿って読み上げていく。

(ルール) 3の倍数と十進法表記で3のつく数字を飛ばす。

すなわち、1、2、4、5、7、…、11、14、…である。このときＷ氏がn個目に読み上げることになる自然数x(n)をnを用いて表せ。

436:１３２人目の素数さん
09/05/25 04:38:33
>>434

こんな問題

「△ABCと△DEFにおいて、AB=DEとし、それぞれの外接円の半径は等しく、また内接円の半径は等しいとする。
そのとき二つの三角形は合同になるか。理由をつけて答えよ」

聖文社より京大50年問題集が出てたので、その本より引用した。

437:１３２人目の素数さん
09/05/25 06:39:07
>>436
ありあとん！

438:１３２人目の素数さん
09/05/25 06:40:18
>>437
アリアハン

439:１３２人目の素数さん
09/05/25 13:02:08
>>435
それなんてナベアツｗｗｗ

440:１３２人目の素数さん
09/05/25 16:03:00
k桁の自然数Nを10進数表記したとき、0でない桁の個数をf(N)とする。
例）N=105502,f(N)=4　　、　N=100,f(N)=1など
このとき、f(N^2)＜f(N)なるNを一つ求めよ。存在しないならその理由を示せ。

----

あらかじめ言っておくと、解答は用意してない。

441:１３２人目の素数さん
09/05/25 17:37:26
>>440
４０４　そのような問題は存在しません

404^2=163216

442:１３２人目の素数さん
09/05/25 18:29:30
k桁の自然数Nを10進数表記したとき
↑
表記する前のk桁って何だろう

443:１３２人目の素数さん
09/05/25 18:40:00
24495^2=600005025.

444:１３２人目の素数さん
09/05/25 19:05:39
計算機って便利ね

445:１３２人目の素数さん
09/05/25 19:30:02
316227766017^2=100000000000102500044289.

446:１３２人目の素数さん
09/05/25 19:43:59
14142135623731^2=200000000000001400410360361

447:１３２人目の素数さん
09/05/25 20:34:31
>>443-446
うれしそうに書いてるところ申し訳ないのだが
・・・逆なんだけど

448:１３２人目の素数さん
09/05/25 20:40:29
何が逆なんだ？

449:１３２人目の素数さん
09/05/25 20:42:47
>>447
N=24495
f(N)=5
f(N^2)=4
f(N^2)<f(N)
だけど何が逆？

450:１３２人目の素数さん
09/05/25 20:47:29
そういえば問題中のk使ってないな

451:１３２人目の素数さん
09/05/25 21:38:49
2^24495=600005025
2^316227766017=100000000000102500044289
2^14142135623731=200000000000001400410360361

452:１３２人目の素数さん
09/05/25 21:45:27
なんだその記法

453:１３２人目の素数さん
09/05/25 22:04:06
自然数Nを10進数表記したとき、0でない桁の個数をf(N)とする。
例）N=105502,f(N)=4　　、　N=100,f(N)=1など
このとき、f(N^3)＜f(N^2)＜f(N)なるNを一つ求めよ。存在しないならその理由を示せ。

454:１３２人目の素数さん
09/05/25 22:12:03
いやです。

455:１３２人目の素数さん
09/05/25 22:15:11
>>414
結局、これどうやんの？

456:１３２人目の素数さん
09/05/25 22:31:28
f(N^3)<f(N)
これが絶望的

457:１３２人目の素数さん
09/05/26 00:28:49
>>453
直感だが、sqrt(10^(6k+1) + 1) - [sqrt(10^(6k+1) + 1)] が十分小さくなるようなkの値をとってくれば良いんじゃないだろうか……
いや、スマン適当。

458:１３２人目の素数さん
09/05/26 01:16:27
十進数って書いたほうがいい

459:１３２人目の素数さん
09/05/26 06:55:30
>>451みたいな数を研究してたサイトがあったな

460:１３２人目の素数さん
09/05/26 06:57:15
ここに書ききれないぐらいでかい数になりそう

461:１３２人目の素数さん
09/05/26 09:34:55
>>459
ｋｗｓｋ！

462:１３２人目の素数さん
09/05/26 13:08:17
>>461
十進表示で0を含まない自然数Nを二乗した数N^2が0を出来るだけ長く含む(Nの桁数に対する割合で)ものを一覧にしていて、上記の意味で一定以上の長さで0を含むものが有限であるとか示して、リストもあったと思った。ただ、どこにあったか思い出せん。

463:１３２人目の素数さん
09/05/26 15:40:00
使う数字が少ない平方数などならここにある。
URLﾘﾝｸ(www.asahi-net.or.jp)

464:１３２人目の素数さん
09/05/27 01:18:15
追いかけるだけで精一杯だね
てか、追いかけることすらできない…

465:１３２人目の素数さん
09/05/27 02:04:41
それは精一杯と表現していいのか？

466:１３２人目の素数さん
09/05/27 17:18:04
４×４の正方形のマスにおいて、左下の頂点からスタートし、線上を通り、右上の頂点まで辿り着く道順は何通りあるか。
ただし、最短か否かは問わず、同じ線上を通ってはならないものとする。

467:１３２人目の素数さん
09/05/27 17:45:37
>>466
無理

468:１３２人目の素数さん
09/05/27 19:44:29
ウィンドウズのフリーセル。並べ替えに失敗すると手詰まりか、
同じカードペアを永遠に並べる事しか出来なくなる。後者の場合、
1ペアで繰り返しになる時と２ペアでの場合がある。さて、このパターンで
「3ペア以上は存在しない」これを証明せよ。証明できるとは限らない。

469:１３２人目の素数さん
09/05/28 01:52:40
＞同じカードペアを永遠に並べる
意味がわからん

470:１３２人目の素数さん
09/05/28 02:21:46
>>469
フリーセルの必殺技

471:１３２人目の素数さん
09/05/28 06:51:02
A君がB君をあるゲームに誘った。
A君“B君、ゲームをしよう。二人で1から交互に順番に数字を数えていって100と言った方が負け。一回につき三つまで数を言うことができる。僕が先攻ね”
B君“わかったよ”

何回かやったがA君の全勝
B君“たまには僕の先攻にしてよ”
A君“いいよ、でもちょっとルールを変えて101と言った方が負けにしよう”
B君“いいよ”
やっぱりA君の全勝

A君の戦略を簡単に説明せよ

472:１３２人目の素数さん
09/05/28 08:55:51
>>471
自然数という制限もないのに100や101を言ったBがマヌケなだけ

473:１３２人目の素数さん
09/05/28 11:45:08
>>471
小学生のときにこれ研究したなー。
↓そのときの解答。

言ったら負けな数字を　M　（この場合100や101）
増やせる数の下限　a　（この場合１）
増やせる数の上限　b　（この場合３）
としたとき、
先攻は　（M-1）mod（a+b）　を宣言。
ただしこれが0の場合は後攻になる。

あとは(a+b)-（相手の増やした数）　を増やせばよい。

474:１３２人目の素数さん
09/05/28 11:56:53
>>471
100を言えば負けは、すなわち99を言えば勝ち。
先攻を選び99を4で割った余り3から以後7,11,1519,……,99を言えば勝ち。
101を言えば負けの場合は100を言えば勝ち。
100を4で割った余りは0だから、後攻で4,8,12,……100を言えば勝ち。
常識だね。

475:１３２人目の素数さん
09/05/28 13:10:38
【先手必勝なゲームを探せ！！】
ｽﾚﾘﾝｸ(math板)

476:１３２人目の素数さん
09/05/28 15:13:03
「二人で1から交互に順番に数字を数えていって100と言った方が負け。」なんだから
口には出さず100や101を心の中で数えればよい。負けなど無くなる！

477:１３２人目の素数さん
09/05/28 15:18:02
>>476
意味が分かりません。

478:１３２人目の素数さん
09/05/28 22:42:32
>>468
URLﾘﾝｸ(www.dotup.org)
3ペアってこうですか？わかりません

479:１３２人目の素数さん
09/05/29 21:52:49
>>466
こんな問題、解けるやついるの？

480:１３２人目の素数さん
09/05/29 22:22:44
>>466
色々と計算式を考えてみてもどこかで同じルートだったり抜けがあったりで上手く行かない。
難しいからプログラムでも組んでみようかと思ったがどういうアルゴリズムにすべきか・・・
虱潰しで行くにしても判定が難しいし一回判定したルートを保存するのも大変。

481:１３２人目の素数さん
09/05/29 23:01:52
定石で行けば頂点に適当に順番をつけて、幅優先探索か深さ優先探索だなぁ。

482:480
09/05/29 23:45:49
通る道と通らない道の組み合わせを全通りチェック。
一筆書きの要領で開始点と終了点以外で交点が奇数の部分があれば除外。

というプログラムを組んだが異様なほど時間がかかる。
しかも何か間違えてそうで怖い。

483:480
09/05/29 23:51:19
まあ３流プログラマなんでお世辞にも効率の良いアルゴリズムとは言えないんだが・・・
このペースだと終わるまで3時間くらいか。

組み合わせ自体が（２の２０乗）×（２の２０乗）だし。

・・・これ間違ってないよね？

484:１３２人目の素数さん
09/05/29 23:55:13
>>483
対称性から、始めの一歩を指定しておけば、半分になるぞ！

485:480
09/05/29 23:58:23
>>484
おお、そうだった！
サンクス！

処理が終わったらまた書き込む。
合ってるって確信できないのがアレだけどｗ

486:480
09/05/30 00:18:13
たった今欠陥に気付いた。

組みやすくするために左上から右下というルートで考えてたんだが、

┯━┯━┯━┯━┓
│ 　│ 　│ 　│ 　┃
├─┼─┼─┼─┨
│ 　│ 　│ 　│ 　┃
├─┼─┼─┼─┨
│ 　│ 　│ 　│ 　┃
┏━┓─┼─┼─┨
┃ 　┃ 　│ 　│ 　┃
┗━┛─┴─┴─┨

これでもカウントされてしまう。

つながってるかも判定入れないと・・・

もうギブアップ。

487:１３２人目の素数さん
09/05/30 00:36:42
諦めたらそこでry

488:１３２人目の素数さん
09/05/30 00:42:01
∠ABC=24°の菱形ABCDがあって、
線分BCのC側の延長上に点Eを、∠CDE=30°となるようにとるとき、
∠DAE=30°となることを証明してちょ。

489:１３２人目の素数さん
09/05/30 01:39:48
>>480
漏れのプログラムでは１８４通りとでた。
計算時間は0.2sec

490:489
09/05/30 01:41:57
あ、しもた。
4x4の解釈間違ってるしｗ
3x3でやっちゃった。

491:489
09/05/30 01:44:56
4x4でやり直したら8512通り、計算時間は6.1secになった。

492:１３２人目の素数さん
09/05/30 01:59:07
>>491
プログラムの素人に分かるように解説期盆濡！

493:１３２人目の素数さん
09/05/30 02:07:00
>>480
同じ組合せでも道順は複数あることはわかってるよな？
．．．って、もうギブしてたかｗ

494:１３２人目の素数さん
09/05/30 02:07:52
オンライン整数大辞典様にはばっちり収録されてた

495:１３２人目の素数さん
09/05/30 02:08:01
単純な幅優先探索しか使ってないっす。

496:491
09/05/30 02:22:17
ヒントだけ言うと用意するクラスは
頂点、ルート、ルートの集合の３つ。

それぞれのクラスに用意したメソッドは

頂点
｛
その頂点に隣接する頂点の集合を返す関数
その頂点が4x4のマスの中にあるかどうかを返す関数
｝

ルート
｛
自分自身から一つ頂点を増やしたルートの集合を返す関数
同じ頂点を２度、通ってないかを返す関数
ゴールにたどり着いたかを返す関数
｝

ルートの集合
｛
自分が持っているそれぞれのルートに対して一つ頂点を増やしたルートを集めたルートの集合を返す関数
｝

後は自分でアルゴリズムを組み立てて見れ。

497:１３２人目の素数さん
09/05/30 02:40:00
それは同じ頂点を通らないもの。

498:１３２人目の素数さん
09/05/30 02:42:11
>>496
＞同じ頂点を２度、通ってないかを返す関数
とあるが、今回は同じ頂点は２度通ってもいいというルールと認識しているぞ。
２度通ってはいけないのは「同じ道」
「辺の集合」を持たないといけないから結構面倒。

499:491
09/05/30 02:43:20
あ、なるほど～
やけに簡単な問題に悩んでるなと思ったら、漏れが問題勘違いしてたか。

500:491
09/05/30 03:00:32
一応、プログラム書き直して3x3でやったら800通りになったけどみんなの結果と一致してる？
4x4は結構計算時間が掛かりそうだ。

501:１３２人目の素数さん
09/05/30 03:19:37
通る道は同じでも道順が違うのも考慮しなきゃいけないのか・・・
ℓとΩみたいなので。

わかりづれえorz

502:４９１
09/05/30 03:20:36
幅優先探索なもんだからメモリ食い尽くしちまったぜｗ
ヌルポきたこれｗｗｗ

503:１３２人目の素数さん
09/05/30 03:22:36
NP完全・・・だと・・・・？？？？

504:１３２人目の素数さん
09/05/30 03:30:00
数え終わったのを記憶しておく必要がないから深さ優先で。

505:491
09/05/30 04:03:02
ヌるぽに切れてC++で書き直してやった。
漏れのプログラムでは4x4の結果は323632通りになったよ。
計算時間は9秒。
アルゴリズムは同じく幅優先。
あってるかどうかは知らね。

506:１３２人目の素数さん
09/05/30 04:06:04
オンラ（ｒｙ
によると合ってる
素辺な経路っていう用語があるのね

507:491
09/05/30 04:15:23
>>506
さんくす。コレで気持ちよく寝れるｗ
ま、>>492は幅優先探索とか深さ優先探索は勉強しといて損はないぞ。

508:１３２人目の素数さん
09/05/30 04:35:57
>>466　の問題について

準備：
２×２の正方形の連結　（田の字）　で考える。
頂点に名を付ける　。　左下から　右へ　ABC、中段左からDEF　、上段左からGHI
Aがスタート、Iがゴールである。
スタートからゴールまで同じ道を２度以上通らずに辿る道順を正規のルートと呼ぶ。
問題は、そのような道順が何種類あるのかを数えることである。

GHI
DEF
ABC

道順　ABEHGDEFI　は　正規のルートである
道順　ABEDGHEFI　は　正規のルートである

このふたつのルートは、道「順」である以上、区別されるべきか？
それとも、通る道は同じなので、同一視するべきか？

509:１３２人目の素数さん
09/05/30 04:37:08
あ、すまん。501が先に書いてた。

510:１３２人目の素数さん
09/05/30 05:58:30
面倒なのでperlでｗ
しらみつぶしに樹型図を描くようなイメージの素朴なアルゴリズムで探すと、
（なんせperlなんで）数分かかったが、同じく323632通りという結果が出た。

基本的には、現在見ている経路と、その経路上でまだ試していない分岐だけ
覚えておけばいいので、メモリーは全然食わないし、真面目にcとかで書けば
時間もそんなにかからないとは思うが。

ちなみに、２×２は16、３×３は800。
これらは経路リストも出したが、やたら長い経路をたどってみると
なんかPipeDreamみたいになってて笑える。

511:１３２人目の素数さん
09/05/30 06:03:15
4*4の計算が1913年後に終わるorz
おやすみなさい

512:１３２人目の素数さん
09/05/30 06:40:55
んじゃ、n×nの素辺な経路の
経路の長さの最大値は2n^2であること、および、
n≧3の場合は最長経路の描く図形が対角線について対称な２種類しかないこと
を示せ

ってのはどう？

513:１３２人目の素数さん
09/05/30 06:52:12
>>512はちょっと間違ったので書き直し。

n×nの素辺な経路の長さの最大値は2n^2であること、および、
n≧3の場合は、最長経路の描く図形が、向きの違うものを区別すると
ちょうど４種類あることを示せ。

514:１３２人目の素数さん
09/05/30 10:26:23
>>510
Oops!!
Well done.

515:１３２人目の素数さん
09/05/30 10:52:24
＞n×nの素辺な経路の長さの最大値は2n^2であること
nが偶数の場合は出来たけど、奇数の場合は評価が少し面倒そうだな。

516:１３２人目の素数さん
09/05/30 11:44:22
URLﾘﾝｸ(www.research.att.com)

517:１３２人目の素数さん
09/05/30 12:11:56
URLﾘﾝｸ(www.research.att.com)

このサイト便利だな

518:１３２人目の素数さん
09/05/31 04:34:51
n×mができるやつ。　ただし5×5くらいが限界。
それ以上は、経路数が32ビットを超えるのでlong　long　int　をつかうとかして。
4×4がPemM　1.6GHzで5秒くらい。５×５はたぶん半日以上かかると思う。
↓
#include　<stdio.h>
#define　DX　4
#define　DY　4
void　main(void)
{
int　r[DX*(DX+1)+DY*(DY+1)],m[2][DX+1][DY+1],c=0,x,y,p,n;
memset(r,0,sizeof(r));
for(;;){
memset(m,0,sizeof(m));
for(x=y=p=0;p<DX*(DX+1)+DY*(DY+1);p++){
if(r[p]&1){
　if(r[p]　2){
　　if(--y<0||!(m[1][x][y]^=1))break;
　}else　if(!(m[1][x][y]^=1)||++y>DY)break;
}else　if(r[p]&2){
　if(--x<0||!(m[0][x][y]^=1))break;
}else　if(!(m[0][x][y]^=1)||++x>DX)break;
if(x==DX&&y==DY){
　c++;
　break;
}
}
for(n=p;n>=0;n--)if((r[n]=((r[n]+1)&3))!=0)break;
if(r[0]==(DX==DY?1:2))break;
}
printf("%d",c*(DX==DY?2:1));
}

519:１３２人目の素数さん
09/05/31 08:04:36
× if(r[p] 2){

○ if(r[p]&2){

520:１３２人目の素数さん
09/05/31 13:05:45
1x1　2
1x2　4
1x3　8
1x4　16
1x5　32
2x1　4
2x2　16
2x3　72
2x4　335
2x5　1562
3x1　8
3x2　72
3x3　800
3x4　9754
3x5　121130
4x4　323632
4x1　16
4x2　335
4x3　9754
4x5　11171466
5x1　32
5x2　1562
5x3　121130
5x4　11171466
5x5　1086297184
計算の結果

521:１３２人目の素数さん
09/05/31 13:50:00
URLﾘﾝｸ(groups.google.co.jp)

522:468
09/06/01 03:16:34
>>478
消されてて分からないけど、実際にプレイして3ペアに到達したのなら反例を
見つけた事になるね。次の問題は当然、特定カード内での操作しか出来なくなる
、その最大枚数は？　という事だけど。現在値は６ですか。（未確認情報）
個人的には４　しか見てない。かなりやってるけど見ないね。

523:１３２人目の素数さん
09/06/01 05:15:21
>>522　
ゲームを終わらせようとしてると３ペアにはまずならない
わざと３ペア以上を作ろうとしないと

524:468
09/06/01 09:27:05
>>523
それでも作ろうとして作れるのならそれが法則なんで。ただし、フリーセル
を基準にした場合を想定してるのでこの証明は相当に厄介だと思われ。
最大で６４０００位のゲームが存在するけど、トランプの順列からすれば
ほんの一部でしか無いからね。

525:１３２人目の素数さん
09/06/01 10:28:13
>>524
何が言いたいのかよくわからない。

>>523は522の　「かなりやってるけど見ない」というのに返しただけなんだが
522がわざと作ろうとしてやっていてできないというのなら申し訳ないが

526:468
09/06/01 10:35:54
>>525
まず、面白い問題とは思うが自分はその答えを知らない。ココ重要。
だから経験則から言える事を言ってるだけ。証明はしたい人もしくは出来る人が
してくれ。そういう事。

527:１３２人目の素数さん
09/06/01 11:19:00
「実際にプレイして」３ペアに到達する必要はあるのか？

528:468
09/06/01 11:41:28
>>527
さあ・・。でもフリーセルはごく一部のゲームを除いてほとんど全てが
クリア可能になってる。ここで問題なのはクリアできずに終わってしまう
手順。しかし実際にはクリア出来ない初期設定の方が膨大と思われ。
しかし、それはこの証明には関らない。何故ならそれはフリーセルの仕様に
反するから。

529:468
09/06/01 11:49:14
それにわざと３ペアを残そうとしても相当に苦労すると思うよ。やってみれば
分かるがクリアする方がむしろ簡単かも。将棋みたいなゲームもそう。
わざと負けるのが簡単なのは相手が勝とうとしてる場合だけ。

530:１３２人目の素数さん
09/06/01 11:49:56
>　　しかし実際にはクリア出来ない初期設定の方が膨大と思われ。
?
なぜそう思う？

>　しかし、それはこの証明には関らない。何故ならそれはフリーセルの仕様に　
反するから。　

仕様に反するの意味がよくわからないのだが
フリーセルのルールに
カードの乱数（のようにみえるもの）による初期配置に関するルールも
加えようと言うことなのか？

トランプよく切って、フリーセルの初期状態のようにテーブルに並べたものは
フリーセルのようなものであって、フリーセルのルールに反すると？

531:１３２人目の素数さん
09/06/01 12:01:27
＞　それにわざと３ペアを残そうとしても相当に苦労すると思うよ。

何故そう思う？　
URLﾘﾝｸ(hp.jpdo.com)

532:468
09/06/01 12:11:03
>>530
例えばクリアできないのはゲームＮＯ．－１、－２
普通にカードを順序良く並べただけだが、ルール通りにやっても絶対に無理。
という事は、ここから発生する順列は全てアウトという事。それは別の見方を
するとクリアされた状態から逆操作をして５２！通りの初期値を作ることが
出来ない事を意味してる。
＞トランプよく切って
それはダメ。あくまでも正規のフリーセルゲーム（ＮＯ．を指定できる）で
ないと。

533:468
09/06/01 12:18:21
それともう一つ条件を付ける必要があった。「フリーセル」は
４つとも埋まっていて空かないものとする。

534:１３２人目の素数さん
09/06/01 12:18:53
>>532
＞　ここから発生する順列は全てアウトという事。

ここから発生する順列ってなんのこと？　

URLﾘﾝｸ(hp.jpdo.com)

535:１３２人目の素数さん
09/06/01 12:21:42
＞　それはダメ。あくまでも正規のフリーセルゲーム（ＮＯ．を指定できる）でないと。

ではフリーセルが指定したナンバーを元にトランプの並びをどう決定しているのかを教えてくれないかな。
でないと、「フリーセルが並べるパターン全て」という証明はできないよ。

URLﾘﾝｸ(hp.jpdo.com)

536:１３２人目の素数さん
09/06/01 12:23:01
>>533
フリーセルがひとつでも開いていれば手詰まりではないのだから
その条件は要らないと思うが？

537:１３２人目の素数さん
09/06/01 12:23:53
４ペア　ワロス。

538:468
09/06/01 12:33:41
>>535
君の思考が理解出来ないが、それを知る必要はないでしょ。知ったところで
ゲーム内容は変化しないよ。
>>536
その条件は問題を単純化する為に敢えて必要。そうしないとセルが空いていても
クリア不能な状態を定義する必要があるからね。

539:１３２人目の素数さん
09/06/01 12:36:30
３ペアやその変形や４ペアを作ってみたが
３ペアが作れないパターンのほうが少ないように感じるよ。

何度もやってるのにできない、というのは作る気がないのか
よほど操作が下手なのかのどちらかだと思う。

540:１３２人目の素数さん
09/06/01 12:37:24
>>538
＞　それを知る必要はないでしょ

それがわからない状態で、どうやって全てのパターンについての証明をするのか？

541:１３２人目の素数さん
09/06/01 12:39:29
フリーセルには幾つかのバージョンがあるようだけど
全てのフリーセルで、同じナンバーを入力すると同じパターンで始まるの？

542:１３２人目の素数さん
09/06/01 12:40:54
>>538
>>536の言うように「ひとつでも空きがあるなら手詰まりでない」の定義で十分だと思うが。

543:１３２人目の素数さん
09/06/01 12:43:04
これだけ反例を貼られてもなっとくしない468ってなんなの？

544:468
09/06/01 12:50:18
>>542
何故そういう風に考えるのか分からないけど、どんな状態、組み合わせであろうと
そこからクリア出来ないのならそれは手詰まり（の一種）ですよ。

545:１３２人目の素数さん
09/06/01 12:52:19
>>524
＞　最大で６４０００位のゲームが存在するけど

うちのフリーセルは１～１００００００の数が指定できるんだけど
結構かぶってるの？

546:１３２人目の素数さん
09/06/01 12:54:23
>>544
だからそれはそう定義するからでしょ。　よくわからん人だね。　
定義の問題だと言ってるのに別の定義で反論されても意味ないでしょ。

547:１３２人目の素数さん
09/06/01 12:58:53
で、反例はもう納得できたのか？
それとも自分でやったわけじゃないから未確認か？

548:468
09/06/01 13:05:32
>>545
そうなんだ。一応ですね、Ｍ＄版のものを想定してますんで。Ｖｉｓｔａ
とか７ではそうなってるのかな。その辺の事情は知らないんでスマン。
>>546
分かりました。では５３８の条件は忘れて下さい。
３ペアが作れるという人、暇ならその手順を書いてくれれば有り難いです。
例えば　Ｓ９（スペード）up,HA + (home cell),D3→C4
みたいな感じで。ゲームＮＯ．は３２０００以下頼みます。

549:545
09/06/01 13:13:11
>>548
うちはXPで、それについていたフリーセルが100000まで指定できるんですが。

550:468
09/06/01 13:17:48
>>549
うちは２０００なんで３２０００までです。でもＮＯ．を指定して
同じＮＯ．で同じゲームになるなら基本的には同じだと思います。
勘違いを誘ってるようですが自分は面白そうな問題を出しただけで
自分でそれを解決出来るなどとは言ってませんのでよろしく。

551:１３２人目の素数さん
09/06/01 13:30:28
ゲーム#3644で以下のキーを入力
6523121380808080468400400804606060

552:468
09/06/01 13:34:59
>>551
納得しました。私の仮定は完全に誤りでした。
連打スマンこってしたorz

553:１３２人目の素数さん
09/06/01 14:08:24
一段落したところで、暇な人は>>488でも考えてくれ

554:468
09/06/01 19:39:48
>>539
負け惜しみで言うけど５５１みたいなあり得ない操作は下手ですよええ。
でも普通にクリアするスピードはここいらの住人ではトップクラスと思ふ。
数学とは関係無いですよはい。

555:１３２人目の素数さん
09/06/01 19:54:44
>５５１みたいなあり得ない操作

普通にゲームをクリアするときとは目的が違うのだから
その目的のためには>>551の操作はあり得ないどころか
大変的確な操作でかつ特にトリッキーな操作でもないと思うがどうか。

手詰まりペアを多く作るという目的のときに
どこに着眼してどのような思考をすればいいかすら
考えていないのではないか？

556:１３２人目の素数さん
09/06/01 20:04:01
>>554
９９８連勝中。

557:468
09/06/01 20:04:12
>>555
ま、通常必要無い思考なので。クリアを目的としても的確な思考は要る。
それでも全ゲームを一発クリアできる人間がいるとは思えないし。
それも、思えないというだけの話でいないという証明は当然無いね。

558:468
09/06/01 20:11:01
>>556
強いですね。ＮＯ．１から順番にといて３０連勝までしてやめますた。
そういうコツコツ作業が嫌いなので。

559:１３２人目の素数さん
09/06/01 20:55:32
>>557　
554や550あたりでおまえの言っていることを要約すると
「自分で考える気もない問題を、面白い問題だと思って出した」と言っているんだが
そういうのは読んでいるほうからするとどう感じると思う？

560:468
09/06/01 21:12:28
>>559
別にあんたに説教される筋合いは無い。この問題も、もしかしたら面白いかも知れない。
考えるのは好きでしょ？　自分は得意ではないので。自分が難しいと感じる
事を瞬時に理解する人間もいるっしょ。だいたいこのスレとか、そういう
趣向が無ければ意味無いジャン。

561:１３２人目の素数さん
09/06/01 21:33:40
こんなアホにかまってないで次行こうぜ

562:１３２人目の素数さん
09/06/01 21:39:23
何か面白い趣向でもあるのかと思った人が突っ込みを入れてるのに
まるで理解していない>>468

何もないことがわかったので>>559は怒っているわけだが
気づくの遅すぎだよ

563:468
09/06/01 21:39:47
そうそう、次へ行かないと。

564:１３２人目の素数さん
09/06/01 21:41:48
普通は何か準備をして出題するよなあ

565:１３２人目の素数さん
09/06/01 21:46:32
最初の日本語が変な点でスルーすべきだったな

566:１３２人目の素数さん
09/06/01 21:50:31
これに懲りたらアホな問題出すなよ。

567:１３２人目の素数さん
09/06/01 22:18:14
468からは、フリーセルに対する妙なプライドが垣間見られる。
>>557なんて、>>555への返答になってないし。

フリーセルを「クリア」する能力と、具体的な問題に対して
「反例」を構成する能力は全くの別物でございます。

568:１３２人目の素数さん
09/06/01 22:23:42
今更なんだがローカルルールで
・出題者は回答を用意してから書き込むこと
とか付け足しちゃどうだろう。

569:１３２人目の素数さん
09/06/01 22:26:09
過去ログまとめにスレ上での未解決問題もちらほらあるのを考えると
兼ね合いが難しいね

570:１３２人目の素数さん
09/06/01 23:30:43
・出題者は自分で面白いと思っていない考える気もないような問題は出さないこと

これだけで馬鹿よけには十分だろ。

571:１３２人目の素数さん
09/06/01 23:40:05
>>567
＞　>>557なんて、>>555への返答になってないし。　

してるよ。
↓
＞　ま、通常必要無い思考なので。

「考えていないのではないか？　」　きかれて、そう答えたら
考える気もないという返事だろう。

次ページ