ニート歴10年からの数学日記

2008年〜2009年の高一の冬休みから無職。最長で4ヶ月ほどの中断アリ。

算数オリンピックの問題 その12

メチャメチャだけど【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、算数オリンピックについて考察していく。
グラフや幾何学の問題や、記述に関するメタ的な問題以外の今までに無い種類の問題について考察する。
 

 

06年度ファイナル問題 問題4

『次のABCDEは5けたの整数、FGHIは4けたの整数、各位の数字A〜Iは1〜9のすべて異なる整数を表しています。
   ABCDE × FGHI > 80000000
このような条件を満たすABCDEとFGHIの最小の和を求めなさい。』


[A, B, C, D, E, F, G, H, I] := それぞれカブり無しで全部に := [1, 2, 3, 4, 5, 6, 7, 8, 9];

(10000*A + 1000*B + 100*C + 10*D + E) * (1000*F + 100*G + 10*H + I) > 80000000;

((10000*A + 1000*B + 100*C + 10*D + E) + (1000*F + 100*G + 10*H + I) )が最小になるように設定;

結果における((10000*A + 1000*B + 100*C + 10*D + E) + (1000*F + 100*G + 10*H + I) );


98000*7000と97000*8000では後者の方が大きくなる。97000*8600と96000*8700でも、まだ後者の方が大きくなる。96000*8750と95000*8760で、ようやく前者の方が大きくなる。
次は96400*8740で、左に100足すか、右に10足すか。96400*10=964000、8740*100=874000で、右に10足した方が良いと分かる。96300*8753で、左に100足すか、右に1足すかだと、87万と9万で、左に100足した方が良い。96420*8752の左に10か右に1かだと、右に1。96421*8753が、とりあえず最大だと分かる(と思う)。
同じ数字の中で位置が逆転することは無いとして、どちらの先頭を大きくしたら良いかというと、右の1000 > 右の100 > 左の1000 > 右の10 > 左の100 > 右の1 > 左の10 > 左の1。
96421*8753=843973013。でもこれは、求められている答えの10倍は多い。逆に14689*2357は34621973。なんか推論として正しいのかな。いや、右の1と左の10と左の1を3通り入れ替えてみて、順番に増えていかないので、何かおかしいかもしれない。

求められている答えは8*10^7以下だが、すでに10^7はあるので、一番上の位同士の掛け算は答えが7以下なはず。1*8ではいけないし、2*4でもいけないし、3*3でもいけない。この時点で、1*(1~7)、2*(1~3)の10通りには絞られる。

えー分からないので答えを見ると、まずABCDE+FGHIを最小にすることを考えるとAは1で、その上でAB*Fの積と和の組み合わせを考えると、
12*6=72、12+6=18。12*7=84、12+7=19。13*6=78、13+6=19。13*7=91、13+7=20。
以上から、ABが12、Fが6のとき、ABCDE*FGHI > 80000000で、ABCDE+FGHI < 19000であれば、このときのABCDE+FGHIが最小になると分かる。
12CDE+6GHIが最小になるのは、残りの整数を上の位から順に入れた場合、つまりCとGに3と4、DとHに5と7、EとIに8と9を入れた場合なので、このとき、(12+6)*1000 + (3+4)*100 + (5+7)*10 + (8+9) = 18837になる。
2数の和が一定の時、2数の差が小さいほど積は大きくなるので、12358*6493>80000000となれば、条件を満たす最小の和は18837になるので、調べてみると12358*6493=80067482>80000000となり、答えは18837と分かる。

単純に不甲斐ない。が小学生が解く問題だと考えると知能の問題では無く(解いている奴のIQが130でも、大人の100であればそれを基準に128だ、逆に言えばその小学生は78だ)、だから慣れの問題だと思うが。
解答は足し算の制約から答えに至っている。掛け算の制約について考えても答えになんて至らない。次回からは、複数の制約がある時は、どの制約から考えるかをしっかり検討しよう。

