Author 
Topic: Parking Lot (Read 4266 times) 

Garzahd
Junior Member
Gender:
Posts: 130


Parking Lot
« on: Jan 29^{th}, 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 23^{rd}, 2003, 8:11pm by Icarus » 
IP Logged 



Phil
Newbie
Posts: 38


Re: New puzzle: Parking Lot
« Reply #1 on: Jan 29^{th}, 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 29^{th}, 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 parallelparking spaces).


IP Logged 



Garzahd
Junior Member
Gender:
Posts: 130


Re: New puzzle: Parking Lot
« Reply #3 on: Jan 29^{th}, 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 onedimensional.


IP Logged 



ragna
Guest


Re: New puzzle: Parking Lot
« Reply #4 on: Feb 4^{th}, 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 5^{th}, 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: CarCar or Bus => f(2)=2 For N>2: you may: 1. Place a car in the first location. Then you have f(N1) options to complete the location. 2. Place a bus in the first (and second) location. Then you have f(N2) options to complete the location. In total, you have f(N) = f(N1)+f(N2), and f(1)=1, f(2)=2


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



