wu :: forums « wu :: forums - Parking Lot » Welcome, Guest. Please Login or Register. Apr 20th, 2024, 1:47pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: william wu, towr, ThudnBlunder, Icarus, Eigenray, SMQ, Grimbal)    Parking Lot « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Parking Lot  (Read 4266 times)
Garzahd
Junior Member

Gender:
Posts: 130
 Parking Lot   « on: Jan 29th, 2003, 12:37am » Quote Modify

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?
 « Last Edit: Oct 23rd, 2003, 8:11pm by Icarus » IP Logged
Phil
Newbie

Posts: 38
 Re: New puzzle: Parking Lot   « Reply #1 on: Jan 29th, 2003, 10:41am » Quote Modify

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?
 IP Logged
Chronos
Full Member

Gender:
Posts: 288
 Re: New puzzle: Parking Lot   « Reply #2 on: Jan 29th, 2003, 11:03am » Quote Modify

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).
 IP Logged
Garzahd
Junior Member

Gender:
Posts: 130
 Re: New puzzle: Parking Lot   « Reply #3 on: Jan 29th, 2003, 2:46pm » Quote Modify

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.
 IP Logged
ragna
Guest

 Re: New puzzle: Parking Lot   « Reply #4 on: Feb 4th, 2003, 11:02pm » Quote Modify Remove

If I understand the problem correctly, the answer should be

the fibonacci numbers

which can be found by writing a recursive definition for the problem.
 IP Logged
BNC
Uberpuzzler

Gender:
Posts: 1732
 Re: New puzzle: Parking Lot   « Reply #5 on: Feb 5th, 2003, 5:05am » Quote Modify

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

For completeness sake, here is a proof:

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

 IP Logged