……IQというのは、普遍的な頭の良さ、つまり様々な目的に対して達する傾向にあるかを計る試験ということだが、肝心の各ジャンルの一流のIQがそこまで高くない。練習したら上げることができるというのもおかしいし、その上げた後にそいつの頭が良くなるというわけでも無い、もしそうなら皆でIQテストの練習をすれば良い。この2点がIQの「普遍的な頭の良さがある」という仮説として、致命的だと思う。
俺のIQは元々せいぜい104だったと記憶している。102か103ぐらいだったはず。テストを受けるたびに上がっていったが、俺はIQテストの練習なんて恥ずかしいことはしていない。
IQテストはこれからも、治療に必要だからという理由と、しかしIQテストなんて本質的じゃないに決まってるじゃないかという上っ面だけの自覚と共に、人を知的に抑圧し続けるだろう。
普遍的な機能が頭の中に入っているわけでは無い。IQが上がるほど脳神経が減って、それ以外の細胞の総称であるグリア細胞が増えていくという研究もある(そしてグリア細胞は増やすことができる、つまり大体は脳神経が少ないということだ)。
togetter.com
この画像では、まるでIQが高い人間は脳が大きいみたいだが、そういう事実も無い。人間の頭の良さへの偏見が表れている。頭の良さとは実際には最適化だろう。
人間の遠慮だとか、社会的生物としての嫌ったらしい抑圧だとか、そういうものがIQという概念の中にはあると考える。
 

06年度ファイナル問題 問題6

『次のABC、DEF、GHIはそれぞれ3けたの整数、各位の数字A〜Iはすべて異なる数字を表しています。
   ABC + DEF + GHI = 2006
次の問いに答えなさい。

(問い1)0〜9の10個の数字の中で、A〜Iの9個のどれにも入らない数字が出てきます。この数字が1通りであればその数字を、2通り以上であれば小さい順にすべて書き出しなさい。
(問い2)このとき、A〜Iの数字の入り方は全部で何通りありますか。ただし、たとえば次の例のように3個の3けたの整数の組み合わせが同じになる場合は合わせて1通りと数えます。

(例)123 + 456 + 789 = ・ 456 + 789 + 123 = ・ 789 + 456 + 123= 』


0 <= A, B, C, D, E, F, G, H, I <= 9;
A != B != C != D != E != F != G != H != I;
(100*A + 10*B + C) + (100*D + 10*E + F) + (100*G + 10*H + I) == 2006;

結果における([0~9].[?1: ?1∉(A~I)]);

結果における[A~I].数; ??昔数学の授業で習った、組み合わせのPとかCとかを表す機能か、その機能を果たすコードを考える必要がある


100*(A+D+G)+10*(B+E+H)+(C+F+I)。3つの数字を合わせると最大は9+8+7=24、最小は3。
つまり、A+D+Gは、少なくとも18以上である必要がある。また、C+F+Iは、6か16かのどちらか。
A+D+Gは20以下18以上なので、20だと9+8+3、9+7+4、9+6+5、8+7+5の4通り。19だと9+8+2、9+7+3、9+6+4、8+7+4、8+6+5の5通り。18だと9+8+1、9+7+2、9+6+4、8+7+3、8+6+4、7+6+5の6通り。
C+F+Iは6だと、0+1+5、0+2+4、1+2+3の3通り。16だと、9+7+0、9+6+1、9+5+2、9+4+3、8+7+1、8+6+2、8+5+3、7+6+3、7+5+4の9通り。

これだけでは答えが出そうにないので、A+D+Gの3通りと、C+F+Iの2通りで、6通りの場合について、B+E+Hを考えてみる。
20と16だと、不可能(気付かなかった、寝不足のせいかもしれない)。20と6だと、0なので不可能。19と16だと、9。19と6だと、10。18と16だと、19。18と6だと、20。
9は、0+1+8、0+2+7、0+3+6、0+4+5、1+2+6、1+3+5、2+3+4の7通り。10は、0+1+9、0+2+8、0+3+7、0+4+6、1+2+7、1+3+6、1+4+5、2+3+5の8通り。19は、9+8+2、9+7+3、9+6+4、8+7+4、8+6+5の5通り(流用)。20は、9+8+3、9+7+4、9+6+5、8+7+5の4通り(同じく流用)。
これで、一つでも成立すれば、それが答えだろう。馬鹿みたいな方法だと思うが。

