Weekend Mathematics／問題／問題99



９９．駐車場の問題

一列に１２区画に区切られた駐車場があり、乗用車は１区画、トラックは連続した２区画を必要とする。 ６台の乗用車と２台のトラックが駐車していて、さらにトラック１台が駐車できる空き区画がある。 このように乗用車とトラックを駐車区画に駐車するパターンは何通りあるか。ただし各乗用車、各トラックは区別しない。

Hint：例えばこれで１通り




問題の出典


数学オリンピック　1991〜1996
数学オリンピック財団編
日本評論社
第３回日本数学オリンピック予選問題




答えと解説





答えと解説

解答・その1

（ペンネ−ム：やんま）

ｎを問題の区画数、Ｔをトラックの台数としてＴ＝１，ｎ＝２Ｔ＝２から順次パターンを調べてみると次の表のようになる。
Ｔ＝１の行はｎが２，３，４・・・ならパターンは１，２，３・・・と増加する。
Ｔ＝２の行で２Ｔ＋１の列の値はその上の２と左の１との合計である。
以下同様の規則性がある表を作成するのは容易である。
問題はｎ＝１２，Ｔ＝３であるから２Ｔ＋６の列とＴ＝３の行との 交点の値が解である。

　　　　答え　８４通り

　　n 2T2T+12T+22T+32T+42T+5 2T+6 2T+7
T=11234 56 7 8
T=213610 1521 28 36
T=3 1 4 10 20 35 56 84 120
T=4151535 70126 210 330
T=5162156 126252 462 792
T=6172884 210462 924 1716


注）問題がわかりにくかったかもしれませんが、 ３台のトラックが同等ではなく、最後のトラックだけ区別をしています。 従って、８４×３＝２５２が正解となります。(Junko)



解答・その2

（ペンネ−ム：浜田　明巳）

私が問題を取り違えているのか，あまり綺麗な結論にはいたりませんでした．
左から１区画〜１２区画と番号付けをします．
(１，２)区画〜(１１，１２)区画のそれぞれに空き区画を設け，それぞれの場合の数を求める．
以下がその答となる．

Option Explicit
Public VACANT As Integer
Sub Macro1()
　　Sheets("Sheet1").Select
　　Cells(1, 1).Value = 0
　　Dim a(9) As Integer
　　Dim j As Integer
　　For VACANT = 1 To 12 - 1 'VACANT=j:左からj,j+1番目の2区画が空
　　　If VACANT = 1 Then
　　　　a(1) = 2
　　　　Call saiki2(2, a())
　　　Else
　　　　Call saiki1(1, a())
　　　End If
　　Next VACANT
　　For j = 1 To 12 - 1
　　　Cells(j, 13).Value = "(" + strr(j) + "," + strr(j + 1) + ")区画"
　　　Cells(j, 14).Value = "=COUNTIF(B1:B" + strr(Cells(1, 1).Value) + "," + Str(j) + ")"
　　Next j
　　Range("A1").Select
End Sub
Sub saiki1(ByVal n As Integer, ByRef a() As Integer)
　　Dim wa As Integer
　　Dim j As Integer
　　a(n) = 1
　　While a(n) <= 2
　　　If QX(n, a()) Then
　　　　wa = 0
　　　　For j = 1 To n
　　　　　wa = wa + a(j)
　　　　Next j
　　　　If wa < VACANT - 1 Then
　　　　　Call saiki1(n + 1, a())
　　　　ElseIf wa = VACANT - 1 Then
　　　　　a(n + 1) = 2
　　　　　If n + 1 < 9 Then
　　　　　　Call saiki2(n + 2, a())
　　　　　Else
　　　　　　Call check(a())
　　　　　End If
　　　　End If
　　　End If
　　　a(n) = a(n) + 1
　　Wend
End Sub
Sub saiki2(ByVal n As Integer, ByRef a() As Integer)
　　Dim j As Integer
　　a(n) = 1
　　While a(n) <= 2
　　　If QX(n, a()) Then
　　　　If n < 9 - 1 Then
　　　　　Call saiki2(n + 1, a())
　　　　Else
　　　　　a(9) = 1 * 6 + 2 * 3
　　　　　For j = 1 To 9 - 1
　　　　　　a(9) = a(9) - a(j)
　　　　　Next j
　　　　　If QX(9, a()) Then
　　　　　　Call check(a())
　　　　　End If
　　　　End If
　　　End If
　　　a(n) = a(n) + 1
　　Wend
End Sub
Sub check(ByRef a() As Integer)
　　Dim wa As Integer
　　Dim j As Integer
　　Cells(1, 1).Value = Cells(1, 1).Value + 1
　　Cells(Cells(1, 1).Value, 2).Value = VACANT
　　wa = 0
　　For j = 1 To 9
　　　wa = wa + a(j)
　　　If wa <>  VACANT + 1 Then
　　　　Cells(Cells(1, 1).Value, j + 2).Value = a(j)
　　　Else
　　　　Cells(Cells(1, 1).Value, j + 2).Value = "space"
　　　End If
　　Next j
　　Range("B" & Cells(1, 1).Value).Select
End Sub
Private Function QX(ByVal n As Integer, ByRef a() As Integer) As Integer
　　Dim b(2) As Integer
　　Dim j As Integer
　　For j = 1 To 2
　　　b(j) = 0
　　Next j
　　For j = 1 To n
　　　b(a(j)) = b(a(j)) + 1
　　Next j
　　QX = -(b(1) <= 6 And b(2) <= 3)
End Function
Private Function strr(ByVal n As Integer) As String
　　strr = Right(Str(n), Len(Str(n)) - 1)
End Function

