wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Parking Lot
        
(Message started by: Garzahd on Jan 29^th, 2003, 12:37am)

Title: Parking Lot
Post by Garzahd on Jan 29^th, 2003, 12:37am

A parking lot has N spaces. N cars could park there, one per space, or N/2 buses could park there, one per two spaces. How many ways are there to fit some number of buses and cars?

Title: Re: New puzzle: Parking Lot
Post by Phil on Jan 29^th, 2003, 10:41am

A little specificity, please. Are you asking how many different ways the lot could be filled, or how many ways x cars and y buses could park given that x+2y is less or equal to n? And are they interchangeable or is green car, blue car, bus a different answer from blue car, green car, bus?

Title: Re: New puzzle: Parking Lot
Post by Chronos on Jan 29^th, 2003, 11:03am

We also need to know something about how these spaces are arranged. Do the spaces come in sets of two, each of which can hold one bus or two cars? Or are they all in a line? As an example, here are two possible parking lots:
______
A | B
C | D
E | F
G | H

In this one, you could park a bus in AB or CD, but not in BC. However, it might also be something like
___
| A
| B
| C
| D
| E
| F

in which case you can park a bus in BC, as well as AB or CD (maybe the busses park diagonally, or maybe these are all parallel-parking spaces).

Title: Re: New puzzle: Parking Lot
Post by Garzahd on Jan 29^th, 2003, 2:46pm

For the N=3 example, the possible fittings are (bus car), (car bus), and (car car car). So yes, the specific locations are important. But assume all cars are the same color, and all buses are the same color.

Assume the parking lot is one-dimensional.

Title: Re: New puzzle: Parking Lot
Post by ragna on Feb 4^th, 2003, 11:02pm

If I understand the problem correctly, the answer should be

[hide]
the fibonacci numbers
[/hide]

which can be found by writing a recursive definition for the problem.

Title: Re: New puzzle: Parking Lot
Post by BNC on Feb 5^th, 2003, 5:05am

You are right, ragna (I knew the answer before, so no point in submitting).

For completeness sake, here is a proof:

[hide]
For N=1: one option – Car => f(1)=1
For N=2: Two options: Car-Car or Bus => f(2)=2

For N>2: you may:
1. Place a car in the first location. Then you have f(N-1) options to complete the location.
2. Place a bus in the first (and second) location. Then you have f(N-2) options to complete the location.

In total, you have f(N) = f(N-1)+f(N-2), and f(1)=1, f(2)=2

[/hide]