2024-04-14

もとの6けたの整数はいくつ？

※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。

【2000年度ジュニア算数オリンピックトライアル問題7問目】
　6けたの整数があり一の位の数字は9です。今、この「9」を一番上の位に移したら、もとの整数の4倍になりました。もとの6けたの整数はいくつですか。

【記法化】

Aは0から9の整数である;
Bは0から9の整数である;
Cは0から9の整数である;
Dは0から9の整数である;
Eは0から9の整数である;
(100000*A + 10000*B + 1000*C + 100*D + 10*E + 9) * 4 == 900000 + 10000*A + 1000*B + 100*C + 10*D + E;

print(100000*A + 10000*B + 1000*C + 100*D + 10*E + 9)

ちょっと普通の制約プログラミングで解けるか気になったのでCP-SAT ソルバー | OR-Tools | Google for Developersを参考にして試してみた。

from ortools.sat.python import cp_model

model = cp_model.CpModel()

num_vals = 10
A = model.new_int_var(0, num_vals - 1, "A")
B = model.new_int_var(0, num_vals - 1, "B")
C = model.new_int_var(0, num_vals - 1, "C")
D = model.new_int_var(0, num_vals - 1, "D")
E = model.new_int_var(0, num_vals - 1, "E")

model.add((100000*A + 10000*B + 1000*C + 100*D + 10*E + 9) * 4 == 900000 + 10000*A + 1000*B + 100*C + 10*D + E)

solver = cp_model.CpSolver()
status = solver.solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"A = {solver.value(A)}")
    print(f"B = {solver.value(B)}")
    print(f"C = {solver.value(C)}")
    print(f"D = {solver.value(D)}")
    print(f"E = {solver.value(E)}")
else:
    print("No solution found.")

結果

A = 2
B = 3
C = 0
D = 7
E = 6

【工夫】
「ABCDE9 * 4 == 9ABCDE」なので、まず左辺の計算結果の下1ケタは6だと分かり、Eは6だと分かる。Eが分かれば下2ケタ目も求められるし、下2ケタ目が求められれば同じように下3ケタ目も求められる。そういうことが普通の制約プログラミングでできるか分からなかったのだけど、どうもできるらしいので工夫はいらないものと考える。

2024-04-12

三郎のもっている残りの3個の玉に書かれた数字はそれぞれいくつ？

※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。

【2000年度ジュニア算数オリンピックトライアル問題5問目】
　①～⑫の数が書かれた玉が1つずつ、合計12個あります。
　一郎、二郎、三郎の3人が4個ずつとりました。すると、3人のもっている玉に書かれた数の和が3人とも同じになりました。
　つぎの3つのヒントを読んで問いに答えなさい。
　ヒント1：一郎には⑤と⑫があります。
　ヒント2：二郎には⑥と⑧があります。
　ヒント3：三郎には①があります。
　さて、三郎のもっている残りの3個の玉に書かれた数字はそれぞれいくつですか。

【記法化】

ichiro := [];
ziro := [];
saburo := [];

実行;

[ichiro, ziro, saburo].every := 1つ辺り4つ追加 : 被りなしで全部 := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12].every;

実行;

sum(ichiro) == sum(ziro) == sum(saburo);
5 in ichiro;
12 in ichiro;
6 in ziro;
8 in ziro;
1 in saburo;

print(saburo);

「[ichiro, ziro, saburo].every := 1つ辺り4つ追加 : 被りなしで全部 := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12].every;」という表記は正直迷っている。この算数の問題文の記法の本質の1つは、例えば一郎や二郎や三郎が何番を取るかで実行結果が分岐していくことなのだけど、分岐要因の1つである移動がどういう表記であるべきかは定まっていない。

【工夫】

ichiro := [];
ziro := [];
saburo := [];

実行;

[ichiro, ziro, saburo].every := 1つ辺り4つ追加 : 被りなしで全部 := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12].every;

実行;

sum(ichiro) == sum(ziro) == sum(saburo) == sum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]) / 3;
5 in ichiro;
12 in ichiro;
6 in ziro;
8 in ziro;
1 in saburo;

print(saburo);

「sum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]) / 3」なのは当たり前だろとも思うのだけど、内部的にどう振る舞うのかがまだハッキリしてないので、もしかしたら必要かもしれない。そうするとそれぞれにおいて合計26になると分かるので、例えば一郎は「26 - 5 - 12」で残り9。「1、8」「3、6」「4、5」の組は選択肢にないので自動的に「2、7」が残り。二郎も同じように「3、9」。それ以外が三郎と分かる。
しかしこの工夫にしても、色々なことを前提にしてしまっている気がする。例えば一郎の場合に、残りが9であること、更には「1、8」「3、6」「4、5」の組は選択肢にないという判断を内部的に行うと考えて良いものだろうか。良いような気もするし良くないような気もする。

2024-04-09

【未解決】この本は何ページの本か？

※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。

