Ktya https://blog.hatena.ne.jp/Ktya/ Ktya’s blog https://ktya.hatenadiary.jp/ SLP SLP_2018 SLP 2018 C6 概要 aとbを異なる正整数とする。何も数字が描かれていない黒板に対して以下の操作を無限回行う。① 黒板に同じ数字が書かれているときどちらかをa増やし、もう片方をb増やす。② ①ができないとき、新しく0を二つ書く。ここで、どのように①の操作を行っても②の操作を行う回数は必ず有限回になることを示せ。 以下後日更新 証明 g=gcd(a,b)としたときに、全ての数をgで割ることでg=1として一般性を失わない。 ①の操作を有限回、②の操作をN+1回行った直後の状態を考える。 で本状態に至るまでに黒板にxが書かれた回数をあらわすことにする。xが負の時は0として、第二変数は整数全体… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fktya.hatenadiary.jp%2Fentry%2F2020%2F04%2F26%2F200715" title="SLP2018 Cうめ - Ktya’s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=f%28N%2Cx%29 Hatena Blog https://hatena.blog 2020-04-26 20:07:15 rich https://ktya.hatenadiary.jp/entry/2020/04/26/200715 1.0 100%