19と16と9の場合から。
9+8+2、9+7+3、9+6+4、8+7+4、8+6+5。
9+7+0、9+6+1、9+5+2、9+4+3、8+7+1、8+6+2、8+5+3、7+6+3、7+5+4。
0+1+8、0+2+7、0+3+6、0+4+5、1+2+6、1+3+5、2+3+4。
選択肢が少ない19から見ていくと、9+8+2は、7+6+3・7+5+4、0+3+6・0+4+5・1+3+5。7+6+3と0+4+5の組がマッチ。7+5+4と0+3+6の組もマッチ。
9+7+3は、8+6+2、0+1+8・0+4+5・1+2+6。8+6+2と0+4+5の組がマッチ。
9+6+4は、8+7+1・8+5+3、(で共通する8も除外するとして)0+2+7・1+3+5。8+5+4と0+2+7の組がマッチ。
8+7+4は、9+6+1・9+5+2、(で共通する9も除外するとして)0+3+6・1+2+6・1+3+5。9+5+2と0+3+6の組がマッチ。
8+6+5は、9+7+0・9+4+3、(9も除外するとして)0+2+7・0+3+6・2+3+4。9+7+0と2+3+4の組がマッチ。9+4+3と0+2+7の組がマッチ。
発狂しそうだ。気付いたけど、0~9の和が45で、19+16+9の和が44だから、使われない数字は1だな。

19と6と10の場合について。19+6+10=35。数字は9までで、10使わないということはできないので、これは無理。

18と16と19の場合について。18+16+19=53。45を過ぎているので無理。

18と6と20の場合について。18+6+20=44。使わない数字は1。この時点で、問い1の答えは1だと分かった。
9+8+1、9+7+2、9+6+4、8+7+3、8+6+4、7+6+5。
0+1+5、0+2+4、1+2+3。
9+8+3、9+7+4、9+6+5、8+7+5。
選択肢が少ない6から見ていくと、0+1+5は、9+7+2・9+6+4・8+7+3・8+6+4、9+8+3・9+7+4。どの組もマッチしない。
0+2+4は、9+8+1・8+7+3・7+6+5、9+8+3・9+6+5・8+7+5。8+7+3と9+6+5の組がマッチ。7+6+5と9+8+3の組がマッチ。
1+2+3は、9+6+4・8+6+4・7+6+5、(6を除外するとして)9+7+4・8+7+5。9+6+4と8+7+5の組がマッチ。

11組がマッチして、100の位の入れ方が6通り、10の位が6通り、1の位が6通り。更に同じ3つの3けたの数字の組み合わせで位置が違う場合が6通り。6*6*6*11/6=396が答えだろう。

答えを見ると、11組で無く10組で、単に数え間違え。おそらく、「どの組もマッチしない」に反応してしまったんだろう。
答えは360通り。解法がこのままなのはキチガイじみているというか、神経が磨り減りそうな問題だと思った。
 

07年度トライアル問題 問題10

『A君とB君が20問からなるクイズに挑戦しました。このクイズは正解するとある2けたの点数がもらえ、不正解だと別の2けたの点数が引かれます。
結果は、A君が328点、B君は27点でした。

問い1.このクイズで正解でもらえる2けたの点と不正解で引かれる2けたの点の和はいくつですか。(たとえば正解で52点がもらえ、不正解で37点が引かれる場合、答えは52+37=89点とします。)
問い2.このクイズは正解だと何点もらえ、不正解だと何点引かれますか。』


10 <= X, Y <= 99;

A := カブり有りで20 := [X, -Y];
B := カブり有りで20 := [X, -Y];

A.+ == 328;
B.+ == 27;

結果における(X+Y);
結果における(X, Y);


X*a - Y*(20-a) == 328。X*b - Y*(20-b) == 27。うーんなんとも。

Xが10点だとして、20問正解したら200点だから、328点に届かないという理由でこれは無い。17点以上。20問は20で割り切れないから無いとして、18点以上。19*18-? == 328になるようなものを考えるか?

念の為に。X*a - Y*(20-a) - {X*b - Y*(20-b)} = = 328 - 27、X*a - Y*(20-a) - X*b + Y*(20-b) == 301、X(a-b)+ Y(-20+a) + Y(20-b) = 301、X(a-b)+Y(a-b) = 301、(X+Y)(a-b)=301。これは行けそうだな。
301=7*43。aは20以下なんで、(a-b)が7で、(X+Y)が43だろう。この時点で、問い1は43。