【1999年度ジュニア算数オリンピックトライアル問題13問目】
　ある本をたろう君は1日目35頁、2日目40頁、3日目45頁と5頁ずつ増やして読んでいったら読み終わった日は35頁ですみました。同じ本を花子さんは1日目45頁、2日目50頁、3日目55頁と5頁ずつ増やして読んでいったら読み終わった日は40頁ですみました。この本は何頁の本ですか。

【記法化】

pages_Aは自然数;
pages_Bは自然数;
pages_A == pages_B;

記録1;
実行;

i := 0;

実行;

while(pages_A != 35) {
    pages_A -= (35 + 5*i);
    実行;
    i += 1;
    実行;
}

i := 0;

実行;

while(pages_B != 40) {
    pages_B -= (45 + 5*i);
    実行;
    i += 1;
    実行;
}

記録1 {
    print(pages_A);
}

【工夫】
解答を見ると、余分なページを前に持ってくるみたいだ。
35、35、40、45……。
40、45、50、55……。
で後者において余分な70ページが1日で読まれることが分かる（増加ペース的に2日以上には分けれない）から、答えは40+45+50+55+60+65+70。

2024-04-05

【未解決】20回目にはウサギはどこにいるか？

※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。

【2000年度ジュニア算数オリンピックトライアル問題1問目】
　図のように下の左（ア）にはイヌ、下の右（イ）にはネコ、上の左（ウ）にはサル、上の右（エ）にはウサギがいます。今、1回目は上と下を入れかえ（イヌとサル、ネコとウサギを入れかえる）、2回目は左と右を入れかえ、3回目は、また上と下を入れかえ、次はまた左と右を入れかえ・・・・と、次々と入れかえていきます。
　20回目にはウサギはどこにいますか、（ア）～（エ）の記号で答えなさい。

【記法化】

house := [
    ["Saru", "Usagi"],
    ["Inu", "Neko"]
];
実行;

for(i = 1;i <= 20;i++){
    if(i%2 == 1){
        house[0] := house[1];
        house[1] := house[0];
        実行;
    }

    if(i%2 == 0){
        for(i = 0; i < len(house); i++){
            house[i][0] := house[i][1];
            house[i][1] := house[i][0];
            実行;
        }
    }
}

print(house);

【工夫】

house := [
    ["Saru", "Usagi"],
    ["Inu", "Neko"]
];
shuffle_count := 20;
実行;

shuffle_count := shuffle_count % 4;
実行;

for(i = 1;i <= shuffle_count;i++){
    if(i%2 == 1){
        house[0] := house[1];
        house[1] := house[0];
        実行;
    }

    if(i%2 == 0){
        for(i = 0; i < len(house); i++){
            house[i][0] := house[i][1];
            house[i][1] := house[i][0];
            実行;
        }
    }
}

print(house);

この解決策は微妙だ。4回で最初に戻ることを人間側が分析して、その余り分つまり0回実行した。分類としては画像圧縮の仕組みに近いと思う。
人間側の判断すらどうにか自動化できないだろうかとは思うが、houseが最初の状態に戻るまでをカウントしても、シャッフルの過程が同じ振る舞いでなければこのように省略できない。いやシャッフルの過程が同じ振る舞いでも場合によっては省略できないかもしれない。何にせよケースバイケースで、人間の判断が入り込んでいる。
算数の問題がプログラミングの計算量圧縮のアイデアの源泉になり得るんじゃないかとは思っているが、同じような問題が集まってこなければ何とも言えない。

2024-04-02

【未解決】ダンボール箱の移動

※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。

【1999年度ジュニア算数オリンピックトライアル問題10問目】
　下のように9つの重さのちがうダンボール箱がA、B、Cの３つの家にあります。これをAの家には15kg、Bの家には30kg、Cの家には45kgになるようにトラックを使って移したいと思います。ただしトラックは一度に2こまでのダンボール箱しか運べませんし、たった1まわりしかできません。Aの家からスタートするとして、○の中に移すダンボール箱の重さを書き入れなさい。

【記法化】

house_A := [8, 9, 13];
house_B := [3, 5, 7, 15];
house_C := [12, 18];

実行;


list_A := 被りなしで2個まで移動 := house_A.every;

実行;
記録1;

house_B := 被りなしで全て移動 := list_A.every;

実行;


list_B := 被りなしで2個まで移動 := house_B.every;

実行;
記録2;

house_C := 被りなしで全て移動 := list_B.every;

実行;


list_C := 被りなしで2個まで移動 := house_C.every;

実行;
記録3;

house_A := 被りなしで全て移動 := list_C.every;

実行;


sum(house_A) == 15;
sum(house_B) == 30;
sum(house_C) == 45;

記録1 {
    print(listA);
}

記録2 {
    print(listB);
}

記録3 {
    print(listC);
}

「house_B.every := 被りなしで2個まで移動（listAとして保存） := house_A.every;」みたいに書ければ随分楽になるんだが、そのような機能を追加するかは保留だ。

