Author |
Topic: Parking Lot (Read 4305 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 |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print