(1,2)区画 28
(2,3)区画 21
(3,4)区画 22
(4,5)区画 22
(5,6)区画 22
(6,7)区画 22
(7,8)区画 22
(8,9)区画 22
(9,10)区画 22
(10,11)区画 21
(11,12)区画 28
合計 252





解答・その3

（ペンネ−ム：ＪＳミル）

駐車場が横に並んでいて，左から順番に1,2,3,4.....,12として，トラック2台分の空 きごとに場合分けをしてみました．

1）空きが駐車場（1,2）の場合
　1台めのトラックが入る場所が
　（3,4）の時，2台めは（5,6）（6,7）（7,8）（8,9）（9,10）（10,11）（11,12） の7通り
　（4,5）の時，（6,7）（7,8）........（11,12）の6通り
　（5,6）の時，（7,8）（8,9）....（11,12）の5通り
　（6,7）の時，同様に4通り
　（7,8）の時，3通り
　（8,9）の時，2通り
　（9,10）の時，1通り　　　で計28通りです．

2）空きが駐車場（2,3）の場合
　1台めのトラックが入る場所が
　（4,5）の時，2台めは（6,7）（7,8）（8,9）.....（11,12）の6通り
　（5,6）の時，（7,8）....（11,12）の5通り
　　・
　　・
　（11,12）の時，1通り　　　　で計21通りです．

同じように
3）空きが駐車場（3,4）の場合　　　計22通り
4）空きが駐車場（4,5）の場合　　　計22通り
5）空きが駐車場（5,6）の場合　　　計22通り
6）空きが駐車場（6,7）の場合　　　計22通り
なお，空きが（7,8）（8,9）（9,10）（10,11）（11,12）の場合は，それぞれ（5,6） （4,5）（3,4）（2,3）（1,2）と同じはずですから，
（28＋21＋22＋＋22＋22）×2＋22=252　で　　答えは252通りです．




解答・その4

（ペンネ−ム：Mr.X）

３台のトラックと6台の乗用車が駐車する場合の数

駐車場の区画を左から順にA,B,C,D,E,F,G,H,I,J,K,L とする。

トラックの最右のものが
（E,F）に在る場合・・・・・・・・・・・1通り
（F,G）に在る場合・・・・・・・・・・2+1通り
（G,H）に在る場合・・・・・・・・・3+2+1通り
（H,I）に在る場合・・・・・・・・4+3+2+1通り
（I,J）に在る場合・・・・・・・5+4+3+2+1通り
（J,K）に在る場合・・・・・6+5+4+3+2+1通り
（K,L）に在る場合・・・・7+6+5+4+3+2+1通り

合計　　

３台のトラックのうち１台が透明であるときの置き方は、これの３倍で ２５２通り

解答は２５２通り




　

解答・その5

（ペンネ−ム：佐野允信）

駐車場の区画に下図のように番号をつける。



区別のつく３台のトラックＴ１、Ｔ２、Ｔ３を駐車し、それ以外の区画に乗用車を駐車するとする。 トラックＴ１、Ｔ２、Ｔ３を 駐車する区画の番号の組をそれぞれ（ｉ，ｉ＋１）、（ｊ，ｊ＋１）、（ｋ，ｋ＋１）とする。 ただし、ｉ＜ｉ＋１＜ｊ＜ｊ＋１＜ｋ＜ｋ＋１とする。
ｉ＝ｌ（１≦ｌ≦１２）とすると、トラックＴ１は（ｌ，ｌ＋１）に駐車することになる。 トラックＴ２、Ｔ３を駐車することのできる区画は下図のとおりである。



