ジュニア算数オリンピックその後の新しい種類の問題 その11
グラフや幾何学の問題や、記述に関するメタ的な問題以外の今までに無い種類の問題について考察する。
【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使う、必要になり次第付け加えていく。
サンプルを増やすことに注力したい。
12年度トライアル問題 問題3
『昭和は1年〜64年まであり、昭和元年(1年)は西暦1926年です。西暦が昭和の年数の倍数となっている年数は全部で何通りありますか。』
1 <= 整数S <= 64。
1925 + S = ?S。(?の使い方が怪しい。?はeveryなのかanyなのか。anyならこれでも良さそうだが。nSにすべきかな)
結果におけるS一覧の数。
多分、下から調べていって、2で無ければ2の倍数は全部削って、3で無ければ3の倍数は全部削って、というやり方をするんじゃないか。
答えを見ると、昭和の年数が1925の約数になる時を調べれば良い、ということらしい。で答えは1、5、7、11、25、35、55の7通り。
足し算だと1ステップずつ確かめないといけないが、掛け算だけにすることで一気にやれるようにした?
12年度トライアル問題 問題5
『あきら君とまなぶ君がカードの順番あてゲームをしています。
あきら君が1、2、3、4、5の数が書かれたカードを、順番を決めて一列に裏を向けてならべます。まなぶ君がその順番を当てるというゲームです。
以下の文章を読んでA、B、C、D、Eそれぞれのカードの数字を求めなさい。
あきら君:「一列にならべたよ。君に順番が分かるかな?」
まなぶ君:「じゃあ、1つ目の質問をするね。1の数字より左に1より大きい数はあるかい?」
あきら君:「2個あるよ。」
まなぶ君:「なるほどね。じゃあ、2より右側には2より大きい数はある?」
あきら君:「1個あるね。あと1回の質問で終わりね。」
まなぶ君:「え〜、わからないな。じゃあ、3より右側にあるカードに書かれている数の和はいくつ?」
あきら君:「7だよ。」
まなぶ君:「待ってね…。わかった!そのならびは左からA、B、C、D、Eだね。」
あきら君:「正解だよ。よくわかったね。」』
リスト[ , , , , ]のカブり無しの中に[1, 2, 3, 4, 5]のカブり無しから全部。
?? [リスト]の並びの制約で[1 > ?]において、[1 < n]の数 = 2。
?? [リスト]の並びの制約で[2 < ?]において、[2 < n]の数 = 1。
?? [リスト]の並びの制約で[3 < ?]において、[全て]の総和 = 7。
結果における[リスト]。
表記については後から整備する。目的は、問題の本質は計算量を少なくすることだと示すことで、繰り返すようだが表記はどうでも良いんだが。ただしかし、表記を見て、問題文に戻らなくても考えることができるぐらいには、シンプルなものに直した方が良いのかもしれない。
多分、(1番目と2番目は弱いので)3番目の制約で、3の右は、2と5か、1と2と4。前者の場合は1と4が左にあって、後者の場合は5が左にある。
1の左には1以上が2つ無いと駄目なので、前者は無い。後者の場合は、5 3 1の順番は確定。更に2の右には2以上が1つあるので、5 3 1 2 4。これは条件を満たす。
並びの制約が本当に見にくい。左右だけなら単に[? < 1]と書くだけでも良いのだけど。
12年度トライアル問題 問題7
『3×3のオセロの盤のすべてのマスにオセロの駒を置いた後に、図のようにオセロのルールでひっくり返る駒がどこにもないような置き方は、図の場合もふくめて全部で何通りありますか。
ただし、回転したり裏返して重なるものも、それぞれ1通りとしてかぞえるものとします。
(図)白白黒
白黒黒
黒黒黒』
リスト[[ , , ], [ , , ], [ , , ]]のカブり無しの中に[白, 黒]のカブり有りから全部に挿入。(表記はこれで良いかな、それぞれに一つだけ挿入になりそうだけど)
リスト[0] and リスト[1] and リスト[2] != [白, 黒, 白] or [黒, 白, 黒]。
リスト[?][0] and リスト[?][1] and リスト[?][2] != [白, 黒, 白] or [黒, 白, 黒]。
[リスト[0][0], リスト[1][1], リスト[2][2]] and [リスト[0][2], リスト[1][1], リスト[2][0]] != [白, 黒, 白] or [黒, 白, 黒]。
結果における[リスト]一覧。
おそらく、問題を細かく分けるという原則で、一番端っこの白は確定として、[白, 白, 白]か[白, 白, 黒]か[白, 黒, 黒]。
縦と横があって、それぞれ不干渉なので(後から気付いたけど白白白同士が干渉しとる、まあド真ん中に白置くしか無いというだけだけど)、とりあえずは3×3=9。その後は、それぞれ残りの4マスで2^4=16通りを堅実に考えるかな。元々の9通りでも、[白, 白, 白]と[白, 白, 黒]、[白, 白, 黒]と[白, 白, 白]、みたいなのは同じだろうから、そういうのを削って残り6通り。6通りと16通りで計算量的には96通りぐらいか?
答えを見ると、オセロ盤の左から右、あるいは右から左に考えると、黒は必ず個数が等しいか少なくなる。
また3つの列で下から連続して黒がならぶか、上から並ぶかのいずれかになる。
この2つの法則で、黒の個数に注目して考えることができる。
左の列から黒の個数が333と000の場合はそれぞれ1通り。
111と222の場合、黒が上から並ぶか下から並ぶかでそれぞれ2通り。
330と300の場合は、左右を変える場合のみなので、2通りずつ。
その他の並び方については、上下どちらか、左右どちらかで4通りずつある。
しかし311と220に関しては真ん中がひっくり返ってしまうので条件を満たさない。
よって、1*2 + 2*4 + 4*12 = 58通り、らしい。
上2つのルールで個数以外では上下左右さえ考えれば良くなった。それから、上下左右を考えなくて良いパターン、上下や左右さえ考えれば良いパターン、上下左右を考えるパターン。
全体の上下左右という感じだから、全体が絡んでいると言えなくもないのか?横方向にしか考えなくて良くした、とも言えるかもしれない。
12年度ファイナル問題 問題3
『横にならんだ9つのマス目があり、各マスに1枚ずつコインが置かれています。はじめ、左から1、3、4、6、7、9マス目のコインは表、2、5、8マス目のコインは裏です。(図では表を○、裏を×で表しています。)
(図)○×○○×○○×○
以下の操作を考えます。
「表になっているコインを1枚選び、そのコインおよびそのコインより左側にあるコインをすべてひっくり返す。すべてのコインが裏になったら終了である。」
これについて次の問いに答えなさい。
(1)最小何回の操作で終了しますか。
(2)最大何回の操作で終了しますか。』
よく分からない種類の問題。リストの整列の問題な気もするが、そうじゃない気もする。
1の答えは、隣り合うコインを同じにして、最後には全部を裏にする操作で7回。実際の答えでは、「最も右の表のコインを選ぶ」という操作で7回、と解説されていたが。
2の答えは、「i枚目のコインが表のとき、2^i-1を足した値を考えます。」、ということらしい。2^0=1、2^2=4、2^3=8、2^5=32、2^6=64、2^8=256。1+4+8+32+64+256=365。実際に、「最も左の表のコインを選ぶ」という操作を行うことで、365回になるらしい。
ベタに考えれば同じ所で何回もひっくり返せば良い気もするけど、そういう話じゃないらしい。
12年度ファイナル問題 問題5
『ひろゆき君とたろう君が数当てゲームをしています。以下の会話を読んで問題に答えなさい。
ひろゆき:「よし、じゃあ、ぼくが1つ数字を決めるから、たろう君当ててみてよ。」
たろう:「まかせてよ。かんたんに当ててみせるよ。」
ひろゆき:「数字を決めたよ。数字は7けたで、1〜7の数字を1回ずつ使っているよ。」
たろう:「他にヒントはないの?」
ひろゆき:「そうだな〜、となり合うけたどうしの数字の差は全部ちがうよ。」
たろう:「う〜ん、まだ分からないよ。」
ひろゆき:「じゃあ、一の位は4以外の偶数だよ。あと上から3けた目は7だよ。」
たろう:「あと一つだけヒントちょうだい。」
ひろゆき:「これが、本当に最後だよ。奇数が3個以上つながっている部分があるよ。」
このとき、ひろゆき君が決めた数字を答えなさい。』
リスト[ , , , , , , ]のカブり無しの中に[1, 2, 3, 4, 5, 6, 7]のカブり無しから全部挿入。
リスト差分[m] = リスト[m] - リスト[m-1]。
?? [リスト差分]の中の全ては≠。
リスト[0] = 2 or 6。
リスト[4] = 7。
リスト[m] = 2? + 1 and リスト[m+1] = 2? + 1 and リスト[m+2] = 2? + 1。 (mがどれか1つという扱いで良いかを細かく考える必要がある)
結果における[リスト]。
答えを見ると、となり合う数字の差は1〜6が一回ずつ出てくることと、6とか5の作り方は限られていることを利用するのが重要みたいだ。
全体の利用、か?ベストを尽くしても差が6までしか作れないことを見切る?よく分からない。