PILAME杯2024 予選問12 解説

PILAME杯2024 予選問12の解説がインターネットのどこにも見当たらないので作問者が自分で解説します。

問題

$2024$以下の正整数が一つずつ書かれている黒板がある．積が平方数になるような$2$つの整数を消すという操作を何回も行えるとき，最終的に黒板に残った整数の個数の最小値を求めよ．

ネタバレ防止用余白

aaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
aabbbbbbbbbbbbbbaaaaaaaaabbbbbbbbbbbbbbb
abbbbbbbbbbbbaaaaaaaaaaaaaaabbbbbbbbbbbb
bbbbbbbbbbbaaaaaaaaaaaaaaaaaaabbbbbbabbb
bbbbbbbbbaaaaaaaaaaaaaaaaaaaaaabbbaaaaab
bbbbbbbbaaaaaaaaaaaaaaaaaaababaabbbaaabb
bbbbbbbaaaaaaaaaaaaaaaaaaababababbbaaabb
bbbbbbaaaaaaaaaaaaaaaaaaaabbbbbabbabbbab
bbbbbaaaaaaaaaaaaaaaaaabaaabbbaabbbbbbbb
bbbbaaaaaaaaaaaaaaaaaaabbaaaaaaabbbbbbbb
bbbbaaaaaaaaaaaaaaaaaaabbbaaaaaaabbbbbbb
bbbbaaaaaaaabaaaabaaaaabbbbaaaaaabbbbbbb
bbbbaaaaaaaabbaaabbaaabbbbbaaaaaabbbbbbb
bbbbaaaaaaaabbaaabbbaabbbbbaaaaaabbbbbbb
bbbbaaaaaaaabaaaabbbbabaaabaaaaaaabbbbbb
bbbbaaaaaaaaabbabbbbbbbabbabaaaaaabbbbbb
bbbbaaaaaabbabaabbbbbbbaababaaaaaabbbbbb
bbbbaaaaaabbabaabbbbbbbaababaaaaaaabbbbb
bbbbaaaaaabbabaabbbbbbbaabababbbaaabbbbb
bbbbaaaaaaabbbbbbbbbbbbbbbbbaaaaaaaabbbb
bbbbabaaaaabbbbbbbbbbbbbbbbbabbbaaaabbbb
bbbbabaaaaaabbbbbbbbbbbbbbbaabbbaaaabbbb
bbbbabaaaaaabbbbbbbbbbbbbbbaabbbaaaabbbb
bbbbabaaaaaabbbbbbaaaabbbbaaabbbaaaabbbb
bbbbbabaaaaaabbbbbaaaabbbbaaaaaaaaaabbbb
bbbbbbbaaaaaaaabbbbaabbbbaaaabbbaaaaabbb
bbbbbbbaaaaaaaaaabbbbbbaaaaaaaaaaaaaaabb
bbbbbbbaaaaaaaaaaaabbbaaaaaabaaaaaaaaaab
bbbbbbbaaaaaaaaaaabaaabaaaaabaaabaaaaaaa
bbbbbbaaaaaaaaaaaabbbbbaaaaabaaabaaaaaaa
bbbbbaaaaaaaaaaaaabbbbbaaaaaaaabbaaaaaaa
bbbbaaabaabbaaaaaaabbbaaaaaaaaabbaaabaaa
bbaaaabaaaaaaaaabbbaaabbbaaaaaaaaaaabbaa
aaaabbaaabaabbbbbbbbabbbbbbbaaaaaaaabbbb
bbbbbaaabaabbbbbbbbaabbbbbbbaaabbbaabbbb
bbbbaaabaabbbbbbbbaabbbbbbbaaabbbbbabbbb
bbaaabbaabbbbbbbbaabbbbbbbbaaabbbbbbabbb
aaaaabbabbbbbbbbaabbbbbbbbaaaabbbbbababb
bbabbaaabbbbbbbbabbbbbbbbbaaabbaababbbab
babbbbabbbbbbbbbabbbbbbbbaaabbaababbbbba

解説

正整数 $n$ を正整数 $a$ と平方因子を持たない正整数 $b$ で $n=a^2b$ と表すとき，2つの整数の組を消すことができる条件は $b$ が等しい事である．
この時、各 $b$ について消せる組の個数は，正整数 $x$ と平方因子を持たない正整数 $b$ で $n=(2x)^2b\leq 2024$ と書ける $n$ の個数と等しい．$n=(2x)^2b$ と書けることは $n$ が $4$ の倍数である事と同値なので、消せる組は $506$ 組になる．よって、$2024-506\times2=1012$ が答えになる。