aもbも20以下だから、20-13から、7-0までで、13通り。XとYはどちらも2ケタなので、10+33から、33+10までで、23通り。
いやそうでは無く、a=b+7、と考えれば良いんだな。X=43-Y。
最初の式に代入して、(43-Y)*(b+7)-Y*(20-b-7)==328、43*b +301 -b*Y -7*b -20*Y +b*Y +7*Y == 328、36*b + 301 -13*Y == 328、36*b - 13*Y == 27。
(43-Y)*b - Y*(20-b) == 27、43*b - Y*b - Y*20 + Y*b == 27、43*b - 20*Y == 27。
試しに、36*b - 13*Y == 43*b - 20*Y、7*Y == 7*b、Y == b。どちらかの式に代入して、36*b - 13*b == 27、23*b == 27、b == 27/23。あー、どこかで計算間違いしたんだろうな。


答えを見ると、つまり正解と不正解で、(X+Y)点分かれる。なぜならX点貰えて、Y点引かれるから。328-27=301で、301点の約数が(X+Y)。
一方、XもYもふた桁の整数なので、20<=(X+Y)<=198。よって(X+Y)は43点に定まる。

(328-27)/43=7から、A君はB君より7問多く正解している。つまりA君は少なくとも7問正解していて、不正解は13問以下。
もしA君が不正解分も正解していたら、満点は328+43*?点。満点は20の倍数なので、?=4。このとき、満点は500点、正解でもらえるのは25点、不正解で引かれるのは18点。


どこで計算間違いしたのかは分からないが、まあいいか。確かにA君とB君の共通点ということを考えると、正解した時の不正解した時の分かれ目というか、一回辺りにどれくらいの差が生まれるかを考えるというのは、自然なことと言えなくもないのかもしれない。分からない。
 

07年度トライアル問題 問題11

『さくら、もも、ゆり、あい、らんの5人の女子を正しい背の順(背の高い順)に左から一列にならべたいと思います。となりあう2人が正しい背の順にならんでいなかったら位置を入れかえることをくりかえしてならべかえます。となり合う2人をいれかえることを「1手」とよぶことにします。
左から順に さくら、あい、らん、ゆり、ももとならんだ場合
   この場合、正しいならべかたにするのに最短で8手必要でした。
左から順に もも、さくら、あい、らん、ゆりとならんだ場合
   この場合、正しいならべかたにするのに最短で8手必要でした。
左から順に ゆり、あい、もも、らん、さくらとならんだ場合
   この場合、正しいならべかたにするのに最短で3手必要でした。
5人の正しい背の順に左からならべなさい。』


sort_list(women_list, change_count){
 for(i := 0; i < (women_list.数 - 1); i++){
  if(women_list[i] > women_list[i+1]){
   women_list[i+1] := women_list[i];
   women_list[i] := women_list[i+1];

   i := 0;
   change_count := change_count + 1;
  }
 }
 return women_list, change_count; ??これで良かったっけ
}


women_list1 := [sakura, ai, ran, yuri, momo];
change_count1 := 0;

women_list1, change_count1 := sort_list(women_list1, change_count1);

change_count1 == 8;


women_list2 := [momo, sakura, ai, ran, yuri];
change_count2 := 0;

women_list2, change_count2 := sort_list(women_list2, change_count2);

change_count2 == 8;


women_list3 := [yuri, ai, momo, ran, sakura];
change_count3 := 0;

women_list3, change_count3 := sort_list(women_list3, change_count3);

change_count3 == 3;


結果におけるwomen_list3;


これは俺の推測だけど、1つ目の条件と2つ目の条件で、ももが逆なのに値が変わらないので、おそらくももは真ん中。3つ目の条件で、ももが真ん中で、交換が3回なので、おそらくあいとらんが交換されたのではないか。
つまり、ゆり・らん・もも・あい・さくら、の順番が答えなのではないか。実際、そこから8回で、1つ目と2つ目になる。

答えを見ると、まず、並びを逆順にするのに10手かかることに注意する。そしてもし並びを直すのに8手かかるなら、逆順にすると2手になる。
1つ目と2つ目を逆順にすると、ももが逆方向にあるのに2手で直さなければいけないので、ももは真ん中で、そのまま答えも出る。