これらの区画の総数は、

　　　　１２−（ｌ＋１）＝１１−ｌ

（１１−ｌ）区画にトラックＴ２、Ｔ３を駐車しなければならないので、

　　　　１１−ｌ≧４

　　　　ｌ≦７　　・・・(1)

これらの区画の番号を下図のようにつけかえる。



ｊ’＝ｍ（１≦ｍ≦１１−ｌ）とすると、トラックＴ２は（ｍ，ｍ＋１）に駐車することになる。トラックＴ３を駐車することのできる区画は下図のとおりである。



これらの区画の総数は

　　　　（１１−ｌ）−（ｍ＋１）＝１０−ｌ−ｍ

（１０−ｌ−ｍ）区画にトラックＴ３を駐車しなければならないので、

　　　　１０−ｌ−ｍ≧２

　　　　ｍ≦８−ｌ　　・・・(2)

トラックＴ３を（ｋ’，ｋ’＋１）に駐車するとすると、ｋ’は

　　　　ｋ’＝ｍ＋２，ｍ＋３，・・・、１０−ｌ

の値をとり得るので、ｋ’のとり得る値の総数は、

　　　　（１０−ｌ）−（ｍ＋１）＝（９−ｌ）−ｍ　　・・・(3)

従って、区別のつくトラックＴ１、Ｔ２、Ｔ３を左からこの順番に 駐車したときのパターン数は、



Ｔ１、Ｔ２、Ｔ３を、区別のつかない２台のトラックと、連続する ２つの空いた区画としたときのパターンの総数が求める数である。よって、

　　　　84×3=252　　　−（答）




解答・その6

（ペンネ−ム：巷の夢）

トラックの駐車場が12区画のどこにあるかで分類すればよく、 例えば、2台はくっついて残り1台が1区画づつ離れるとすると下の様に7通りとなる。



次に以下の様に2台目が1区画、3台目が一つづつ離れるとすると６通りとなる。



以下同様に2台目が2区画、3台目が一つづつ離れるを繰り返すと、5,4,3,2＆1通りとなる。 即ち、全部で28通りとなる。この考えで左端に1,2,3・・・・と乗用車の駐車区画を作っていくと21,15,10,6,3,1通りとなりこれらを全て加えると84通りを得る。トラックと乗用車は区別しないとされている。因って、トラックの空き区間は各々3通りあるから、84×3＝252通りが求めるものである。　



解答・その7

（ペンネ−ム：アッチョンブリケ）

先ず、３箇所のトラックの駐車の区画分の両脇・計４箇所にいくつずつ乗用車の 駐車６区画分を配置するかを考える。

（0,0,0,6),(0,0,1,5),(0,0,2,4),・・・・・,(5,1,0,0),(6,0,0,0)

このように配置のパターンがある。
これが何通りか求めると、
乗用車の駐車６区画分の配分の仕方は次のように９通りあり、
それぞれの配置の仕方は、

(0,0,0,6) ４通り
(0,0,1,5) 4*3＝　１２通り
(0,0,2,4) 4*3＝　１２通り
(0,0,3,3) 4*3/2＝　６通り
(0,1,1,4) 4*3＝　１２通り
(0,1,2,3) 4*3*2＝　２４通り
(0,2,2,2) ４通り
(1,1,1,3) ４通り
(1,1,2,2) 4*3/2＝　６通り

計4+12+12+6+12+24+4+4+6=　８４通りある。

次に、３箇所のトラックの駐車のうち、空き区画１箇所をどれとみなすかにより ３通りあるので求める全パターンは、計84*3=　２５２通りとなる。

答．２５２通り



解答・その8

（ペンネ−ム：杖のおじさん）

答え　２５２通り
注．最初にトラックの空きに関係なく組み合わせが何通りあるか計算します。
nCr=n!/(n-r)!r!を使います
従って６台の乗用車と３台のトラックなので駐車すぺースの組み合わせは ９！／(９−３)！３！となります。
これを計算すると８４になります。
トラックの駐車スペースに空きが１台ありますので上の組み合わせが３通りあります。
８４×３＝２５２通りです




解答・その9

（ペンネ−ム：ＦＩＶＥＩＬＡＮＤ）

答え　２５２通り

考え方　９！÷（６！×２！×１！）＝２５２　簡単に考えすぎましたでしょうか？




解答・その10

（ペンネ−ム：kiyo）

9C6*3C2 =9C3*3C1=252

