質問: 【クイズ】駐車スペースに、1から順に番号をつけます。 ただし、4または13を含む数字は除外します。4*、13*なども除外します。1*3のように、13の間に4以外の数字が入る場合は除外しません。このとき、 (1)1000番まで番号をつけるには、最低何台分のスペースが必要ですか。 (2)1000台ぶんの駐車スペースに番号をつけたら、一番大きな数字は何ですか。
回答: (1) あおったので回答かきます。 場合分けでやると、000~999の3桁の数字のどこにも4が出ないグループの数は9の3乗で729です。 (これは、abcという三桁の数字のaの候補の数とbの候補の数とcの候補の数を掛ける行為です) 次に、13が入ってるグループをもとめます。合致する数は3桁では13*と*13だけで、かつ*=4はすでに除かれています。 したがって*は9個しか候補がないので、13*が9個、*13が9個の合計18個。 729から18をひいて711です。(ワクは1から順番ですので、000という名前のワクは除外して、かわりに1000という名前のワクを足すので合計のワクの数は変わらず711です。) (2) 1~1000の名前をもつワクの個数は711とわかっているので1001~の名前で289個のワクが追加で必要です。 1000~1999のワクの名前を1abcという変数としてあつかいます。 (2)で求める最大の1abcは1499であろうと適当に予測します(さっきといた(1)で、3割くらいは消えることがわかっているから逆に289から10/7=1.5倍強、カサマシしておくというわけです)。これを検算します。 000~499のなかの4が入らない数字は(5-1)×(10-1)×(10-1)=324個あります。aの位の候補とbの位の候補とcの位の候補をかけあわせてるだけです。(289より大きくてちょっと安堵。) そして13について考えます。aの位には、4のほか、3も入ってはいけない(aに3を代入すると13bcという名前を持つ駐車ワクができるため)ので、さっきの式を訂正します。(5-2)×(10ー1)×(10-1)は、243個あります。このグループには4が入った数字と13bcの数字が入っていませんが1a13や113cの形の不純物はまだ残っています。(おっと、ここで289より小さくなってしまった。どうやら1499の予測は小さすぎなのであわてて上方修正すべきかもしれないのですが、いやいやあわてずにこのままやってみましょう。) 1a13は、aが0~4のうち、3,4はつかえない(もう除いた)ので、残っている不純物のワクは1013,1113,1213の3つだけですね。3個除きましょう。 113cはc候補が0~9のうち4が既に除かれているので9個除きましょう。 あわせて12個の不純物を除くことで、1000~1499の間の使えるワクの数は243-3-9で231だとわかります。これを711に足すときには1000番ワクを重複カウントすることになるので1を引く。1499までの名前をもつワクの総数は941であります。のこり59個あればちょうど1000個のワクがつくれます。 今度は1500~1599から59個のワクを調達する件ですが、これはもう簡単です。bが1すすむごとに9個のワクが追加されます。4抜きの9進数になっています。59/9の答えは10進法で6あまり5。途中で1513をも不使用にするので、あまりに1つたして、6。6あまり6を4抜きの9進数で表現するとこうなります。77。したがって1499に77を足して1576が答え。あってたかな。 答えが11bcになるような問題であると最後のほうがもうすこしややこしそうです。 おおむね、1000を4抜き9進数で表現した上で、 その範囲内にあるza13やz13c、13bcを積み上げていくほうがスマートかなーとおもいます。