【工夫】
人間であれば、この条件下で最終的なAの15kgになりうるのは8㎏と7㎏の対だけだと考えて、まず9㎏と13㎏を移動して、次に7㎏と合計30㎏に合致するように15㎏を移動して、最後に7㎏だけ移動させる。この工夫をどう記述すれば良いのかが分からない。
house_Aの1個以上と残りのhouse_Bとhouse_Cを合わせたもので15kgを作ろうとすると8㎏と7㎏の組み合わせになる。だから最初の組は9㎏と13㎏が入るし、残りの組の片方にはそれぞれ7㎏が入る、残りは手なりではじき出す。という感じなんだろうか。
制約が大きいのは15㎏のhouse_Aなのは間違いない。だからそこに着目して優先的に処理して、制約をはじき出してしまおうというアプローチだ。こういう問題がいくつも積み重なってきたら、それらの問題にも共通するような書き方でいつか工夫を正式に記述したい。

2024-03-31

一郎の取った皿は何個のアメがのっていた皿か？

※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。

【1999年度ジュニア算数オリンピックトライアル問題11問目】
　8つの皿にそれぞれ、9、17、24、28、30、31、33、44個のアメがのっています。まず一郎が1つの皿をアメごと取りました。そのあと、二郎、三郎、四郎の3人が同じようにいくつかずつ皿をとり、皿は全部なくなりました。調べてみると二郎と三郎のアメの数は同じで、四郎の2倍の数でした。
　最初に一郎の取った皿は何個のアメがのっていた皿ですか。

【記法化】

dishes := [9, 17, 24, 28, 30, 31, 33, 44];
ichiro := [];
jiro := [];
saburo := [];
shiro := [];

実行;

ichiro := 被りなしで1つ移動 := dishes;

実行;

jiro := 被りなしでいくつか移動 := dishes;

実行;

saburo := 被りなしでいくつか移動 := dishes;

実行;

shiro := 被りなしで全て移動 := dishes;

実行;

sum(jiro) == sum(saburo) == sum(shiro) * 2;
print(ichiro.1個);

【工夫】

dishes := [9, 17, 24, 28, 30, 31, 33, 44];
ichiro := [];
jiro := [];
saburo := [];
shiro := [];

実行;

ichiro := 被りなしで1つ移動 := dishes;

実行;

Aは自然数;
sum(dishes) == 5 * A;
shiro := 被りなしでいくつか移動 := dishes;

実行;

sum(shiro) == A;
jiro := 被りなしでいくつか移動 := dishes;

実行;

sum(jiro) == A * 2;
print(ichiro.1個);

一郎に1つ移動させた後に5の倍数になることに着目する。更にその5の倍数の5分の1を四郎に移動させれなければいけない。そして更にその5の倍数の5分の2を二郎に移動させれなければいけない。
元々の皿の合計が216なので、1つ移動させて5の倍数になるのは31だと人間なら分かる。表記からして1の位が1か6の数字に限定されると分かるからだ。しかしその表記によるラッキーを機械に求めて良いのかは分からない。216-31=185の5分の1は37。よって四郎は28と9、二郎は例えば44と30で、答えが成立すると分かる。
移動させるごとに検証が入り込むことで、計算量はぐっと減るので、この工夫は工夫として成立している。

2024-03-29

1円玉ははじめに何枚あったか？

※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。

【1999年度ジュニア算数オリンピックトライアル問題5問目】
貯金箱をあけると、1円玉、5円玉、10円玉ばかりで合計101枚出てきました。お母さんに、1円玉10枚を10円玉1枚と交かんしていってもらうと、1円玉をすべて交かんすることができて、合計の枚数は65枚になりました。1円玉は、はじめに何枚ありましたか。

【記法化】

ichiyen + goyen + zyuyen == 101;
記録1;

実行;

while (ichiyen != 0){
    if (ichiyen < 0){
        エラー;
    }
    実行;
    
    ichiyen -= 10;
    zyuyen += 1;
    実行;
}

ichiyen + goyen + zyuyen == 65;

記録1 {
    print(ichiyen);
}

【工夫】

start_total == 101;
decreases_per_step == 9;
end_total == 65;

steps == (start_total - end_total) / decreases_per_step; 
answer == steps * 10;
print(answer);

合計に着目して1行目の「ichiyen + goyen + zyuyen == 101;」の「ichiyen」「goyen」「zyuyen」の用意を飛ばす。「101枚から1円玉が10枚減って10円玉が1枚増えて合計92枚、92枚から1円玉が10枚減って10円玉が1枚増えて合計83枚～」という計算を合計65枚になるまで繰り返して、1円玉が何枚減ったかを確認するのが普通の方法。対して合計の変化に着目して、1円玉が何枚減ったかを復元するのが工夫された方法。

しかしこの手の工夫を普遍的に分類することができるんだろうか。今から疑問だ。