答え　　　　　　　252通り。




解答・その11

（ペンネ−ム：蜘蛛の巣城）

「12区画」にとらわれてはいけません。

駐車パターンを

　　　　「９つの駐車区画があって、そのうち３つがトラック用である」

と認識するのが簡明なのではないでしょうか。「トラック用」とは「2区画」を意味すると決めておけば良いと思います。
従って、トラック用を選び出せばよいのですからコンビネーションの問題です。
ただし、トラックは2台で空きが1台分あり、これを区別しなければなりません。

　　　　　９Ｃ３×3＝252　（通り）



解答・その12

（ペンネ−ム：challenger）

トラック2台分の区画とトラック用の空区画、乗用車6台分の 区画の合計9区画の中からトラック駐車用区画として3区画を選 び、次に3区画のうちどれかを空区画にすればよいから求める
場合の数は

　　　9C3*3=252（通り）



解答・その13

（ペンネ−ム：gankopan）

まず、トラック2台、乗用車6台の並べ方を考える。
トラック同士、乗用車同士の区別をしないことから、その場合の数は

　　　　8！/（2！*6！）=28通り

次に、連続2区画の空きスペースを入れるが、その候補は、計8 台の車の両端または間になるので、空きスペースの入れ方は9 通り。
以上から、求める場合の数は

　　　　28*9=252通りとなる。



解答・その14

（ペンネ−ム：ミルク）

乗用車6台、トラック3台で12区画は埋められるので空きスペースはない。
乗用車とトラックを一列に並べる順列は9C3=84通り。
このうち、まだ駐車されていないスペースがどれであるかというのが3C1=3通り。
よって84×3＝252通り。

とは言ったものの、「トラックは連続した２区画を必要とする」の解釈が微妙で、常 識的に考えてトラックの幅は乗用車の幅の2倍もない（普通縦に駐車するだろうから 「幅」でいいと思う）。1区画に乗用車1台とめられるのならトラックは1.2区画くら いあれば停められるんじゃないか。つまり、例えば連続した3区画に2台のトラックを 駐車することができる気がする。そう考えたら上に書いた「1.2区画」の値が実際は いくつなのかで場合分けが必要となる。（1より大きく、2以下の値であることは分 かっているので、不等式で範囲を与えて、そのとき何通りか・・・となる）



解答・その15

（ペンネ−ム：高橋道広）

答え252通り

乗用車をa　トラックをb　空き区画をｃとすると　a６つとb２つとc１つをなら べる方法は何通りあるか　という問題になる
よって「同じものを含む順列」の考え方から

　　　　9!÷6!÷2!÷1!=252通り



解答・その16

（ペンネ−ム：Toru）

乗用車を６台並べておいて、その左右あるいは間の合計７ケ所から重複を許して３ 箇所選んで、トラックをおくと考えれば、
これは7Ｈ3=9Ｃ3=84通り。
トラック３台の うちの１台がどこかへ行ってしまったとすれば、トラックの選び方は３通りで、求め る数は　84x3=252

　　　　　　　　　　　　答え　252 通り

当然ですが、先にトラック３台を並べその左右あるいは間の４ケ所から重複を許し て６つ選ぶとしても、
4Ｈ6=9Ｃ6 =9Ｃ3=84 で　84x3=252と同じになりますね。



解答・その17

（ペンネ−ム：夜ふかしのつらいおじさん）

答は，3Ｃ1×4Ｈ6＝３×9Ｃ6＝３×８４＝２５２通りです。

（１）この問題は始めに１２区画を用意してトラックや乗用車を入れていくと， 場合の数を数えるのが大変です。
（２）最初にトラック２台とトラック１台分の空きスペースを並べ，そのすきま や両端に乗用車６台を入れていき，結果的に１２区画になったと考えた方が楽で す。
この考え方は重複組合せです。

繰り返しを許してｎ個からｒ個取る場合の数をnＨrと表します。
この記号には次の関係式が成り立ちます。

　1Ｈr＝１，　nＨ1＝ｎ

n+1Ｈr＝n+1Ｈr-1＋nＨr　（特定の１個が選ばれる場合と選ばれない場合の和）

具体的に，

