こんにちは。東久留米市の学習塾塾長です。
弱い北風が吹いていて寒い日になりました。今日は建国記念の日で通常授業はお休みです。とは言え、中３の受験生は来るはずなのですが、昨日私立高校の受験で疲れたのか、お休みのようです。
昨日に続いて麻布中の算数入試問題大問５を紹介します。
問題は、剰余に関するもので、「１番から９９９９番のカードに９９で割ったときの余りと１０１で割ったときの余りが書いてあって、それぞれ５１と４１と書いてあるカードは何枚目のカードか」というものです。
初めに力ずくで解いてみます。
このカードがＮ枚目（Ｎ≦９９９９）とすると、
Ｎ＝９９ｐ＋５１＝１０１ｑ＋４１ 式（１）
が成り立ちます。
ここでｐとｑを０から１ずつ増やして計算すると、ｐ＝ｑ＝５のとにＮ＝５４６になり正解に辿り着きます。（０≦Ｎ≦９９９９の範囲に５４６以外で式（１）を満たすＮの有無を調べていないので不完全ですが）
そこで、少し工夫します。
式（１）を変形して、
１０１ｑ－９９ｐ＝１０ 式（２）
とします。
ｐとｑとの大小関係で場合分けすると、
（１）ｐ＝ｑのとき、
１０１ｐ－９９ｐ＝２ｐ＝１０から、ｐ＝５、ｑ＝５
式（１）にｐ＝５を代入して、Ｎ＝５４６
（２）ｐ＞ｑ（ｐ＝ｑ＋ｒ、ｒ≧１を満たす整数）のとき、
式（２）は、１０１ｑ－９９（ｑ＋ｒ）＝２ｑ－９９ｒ＝１０
２ｑ＝９９ｒ＋１０
２ｑ、１０が偶数なのでｒは偶数となり、ｒ＝２とすると、
２ｑ＝２０８より、ｑ＝１０４
ｑ＝１０４を式（１）に代入して、Ｎ＝１０５４５となり、Ｎ≦９９９９に反する。
ｒ≧４の場合も同じ。
（３）ｐ＜ｑ（ｐ＝ｑ－ｒ、ｒ≧１を満たす整数）のとき、
式（２）は、１０１ｑ－９９（ｑ－ｒ）＝２ｑ＋９９ｒ＝１０
２ｑ＝１０－９９ｒ＜０より、ｑの解はなし。
以上より、Ｎ＝５４６となります。
他にも連立合同式を使う解法があります。
Ｎ≡５１（ｍｏｄ９９） 式（３）
Ｎ≡４１（ｍｏｄ１０１） 式（４）
式（３）、（４）を満たすＮは、
Ｎ≡５１×１０１×Ａ＋４１×９９×Ｂ
〔但し、１０１Ａ≡１（ｍｏｄ９９）、９９Ｂ≡１（ｍｏｄ１０１）〕
そこで、Ａ、Ｂを求めると、
１＝９９×５０＋１０１×（－９９）より、Ａ＝５０
１＝９９×（－５１）＋１０１×５０より、Ｂ＝５０
従って、
Ｎ≡５１×１０１×５０＋４１×９９×５０≡４６０５００
≡５４６（ｍｏｄ９９９９）
０≦Ｎ≦９９９９より、Ｎ＝５４６となります。
次の小問（３）は、小問（２）より複雑になります。
問題は、「９９９９００枚のカードで、９９、１００および１０１で割ったときの余りが、それぞれ３７、１５、１となるカードを求めよ」というものです。
まず、合同式を使って解いてみます。
Ｍ≡３７（ｍｏｄ９９） 式（５）
Ｍ≡１５（ｍｏｄ１００） 式（６）
Ｍ≡１ （ｍｏｄ１０１） 式（７）
式（５）、（６）、（７）を満たすＭは、
Ｍ≡３７×１０１００×Ｄ＋１５×９９９９×Ｅ＋１×９９００×Ｆ
〔但し、１０１００Ｄ≡１（ｍｏｄ９９）、９９９９Ｅ≡１（ｍｏｄ１００）、９９００Ｆ≡１（ｍｏｄ１０１）〕
そこで、Ｄ、Ｅ、Ｆを求めると、
１＝１０１００×５０＋９９×（－５１０１）より、Ａ＝５０
１＝９９９９×９９＋１００×（－９８９９）より、Ｂ＝９９
１＝９９００×５１＋１０１×（－４９９９）より、Ｃ＝５１
従って、
Ｍ≡１８６８５０００＋１４８４８５１５＋５０４９００≡３４０３８４１５
≡４１８１５（ｍｏｄ９９９９００）
０≦Ｍ≦９９９９００より、Ｍ＝４１８１５となります。
合同式を使うとシステマティックに解けるのですが、この問題のように法が大きい数の場合、電卓が欲しいところです。
そこで、合同式を使わないで解いてみましょう。
Ｍ＝９９Ｑ＋３７ 式（８）
Ｍ＝１００Ｒ＋１５ 式（９）
Ｍ＝１０１Ｓ＋１ 式（１０）
Ｑ＝Ｒ＋ｎ、Ｒ＝Ｓ＋ｍとすると、
式（８）、（９）から、
９９Ｑ＋３７＝１００（Ｑ－ｎ）＋１５
Ｑ＝１００ｎ＋２２
また、式（９）、（１０）から、
１００Ｒ＋１５＝１０１（Ｒ－ｍ）＋１
Ｒ＝１０１ｍ＋１４
そこで、
Ｑ＝Ｒ＋ｎより、
１００ｎ＋２２＝１０１ｍ＋１４＋ｎ
１０１ｍ－９９ｎ＝８ 式（１１）
つまり、式（１１）を満たす整数ｍ、ｎを求めればよい。
（ここで、場合分けは省略して）
ｍ＝ｎ＝４
従って、Ｑ＝４２２、Ｒ＝４１８、Ｓ＝４１４
以上より、Ｍ＝９９×４２２＋３７＝４１８１５
（実は、面倒な場合分けを省略しているので不完全なのですが・・・）
合同式は高校でも詳しく勉強しませんが、整数問題などに威力を発揮するツールです。興味があれば、勉強してみて下さい。
それにしても麻布中の問題は楽しいですね。明日は、大問６を紹介します。
弱い北風が吹いていて寒い日になりました。今日は建国記念の日で通常授業はお休みです。とは言え、中３の受験生は来るはずなのですが、昨日私立高校の受験で疲れたのか、お休みのようです。
昨日に続いて麻布中の算数入試問題大問５を紹介します。
問題は、剰余に関するもので、「１番から９９９９番のカードに９９で割ったときの余りと１０１で割ったときの余りが書いてあって、それぞれ５１と４１と書いてあるカードは何枚目のカードか」というものです。
初めに力ずくで解いてみます。
このカードがＮ枚目（Ｎ≦９９９９）とすると、
Ｎ＝９９ｐ＋５１＝１０１ｑ＋４１ 式（１）
が成り立ちます。
ここでｐとｑを０から１ずつ増やして計算すると、ｐ＝ｑ＝５のとにＮ＝５４６になり正解に辿り着きます。（０≦Ｎ≦９９９９の範囲に５４６以外で式（１）を満たすＮの有無を調べていないので不完全ですが）
そこで、少し工夫します。
式（１）を変形して、
１０１ｑ－９９ｐ＝１０ 式（２）
とします。
ｐとｑとの大小関係で場合分けすると、
（１）ｐ＝ｑのとき、
１０１ｐ－９９ｐ＝２ｐ＝１０から、ｐ＝５、ｑ＝５
式（１）にｐ＝５を代入して、Ｎ＝５４６
（２）ｐ＞ｑ（ｐ＝ｑ＋ｒ、ｒ≧１を満たす整数）のとき、
式（２）は、１０１ｑ－９９（ｑ＋ｒ）＝２ｑ－９９ｒ＝１０
２ｑ＝９９ｒ＋１０
２ｑ、１０が偶数なのでｒは偶数となり、ｒ＝２とすると、
２ｑ＝２０８より、ｑ＝１０４
ｑ＝１０４を式（１）に代入して、Ｎ＝１０５４５となり、Ｎ≦９９９９に反する。
ｒ≧４の場合も同じ。
（３）ｐ＜ｑ（ｐ＝ｑ－ｒ、ｒ≧１を満たす整数）のとき、
式（２）は、１０１ｑ－９９（ｑ－ｒ）＝２ｑ＋９９ｒ＝１０
２ｑ＝１０－９９ｒ＜０より、ｑの解はなし。
以上より、Ｎ＝５４６となります。
他にも連立合同式を使う解法があります。
Ｎ≡５１（ｍｏｄ９９） 式（３）
Ｎ≡４１（ｍｏｄ１０１） 式（４）
式（３）、（４）を満たすＮは、
Ｎ≡５１×１０１×Ａ＋４１×９９×Ｂ
〔但し、１０１Ａ≡１（ｍｏｄ９９）、９９Ｂ≡１（ｍｏｄ１０１）〕
そこで、Ａ、Ｂを求めると、
１＝９９×５０＋１０１×（－９９）より、Ａ＝５０
１＝９９×（－５１）＋１０１×５０より、Ｂ＝５０
従って、
Ｎ≡５１×１０１×５０＋４１×９９×５０≡４６０５００
≡５４６（ｍｏｄ９９９９）
０≦Ｎ≦９９９９より、Ｎ＝５４６となります。
次の小問（３）は、小問（２）より複雑になります。
問題は、「９９９９００枚のカードで、９９、１００および１０１で割ったときの余りが、それぞれ３７、１５、１となるカードを求めよ」というものです。
まず、合同式を使って解いてみます。
Ｍ≡３７（ｍｏｄ９９） 式（５）
Ｍ≡１５（ｍｏｄ１００） 式（６）
Ｍ≡１ （ｍｏｄ１０１） 式（７）
式（５）、（６）、（７）を満たすＭは、
Ｍ≡３７×１０１００×Ｄ＋１５×９９９９×Ｅ＋１×９９００×Ｆ
〔但し、１０１００Ｄ≡１（ｍｏｄ９９）、９９９９Ｅ≡１（ｍｏｄ１００）、９９００Ｆ≡１（ｍｏｄ１０１）〕
そこで、Ｄ、Ｅ、Ｆを求めると、
１＝１０１００×５０＋９９×（－５１０１）より、Ａ＝５０
１＝９９９９×９９＋１００×（－９８９９）より、Ｂ＝９９
１＝９９００×５１＋１０１×（－４９９９）より、Ｃ＝５１
従って、
Ｍ≡１８６８５０００＋１４８４８５１５＋５０４９００≡３４０３８４１５
≡４１８１５（ｍｏｄ９９９９００）
０≦Ｍ≦９９９９００より、Ｍ＝４１８１５となります。
合同式を使うとシステマティックに解けるのですが、この問題のように法が大きい数の場合、電卓が欲しいところです。
そこで、合同式を使わないで解いてみましょう。
Ｍ＝９９Ｑ＋３７ 式（８）
Ｍ＝１００Ｒ＋１５ 式（９）
Ｍ＝１０１Ｓ＋１ 式（１０）
Ｑ＝Ｒ＋ｎ、Ｒ＝Ｓ＋ｍとすると、
式（８）、（９）から、
９９Ｑ＋３７＝１００（Ｑ－ｎ）＋１５
Ｑ＝１００ｎ＋２２
また、式（９）、（１０）から、
１００Ｒ＋１５＝１０１（Ｒ－ｍ）＋１
Ｒ＝１０１ｍ＋１４
そこで、
Ｑ＝Ｒ＋ｎより、
１００ｎ＋２２＝１０１ｍ＋１４＋ｎ
１０１ｍ－９９ｎ＝８ 式（１１）
つまり、式（１１）を満たす整数ｍ、ｎを求めればよい。
（ここで、場合分けは省略して）
ｍ＝ｎ＝４
従って、Ｑ＝４２２、Ｒ＝４１８、Ｓ＝４１４
以上より、Ｍ＝９９×４２２＋３７＝４１８１５
（実は、面倒な場合分けを省略しているので不完全なのですが・・・）
合同式は高校でも詳しく勉強しませんが、整数問題などに威力を発揮するツールです。興味があれば、勉強してみて下さい。
それにしても麻布中の問題は楽しいですね。明日は、大問６を紹介します。
※コメント投稿者のブログIDはブログ作成者のみに通知されます