wu :: forums
wu :: forums - Parking Lot

Welcome, Guest. Please Login or Register.
Apr 20th, 2024, 1:47pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: william wu, towr, ThudnBlunder, Icarus, Eigenray, SMQ, Grimbal)
   Parking Lot
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Parking Lot  (Read 4266 times)
Garzahd
Junior Member
**





    mlahut


Gender: male
Posts: 130
Parking Lot  
« on: Jan 29th, 2003, 12:37am »
Quote Quote Modify 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 Quote Modify 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
***





   
WWW Email

Gender: male
Posts: 288
Re: New puzzle: Parking Lot  
« Reply #2 on: Jan 29th, 2003, 11:03am »
Quote Quote Modify 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
**





    mlahut


Gender: male
Posts: 130
Re: New puzzle: Parking Lot  
« Reply #3 on: Jan 29th, 2003, 2:46pm »
Quote Quote Modify 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

Email

Re: New puzzle: Parking Lot  
« Reply #4 on: Feb 4th, 2003, 11:02pm »
Quote Quote Modify Modify Remove 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: male
Posts: 1732
Re: New puzzle: Parking Lot  
« Reply #5 on: Feb 5th, 2003, 5:05am »
Quote Quote Modify 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]
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board