4Ｈ6
＝4Ｈ5＋3Ｈ6
＝4Ｈ4＋3Ｈ5＋3Ｈ5＋2Ｈ6
＝4Ｈ3＋3Ｈ4＋２×(3Ｈ4＋2Ｈ5)＋2Ｈ5＋1Ｈ6
＝4Ｈ2＋3Ｈ3＋３×(3Ｈ3＋2Ｈ4)＋３×(2Ｈ4＋1Ｈ5)＋１
＝4Ｈ1＋3Ｈ2＋４×(3Ｈ2＋2Ｈ3)＋６×(2Ｈ3＋1Ｈ4)＋３＋１
＝４＋５×(3Ｈ1＋2Ｈ2)＋１０×(2Ｈ2＋1Ｈ3)＋６＋３＋１
＝４＋５×３＋１５×(2Ｈ1＋1Ｈ2)＋１０＋６＋３＋１
＝４＋５×３＋１５×(２＋１)＋１０＋６＋３＋１
＝４＋１５＋１５×３＋２０
＝８４


（１）のように具体的に数えてみます。
Ｔをトラック，ｃを乗用車とします。
縦線｜の左側の・の部分へのｃの配置の場合分けをして，｜の右側の場合の数を 数えます。

　　　・Ｔ・Ｔ｜・Ｔ・

０）ＴＴ｜Ｔｃｃｃｃｃｃの場合は，７通り

１）ＴｃＴ｜Ｔｃｃｃｃｃの場合は，６通り
　　ｃＴＴ｜Ｔｃｃｃｃｃの場合は，６通り

２）ＴｃｃＴ｜Ｔｃｃｃｃの場合は，５通り
　　ｃＴｃＴ｜Ｔｃｃｃｃの場合は，５通り
　　ｃｃＴＴ｜Ｔｃｃｃｃの場合は，５通り

３）ＴｃｃｃＴ｜Ｔｃｃｃの場合は，４通り
　　ｃＴｃｃＴ｜Ｔｃｃｃの場合は，４通り
　　ｃｃＴｃＴ｜Ｔｃｃｃの場合は，４通り
　　ｃｃｃＴＴ｜Ｔｃｃｃの場合は，４通り

４）ＴｃｃｃｃＴ｜Ｔｃｃの場合は，３通り
　　ｃＴｃｃｃＴ｜Ｔｃｃの場合は，３通り
　　ｃｃＴｃｃＴ｜Ｔｃｃの場合は，３通り
　　ｃｃｃＴｃＴ｜Ｔｃｃの場合は，３通り
　　ｃｃｃｃＴＴ｜Ｔｃｃの場合は，３通り

５）ＴｃｃｃｃｃＴ｜Ｔｃの場合は，２通り
　　ｃＴｃｃｃｃＴ｜Ｔｃの場合は，２通り
　　ｃｃＴｃｃｃＴ｜Ｔｃの場合は，２通り
　　ｃｃｃＴｃｃＴ｜Ｔｃの場合は，２通り
　　ｃｃｃｃＴｃＴ｜Ｔｃの場合は，２通り
　　ｃｃｃｃｃＴＴ｜Ｔｃの場合は，２通り

６）ＴｃｃｃｃｃｃＴ｜Ｔの場合は，１通り
　　ｃＴｃｃｃｃｃＴ｜Ｔの場合は，１通り
　　ｃｃＴｃｃｃｃＴ｜Ｔの場合は，１通り
　　ｃｃｃＴｃｃｃＴ｜Ｔの場合は，１通り
　　ｃｃｃｃＴｃｃＴ｜Ｔの場合は，１通り
　　ｃｃｃｃｃＴｃＴ｜Ｔの場合は，１通り
　　ｃｃｃｃｃｃＴＴ｜Ｔの場合は，１通りの合計８４通り。




正解者

kiyo ＪＳミル 巷の夢
Toru 浜田　明巳 ＦＩＶＥＩＬＡＮＤ
杖のおじさん 夜ふかしのつらいおじさん Mr.X
佐野允信 challenger 蜘蛛の巣城
高橋道広 アッチョンブリケ gankopan
ミルク やんま





まとめ

基本は数え上げだと思うのですが、いただいた解答の中にもいろいろな解法があって、 大変興味深く読ませていただきました。
「８４」という解答を何件かいただきましたが、 ３台のトラックは同等ではなく、最後の１台だけは別物と解釈しますと、 「２５２」ということになります。
蜘蛛の巣城さんのご指摘の通り、１２区画ということにとらわれず、

　　　　A,A,A,A,A,A,B,B,B'

をどう並べるかというように問題を置き換えると、 同じものを含む順列、もしくは重複組み合わせの問題としてとらえることができます。 重複組み合わせについては、夜ふかしのつらいおじさん が丁寧に解説してくださっています。どうもありがとうございました。 こちらにも重複組み合わせの解説があります、ご参考までに。





E-mail top