|
triacontahedron lover |
|
9枚のとき、27枚のとき、81枚のときで考えてやっと確信が持てました。
マス目書いて0,1,2,3,4,9,10,12,13,...と順に丸をつけていくとようやく規則性が見えてきました。 |
|
10月2日（木） 0:25:28
42451 |
|
おーちゃん |
| カントール集合ぽい話ですね |
|
10月2日（木） 0:26:39
42452 |
|
triacontahedron lover |
|
自分で書いておきながら2を数えているとは何事じゃ
カントール集合について調べてきましたが確かにそれっぽかったです |
|
10月2日（木） 0:29:21
42453 |
|
CRYING DOLPHIN |
|
直感で、3進法で2を使わない数を列挙すればいいのかなーと思ったけど、そうでもないようで…。
例えば、0〜8のときは「0,1,3,4」以外にも「0,1,3,8」なんて選び方もあったり。 ということで、問題の背景がまったくわからぬままです。。 |
|
誰もいない市街地
10月2日（木） 0:31:56
HomePage:ブログもある 42454 |
|
triacontahedron lover |
|
連投ごめんなさい
カントール集合みたいに考えるなら9枚のとき、81枚のとき、729枚のときと増えていくのがそれらしいですね ●●○ ●●○ ○○○ ↓ ●●○ ●●○ ○○○ ●●○ ●●○ ○○○ ○○○ ○○○ ○○○ ●●○ ●●○ ○○○ ●●○ ●●○ ○○○ ○○○ ○○○ ○○○ ○○○ ○○○ ○○○ ○○○ ○○○ ○○○ ○○○ ○○○ ○○○ こんな感じですよね。あってるでしょうか。。。 |
|
10月2日（木） 0:34:29
42455 |
|
しらす |
|
10^5以下の非負整数から、下記の条件を満たす1991個の数が選べることを示せ。
条件：どの三個を選んでも等差数列をなさない。 って数オリかどっかの問題が合ったことを思い出しました |
|
10月2日（木） 0:34:39
42456 |
|
しらす |
|
下のやつは1983年のIMO5番でした
問題文中の数値も1991じゃなくて1983みたいです(少なくとも2048以下ならいけそう) |
|
10月2日（木） 0:48:02
42457 |
|
おーちゃん |
|
私は3進数で1を使わない
0,2,6,8,18,20,24,26,…… というのを考えてました。（カントール集合） triacontahedron loverさんの記法を借りると ●○● ○○○ ●○● です。 No.42455は3進数で2を使わないパターンですね。 |
|
10月2日（木） 0:48:51
42458 |
|
Mr.ダンディ |
|
729＝3^6(枚)ということで、3進法に関係あるのではと考え
0,1,3,4,9,10,12,13,27 まで求めておいてから、これらを3進数に直すと 0,1ばかりからなるので 3進数で 1000000以下の 0,1ばかりからなるもの 2^6=64（個）としました。 「3進数で1,0ばかりからなる異なる２数を加えて どの位も2か0になることは ないので、その平均がこの群に存在することはない」という理由でよいのかな？ すると 0〜(3^n−1)までの範囲では ２^n(個） （難しくて、連続正解が途切れるピンチでした） |
|
10月2日（木） 1:44:06
42459 |
|
Jママ |
|
こんばんは
CRYING DOLPHINさんにとても近い考え方です 3進法で0と1のみで表せる0から728までの整数の数を数えました。 理屈は上手く説明できませんが(^^; 最大枚数は3^k枚であれば2^k枚でよいのか… まだよくわかっておりません(^^; |
|
10月2日（木） 1:00:09
42461 |
|
ベルク・カッツェ |
|
729までで65枚でなぜ合わないのかと思っていたら、よく見たら728までなので64枚でした。
疲れたので考え方が正しいかの検証は、日を改めて・・・。 |
|
10月2日（木） 1:03:13
42462 |
|
ベルク・カッツェ |
|
ちなみに、数字の間隔を考えて地道に法則を見つけてみました。
1、2、1、5、1、2、1、14、1、2、1、5、・・・・・・ |
|
10月2日（木） 1:05:11
42463 |
|
ハラギャーテイ |
| おはようございます。認証頼りでした。 |
|
山口
10月2日（木） 6:33:30
HomePage:制御工学にチャレンジ 42464 |
|
まるケン |
|
皆さんと同じように、小さい数字からためして法則を見つけ、７２８に拡張して６４枚にたどり着きました。
確認のため、プログラムを書き、いろいろ試したところ、とんでもないものを見つけてしまいました。 ０から順に調べ、カード群にある数字と新しい数字との平均になる数字がカード群にない場合はその新しい数字をカード群に加えます。 単純に０から順に調べると、 [0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 120, 121, 243, 244, 246, 247, 252, 253, 255, 256, 270, 271, 273, 274, 279, 280, 282, 283, 324, 325, 327, 328, 333, 334, 336, 337, 351, 352, 354, 355, 360, 361, 363, 364] の６４枚のカード群ができます。 しかし、しかしです。この中のたとえば120をスキップさせてみたところ、 [0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 121, 201, 228, 237, 240, 244, 245, 247, 256, 258, 259, 261, 270, 280, 283, 292, 297, 298, 306, 327, 330, 331, 334, 343, 346, 360, 496, 497, 525, 534, 588, 589, 597, 613, 616, 666, 670, 671, 675, 678, 687, 705, 706, 713, 715, 718, 728] と、７７枚のカード群ができてしまいました。 ということで、６４は最多ではなさそう、、、 じゃ、最多はいくつ？ |
|
ないしょ
10月2日（木） 12:40:04
HomePage:まるケンの部屋 42465 |
|
ユートニウム |
|
秘密のページが現れました！！
このようなモノがあったのですね。。。 |
|
10月2日（木） 11:52:48
42466 |
|
ユートニウム |
|
秘密のページが現れました！！
このようなモノがあったのですね。。。 |
|
10月2日（木） 11:58:49
42467 |
|
吉川マサル |
|
出先からです。
実はこの問題、最大性については証明できず、3進法を用いて64個の場合に作れることのみの思考で「これが最大だろう」と出題してしまいました。すみません…。 元ネタは、秋山仁さんの参考書で、3進法による解法もそこにありました。(が、最大性には言及していません。) 今後の対応については、帰宅(帰社)後に考えます。ご迷惑をおかけし、申し訳ありません。 |
|
10月2日（木） 13:02:53
42468 |
|
あめい |
|
難しかった(きちんと解けていないので「難しい」が正しい)です。
困ったときは何でもヒントにするぞ・・・ということで ７２９＝３＾６・・・・何乗を利用する？怪しい (今回は難しいので最大限のヒントを与えてやろうという？)マサルさんの例、０，１，４，５，９・・・・９がポツンと入る→３＾６→９＾３、９に関わる問題？ ということで ９つずつに数字を区切って並べると最初の９個が０，１，４，５，次の9個が９，１０，１２，１３、次の９個は全滅・・・とグループに入れるのが可能な数を入れていき、何か法則はないかと調べてみました。 すると(ここからがなぜだかわかりませんが)最初の９個の○○×○○××××のパターンが、９個をひとグループにしたときに追加できる数がある○、ない×のパターンにも踏襲されている。これはきっとこの９個ひとグループを９個まとめたものにも踏襲されているだろう・・ということで条件に合う数は、最初の９個は4個がＯＫ、９個を１個とした小グループ９個に４個がＯＫ、小グループ９個を１個とした大グループが９個に４個ＯＫ。ということで４×４×４＝６４となりました。 ここに入れたのは偶然？説明できる？みなさんのをみて、勉強します。 （それにしても今回、今年の連続アウトの危機でホッとしました、） |
|
10月2日（木） 13:31:31
42469 |
|
あめい |
|
#42465マルけんさん、#42468マサルさんの記事を見ないで、書き込みをしてしまいました。
マサルさん、パブロフの犬よろしくパソコンの前に立つ身としては毎回問題を出して下さり、感謝以外の言葉はありません。今回もきっとみなさんがいろいろ検討して下さるので、カントール集合？何それ？と(傍観しかできませんが)楽しませていただきます。 |
|
10月2日（木） 13:48:12
42470 |
|
まるケン |
|
おそらくですが、０から７２８でなく、０から３６４にすれば６４枚でよかったんだろうな、、、と思っています。
７２８だと後半が使わなすぎですよね。なので、ちょっとずらしたりすると、もう少しカードの枚数が増えるんでしょうね。 （現在、プログラム回して、７８枚の組み合わせを発見。まだあるかな？） |
|
ないしょ
10月2日（木） 13:58:02
MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋 42471 |
|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
うーむ，よく分からず，少しはまってしまいました。 729 = 3^6 なので何かありそうだな，と思ったものの，まずは具体的に調べてみるか，と思ったのが却ってよくなかったかも。 最大かどうかもよく分からないし，解法というよりも，思考の流れ，という感じですが，一応，こんな感じ。 まず，最初からいい加減ですが，0 は入りそうだな，というわけで，0 から始めて，0, 1, 3，で 3 個，を得ます。 ここで，一番最後の 3 をすべてに足したもの，3, 4, 6，はそれらの間では条件を満たす最大なので， これと，0, 1, 3，との間で条件を満たすようにすればよく，これは，0, 1, 3, 4，で 4 個。 次に，同様にすべてに 4 を足すと，4, 5, 7, 8，ですが，これと，0, 1, 3, 4，はうまくいきません。 仕方がないので，8 + 1 = 9 を追加した，0, 1, 3, 4, 9，の 5 個，を考えるとうまくいきます。これが例ですね。 そこで，0, 1, 3, 4, 9，を基に一番最後の 9 をすべてに足したもの，9, 10, 12, 13, 18，を考え， これと，0, 1, 3, 4, 9，との間で条件を満たすようにすればよく，これは，0, 1, 3, 4, 9, 10, 12, 13，で 8 個。 次はすべてに 13 を足しますが，これはやってみるとうまくいかず，13 + 13 = 26 の次の 27 を追加して， 0, 1, 3, 4, 9, 10, 12, 13, 27 で 9 個，を得ます。 ここまでやれば規則性も見えてきますが，念のためにもう一回やると， 0, 1, 3, 4, 9, 10, 12, 13, 27 と 27, 28, 30, 31, 36, 37, 39, 40, 54 で， 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40，の 16 個。 次のすべてに 40 を足すのとこれとはうまくいかず，40 + 40 = 80 の次の 81 を追加して， 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81，の 17 個。 結局， 0 〜 (3^n - 1)/2 は 2^n 個，0 〜 3^n - 1 も 2^n 個，0 〜 3^n は 3^n で終わる形で 2^n + 1 個， 証明は一応は数学的帰納法でできるでしょう。 ただし，あくまでも，カード群に 0 を含めるならば，ですし， 最大性も上記の構成法で明らかか，といわれると，ちょっと自信はありません。 この問題では，0 〜 728 = 729 - 1 = 3^6 - 1 のカードなので 2^6 = 64 枚，になります。 ここまで考えて，どうも 3 進法が絡んでいそうだな，と気付きました。 こういうことなのかなぁ。少なくとも上記の考え方の背景にはなるかな。 一般に，数を 3 進法で表すと 0, 1, 2 で表されますが， 0 〜 3^n - 1 では 0，1，2 の現れ方は等しく， 例えば 0 と 1 だけで表せる異なる数の２つの和は 0 と 2 だけになることはなく， したがってそれを 2 で割った平均は0 と 1 だけで表せない，と思います。 そこで，多分，この多分はかなり重い多分，0 と 1 だけでできる数を集めれば題意を満たすのでしょう。 これが正しければ，0 〜 3^n - 1 で 0 と 1 だけで表せる数の個数は 2^n 個なので， 題意を満たすカード群の枚数も 2^n 枚になります。 後は，掲示板を読んで勉強します。 |
|
ネコの住む家
10月3日（金） 18:00:24
42472 |
|
おーちゃん |
|
まるケンさんに触発されて、0,728,1,727,2,726,……という順序でチェックしていくプログラムで
0 1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 81 82 84 85 90 91 93 94 108 109 111 112 117 118 120 121 243 244 246 247 252 253 255 256 270 271 273 274 279 280 282 283 607 608 610 611 616 617 619 620 634 635 637 638 643 644 646 647 688 689 691 692 697 698 700 701 715 716 718 719 724 725 727 728 という80個の組み合わせは見つけました。 3進数で表すと 0[01][01][01][01][01] の 32個 10[01][01][01][01] の 16個 2[12][12][12][12][12] の 32個 の計80個になります。 最大性はまだわかりません。もっと少ない桁数で分析すると何か見えそうですが…… |
|
10月2日（木） 14:27:01
42473 |
|
スモークマン |
|
やっとこさぁ〜^^; (訂正しました…Orz)
729=3^6 じっさいは、728までなので… 天秤で考えると... 0,3^0,3^1,3^2,3^3,3^4,3^5 の分銅の組み合わせで釣り合わない=平均値はない... 0を足しても変わらないので、3^0〜3^5までの6個の分銅の複数個の和だけある。6C1+6C2+6C3+6C4+6C5+6C6=2^6-1 これに、0を加えることができるので…2^6=64 ♪ #42465 をみるとなんと!!! 64が最大じゃないんですねぇ ^^;… |
|
金即是空 ^^;v
10月2日（木） 15:03:18
42474 |
|
triacontahedron lover |
|
言われてみて再検証。括弧に入っているのは対称形です。
3枚のとき 0,2、0,1(1,2)で最大は2枚。 9枚のとき 0,2,6,8、0,2,3,5(3,5,6,8)、0,1,3,4(4,5,7,8)、1,2,4,5(3,4,6,7)、0,2,5,7(1,3,6,8) で4枚だと思いきや。 0,1,3,7,8 ●●○ ●○○ ○●● (0,1,5,7,8) ●●○ ○○● ○●● の5枚が最大だと気付いてしまいました。ちょっと考えてきます。 確かに後半をうまく使ってやると良い感じになりそうです。考えてきます。 |
|
10月2日（木） 14:48:36
42476 |
|
uchinyan |
|
掲示板を読みました。
う〜む，やはりかなりの難問のようですね。 アイディアとしては，カントール集合，3 進法，などがあるようですが， いずれも最大性の議論はなく，プログラム頼りの模様で， 最大は，64 枚ではなく，今のところは，#42481の 82 枚，の模様。 ところで，カントール集合って何？ 勉強します (^^; |
|
ネコの住む家
10月3日（金） 13:35:47
42477 |
|
ベルク・カッツェ |
|
私も数字の間隔と対照性が出てくることから、64が可能、そのやり方だと65にはあと1足りないところまでは確認できましたが、最大については検証できていません。
プログラムによる総当り以外で解く方法はあるのでしょうか。 |
|
10月2日（木） 15:54:24
42478 |
|
triacontahedron lover |
|
実験中。
9枚の時の4枚パターン0,4,5,7(1,3,4,8)もあった。 27枚の時の最大数は12っぽいのですが、9枚の時が最大値5個だったこと考えると13になる組み合わせもありそう。 とりあえず9枚の時の4枚パターンと最大パターンを組み合わせて12以上にする組み合わせを考えることにする。 感覚的には途中までは左右対称で真ん中らへんでうまくかわしていくといいような気がする。漠然としてますが。 |
|
10月2日（木） 15:57:34
42479 |
|
まるケン |
|
#42479
２７枚ということは、０から２６ですよね。 ２７枚程度だと、総当たりで調べても６秒くらいで答えが出ます。（環境にもよりますが、、、） 以下、最大１１枚の１２パターン。 [0, 1, 5, 6, 8, 14, 18, 19, 21, 25, 26] [0, 1, 5, 7, 8, 12, 18, 20, 21, 25, 26] [0, 1, 5, 7, 11, 16, 18, 19, 23, 24, 26] [0, 2, 3, 7, 8, 10, 15, 19, 21, 25, 26] [0, 2, 3, 5, 11, 15, 16, 18, 23, 24, 26] [0, 2, 3, 8, 10, 11, 15, 21, 23, 24, 26] [0, 2, 3, 7, 8, 10, 15, 19, 21, 24, 26] [0, 2, 5, 7, 11, 16, 18, 19, 23, 24, 26] [0, 1, 4, 6, 10, 15, 17, 18, 22, 23, 25] [0, 2, 3, 7, 8, 10, 15, 19, 21, 24, 25] [1, 3, 4, 8, 9, 11, 16, 20, 22, 25, 26] [1, 2, 5, 7, 11, 16, 18, 19, 23, 24, 26] |
|
ないしょ
10月2日（木） 17:34:19
MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋 42480 |
|
まるケン |
|
#42473 触発の触発で、、、
[0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 120, 121, 243, 244, 246, 247, 252, 253, 255, 256, 271, 279, 280, 283, 284, 291, 293, 294, 300, 301, 607, 608, 610, 611, 616, 617, 619, 620, 634, 635, 637, 638, 643, 644, 646, 647, 688, 689, 691, 692, 697, 698, 700, 701, 715, 716, 718, 719, 724, 725, 727, 728] 82枚のパターン発見。 今日は、プログラム流しっぱなしで帰ります。 |
|
ないしょ
10月2日（木） 17:42:28
MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋 42481 |
|
物理好き |
|
0,1,3,4,9・・・をしばらくかきだしてみると
数列に3のn乗が出たら そこまでの数列の項数は2のn乗+1 729=3の6乗 729までは65項 728までは64項。 |
|
大阪府
10月2日（木） 18:02:50
42482 |
|
巷の夢 |
| 全く分からず、本夕再度問題を開くと、マサルさんが３進法と書いて下さっていらっしゃるでは・・・・、それで分かり、64には辿り着いたのですが・・・・。 |
|
真白き富士の嶺
10月2日（木） 21:50:55
42483 |
|
物理好き |
|
0から順番に728まで調べていって
更に入ることが可能な数を飛ばしてはいけないようにすると #42482の解法で最大がもとめられるはずです。 |
|
大阪府
10月2日（木） 22:53:31
42484 |
|
おーちゃん |
|
#42480の結果（27枚から11枚パターンを作る）によって、729枚からはたとえば以下のようにして88枚パターンを作れます。
[0, 2, 6, 8, 18, 20, 24, 26] * 27 + [0, 1, 5, 6, 8, 14, 18, 19, 21, 25, 26] 81枚からは22枚パターン、たとえば [0, 2] * 27 + [0, 1, 5, 6, 8, 14, 18, 19, 21, 25, 26] を作れることがわかりますが、さらに23枚（以上）のパターンが存在するかが気になります。（見つかれば729枚に対して92枚（以上）のパターンも作れる） というわけで81枚に対する探索プログラムを走らせてみていますが、22枚パターンをポツポツ見つけるばかりで、23枚パターンはまだ見つかっていません。これまでのことを考えるとたぶんあるんでしょうけど。 （追記） 予想に反して、どうも81枚に対する23枚パターンはないようです。 0〜80 を （区間A 0〜26）（区間B 27〜53）（区間C 54〜80）の3区間に分けて（各区間からは最大11枚まで）、区間AまたはC のいずれかに 11枚あるパターン、10枚あるパターン、……、6枚あるパターン、と順に探してみましたが見つかりませんでした。 となると次は243枚から44枚を超えるパターンを作れるか……なのですが、さすがにプログラムでも厳しい気がします。 |
|
10月3日（金） 3:01:45
42485 |
|
Halt0 |
|
小さい値についてプログラムで総当りしたのを基にして検索してみたところ,
数列大辞典のA003002が今回の問題そのものですね. → https://oeis.org/A003002 "Size of the largest subset of the numbers [1...n] which does not contain a 3-term arithmetic progression." コメントに"More terms of this sequence can be found directly from A065825"とあります. A065825というのはこちら. → https://oeis.org/A065825 "Smallest k such that n numbers may be picked in {1,...,k} with no three terms in arithmetic progression." 要するに, 今回の問題の場合, この A065825 の数列を a(n) とおくとき, a(n)＞729 になるような最小の n を求めればいい (答えは n-1 になる) わけですが…現在のところ, 知られているのはどうも a(41)=194 までみたいですね. http://www.math.uni.wroc.pl/~jwr/non-ave.htm によると, この値を求めるのに 2.8 GHz CPU で 11.5 日間かかったそうです. ご参考までに. |
|
10月4日（土） 4:18:03
42486 |
|
おーちゃん |
|
Halt0さん#42486の教えてくださったサイトによると a(45)≦227 とのことなので、227枚(<243)から45枚パターンは作れるんですね。
これを使えば 681枚 (<729) から90枚パターンを作ることもできます。 ＃この 90 が今わかる限界でしょうか…… |
|
10月4日（土） 5:32:26
42487 |
|
さいと散 |
| #42487 おーちゃんさん a(45)≦227 なら680枚じゃないでしょうか？ |
|
10月4日（土） 12:29:21
42488 |
|
uchinyan |
|
#42480，#42481，#42485，#42486，#42487
理論的なアプローチは難しそうだったのでプログラムチェックの様子を見ていたのですが， #42486の様子では本当の難問のようですね。 #42485の考え方にしたがって，自分の理解のために少しまとめておくと，次のようになるのでしょうか。 0 〜 3^n - 1 の最大枚数を c(n) とすれば，0 〜 3^(n+1) - 1 の c(n+1) は， 0 〜 3^(n+1) - 1 を， 0 〜 3^n - 1，3^n 〜 2 * 3^n - 1，2 * 3^n 〜 3^(n+1) - 1，の三つの区間に分けて， 0 〜 3^n - 1 には，0 〜 3^n - 1 の解の一つをそのまま 2 * 3^n 〜 3^(n+1) - 1 には，0 〜 3^n - 1 の解の一つの各々の数に 2 * 3^n を足したもの 3^n 〜 2 * 3^n - 1 には，0 〜 3^n - 1 と 2 * 3^n 〜 3^(n+1) - 1 の数の平均にならないもの を入れるようにすれば，題意を満たすものが作れて，このとき， 0 〜 3^n - 1 は c(n)，2 * 3^n 〜 3^(n+1) - 1 は c(n)，3^n 〜 2 * 3^n - 1 は d(n) とすれば， c(n+1) >= 2 * c(n) + d(n) になります。 問題は，不等号と d(n) ですが，プログラムによる実験では， c(n+1) = 2 * c(n) + d(n)，d(n) = 0 又は 1 程度 となりそうですね。 もし， 0 〜 3^n - 1 には，0 〜 3^n - 1 の解の一つをそのまま 2 * 3^n 〜 3^(n+1) - 1 には，0 〜 3^n - 1 に入れたのと同じもの を入れるとすれば，3^n 〜 2 * 3^n - 1 には入れられず d(n) = 0 になります 常にこうすることにして不等号を等号にすれば， c(n+1) = 2 * c(n)，c(n) = 2^n これはマサルさんの期待していた予想解で今回の出題のベースになったもので，3 進法解釈が容易です。 しかし，実際には，最大よりもむしろ，下界，だったようです。 もし，2 * 3^n 〜 3^(n+1) - 1 を調整して常に d(n) = 1 とでき不等号が等号になるならば， c(n+1) = 2 * c(n) + 1，c(n) = 3 * 2^(n-1) - 1 これは，n = 1, 2, 3 では正しく，#42485のおーちゃんさんの最初の予想ですが， それ以降はこれより小さくなるようです。これは，d(n) = 0 が増える，多くが 0，を意味します。 つまり，理論上ではなく，あくまでの今までのプログラムでの実験の予想ですが， この値は，上界，の一つのようです。 ちなみに，この場合の 0 〜 728 に対するのは c(6) = 95 です。 さらに， n = 1, 2, 3，c(n+1) = 2 * c(n) + 1，n >= 4，c(n+1) = 2 * c(n) と仮定すると， n = 1, 2, 3，c(n) = 3 * 2^(n-1) - 1，n >= 4，c(n+1) = 11 * 2^(n-3) となり，0 〜 728 に対するのは c(6) = 88 となり，#42485の最初の枚数と一致します。 しかしながら，#42487によると 90 が可能だろう，ということなので， どこかでポツポツと d(n) = 1 になるものと思われます。 それとも全く異なるパターンなのでしょうか？ |
|
ネコの住む家
10月4日（土） 14:45:30
42489 |
|
おーちゃん |
|
さいと散さん#42488のおっしゃるとおりです。
3進数・区間3分割で考えるのを引きずっていて、中間のギャップ部分を 1 詰めることができるのを見落としていました。 uchinyanさん#42489 「おまけ」の付き具合をまとめると d(1)=d(2)=1, d(3)=0, d(4)≧1, d(5)=? ということですね。 680枚で90枚なら、さらに49枚のスペース増でもう1枚といきたいところですが…… |
|
10月4日（土） 18:54:00
42490 |
|
Halt0 |
|
http://www.math.uni.wroc.pl/~jwr/non-ave/ を更に見てみたところ,
http://www.math.uni.wroc.pl/~jwr/non-ave/DATABASE.TXT a(93)<=676 1 2 8 11 13 16 22 23 27 29 49 51 54 55 65 67 68 74 77 78 84 98 130 136 144 149 156 159 161 164 170 171 175 177 197 199 202 203 213 215 216 222 225 226 232 246 278 284 440 445 452 455 457 460 466 467 471 473 493 495 498 499 509 511 512 518 521 522 528 542 574 580 588 593 600 603 605 608 614 615 619 621 641 643 646 647 657 659 660 666 669 670 676 (1095251260 Gavin Theobald) とのことで 93 枚は可能な模様. http://www.math.uni.wroc.pl/~jwr/non-ave/BEST.TXT を見ると, どうも a(96)<=709 が Theorem 24 によってわかっているっぽいですが (たぶん), 具体的にどのように書き表せるのかはよくわかりません. Theorem 24 というのは http://www.math.uni.wroc.pl/~jwr/non-ave/methods.htm の Theorem N のことみたいですが, この定理がどのように導かれるのかも, この定理をどうやって適用したのかも, 私にはよくわかりませんでした. #追記 ひねりも何もないやり方ですが上の Gavin Theobald 氏の結果に 690 722 728 を付け加えれば 96 枚にできるので, とりあえず a(96)<=728 ですね. a(97) に関しては未だ a(97)<=736 までしかわかってないっぽいので (というか更に736を付け加えればそれで成立する模様) 現時点で本問の限界は96枚と思われます. |
|
10月4日（土） 20:23:00
42491 |
|
おーちゃん |
|
Halt0さん#42491
a(96)≦709 というのは、Theorem N において N=24,q=4,r=24 として得られるみたいです。 N=24 に対しては modular solution の m(24)≦148 から P=148 と {k_1 …… k_24} = {0 6 14 19 26 29 31 34 40 41 45 47 67 69 72 73 83 85 86 92 95 96 102 116} + 1 を得ます。 a(4)=5, k_24=117 です。 これらを Theorem N の式に代入して a(24*(4-1)+24) ≦ 148*(5-1)+117 a(96)≦709 が得られます。 ちょっと面倒なのは、Theorem N に使う modular solution {k_r} は http://www.math.uni.wroc.pl/~jwr/non-ave/DATABASE.TXT にあるものをそのまま使うのではなく、(1) すべて 1以上になるように、(2) 使いたい k_r が最小になるように、mod P で適当にローテーションするということです。（上の場合は 1 を加えるだけで簡単でしたが） ※ modular solution というのは、本問のような両端をもった空間のかわりに、両端がつながって周期化した空間において等差部分数列を含まない数列を考えたものです。 たとえば上の {k_r} は 0〜147 の周期的空間上で、等差部分数列を含まない数列です。 （追記） Theorem N の考え方は、modular solution を適当なギャップ区間をはさみながらつないでいく、という実はかなりシンプルなものです。 たとえば上の a(96) の場合は、 [M24(148)][M24(148)][ギャップ(148)][M24(148)][M24の先頭部分(117)] ※ M24 は modular solution, ()内は区間長さ によって a(96) に対応する数列を作っています。 modular solution を使うことで、となりあう区間で干渉しあって等差数列が出現するのを防いでいます。 また全体の構造は a(4) に対応する {0,1,3,4} で決まっており、3つの区間をまたがる等差数列が出現しないようにしています。 |
|
10月4日（土） 23:27:53
42492 |
|
Halt0 |
|
#42492
おお, そういうことでしたか. ありがとうございます. どうも modular solution の定義を勘違いしていたっぽいです. つまり, {0 6 14 19 26 29 31 34 40 41 45 47 67 69 72 73 83 85 86 92 95 96 102 116} + 1 + 148*({1 2 4 5} - 1) ={1 7 15 20 27 30 32 35 41 42 46 48 68 70 73 74 84 86 87 93 96 97 103 117 149 155 163 168 175 178 180 183 189 190 194 196 216 218 221 222 232 234 235 241 244 245 251 265 445 451 459 464 471 474 476 479 485 486 490 492 512 514 517 518 528 530 531 537 540 541 547 561 593 599 607 612 619 622 624 627 633 634 638 640 660 662 665 666 676 678 679 685 688 689 695 709} を構成して a(96) の上界を得ているのですね. なるほど. (一瞬 modular solution から x,y をとってきたとき (x+y)/2 + 74 が modular solution に含まれているとまずいけどその可能性はないのか…？ などと悩んでしまいましたが, x, (x+y)/2+74, y が mod 148 で等差数列になるから定義からアウトでしたね. 平均という言葉に引きづられていた…) トップページに"Note that if m(n) is even, then terms i and i+m(n)/2 exclude each other. "と書かれていることにも合点がいきました. |
|
10月6日（月） 4:05:37
42493 |
|
uchinyan |
|
#42491，#42492，#42493
情報提供と解説をありがとうございます。 ふーむ，半分分かったようで実は分かってないだろうな，とは思うものの，話の流れは，なるほど，という感じです。 結局のところ，96 はできる，97 は現在は可能かは分からない，が多分無理？，ということでしょうか。 私の#42489で，すべての d(n) が 1 の 95 が上界，かなと予想を立てましたが見事にはずれました。 n が大きくなれば隙間が多くなるので d(n) が大きくなっても不思議はないわけですし， そもそも単純な３分割から得た式はもともと不等式で，もし等式だったら，という仮定の下での評価なので， はずれても当たり前ですね。 実際，a(96) の構成は，似たような考え方のようですが，より一般化されたもののようですね。 いろいろと勉強になります。 変な話ですが．．． 今回の問題は出題者の意図をはるかに超えてしまった点では失敗作と言わざるを得ないでしょうが， 様々な新たな知見を得られた点では大きな収穫がありました。 このサイトの問題は，他のサイトと違って，ただ解いて終わり，ではなく深みのある問題も多いので， いろいろと考察ができて楽しいです。１週間という時間もちょうどいいように思います。 マサルさん，これからも楽しみにしていますね。 |
|
ネコの住む家
10月5日（日） 12:14:22
MAIL:uchi@sco.bekkoame.ne.jp 42495 |
|
マサル |
|
今回はご迷惑をおかけし、申し訳ありません。しかも「本当の正解探し」はみなさんに任せっきりで...すみません。
何人かの方は、正解探しの過程を楽しんでくださったようですが、やはり本来はあってはならないことです。（これが入試だったら大変なことです...） 厚顔はなはだしいですが、皆さんの書き込みもちょっと楽しく読んでいたりします。（すみません..）今後とも、よろしくお願いいたします。今回は申し訳ございませんでした。m(__)m |
|
MacbookPro
10月5日（日） 20:03:24
HomePage:算チャレ 42496 |
|
物理好き |
|
96か97か、本当はどちらなのでしょうか？
これは小学生では理解できないでしょうね。 |
|
大阪府
10月5日（日） 20:26:04
42497 |