OSDev.org

Posted: **Sat Jan 21, 2006 12:06 pm**

There are 22 pegs on a wall, You are given infinite number of hangers of 2 types
First type--> requires 1 peg
Second type-->requires 2 pegs(each peg beside the other)

In how many different ways can you occupy all the pegs?
(No pegs should be left unoccupied)

Any1 got any idea how tht^ is done? ???

Posted: **Sat Jan 21, 2006 12:57 pm**

rich_m wrote: There are 22 pegs on a wall, You are given infinite number of hangers of 2 types
First type--> requires 1 peg
Second type-->requires 2 pegs(each peg beside the other)

In how many different ways can you occupy all the pegs?

Any1 got any idea how tht^ is done? ???

Requires one peg: Each can either contain a hanger or not contain a hanger. So, that's 2^22 == 4194304 possible ways.

Requires two pegs: That's harder. From the start you can either hang one on and skip two pegs, or you can not hang one there and skip one peg. So, for length(N) the options are 1*length(N-1) (for not hanging one) + 1*length(N-2) (for hanging one). That's identical to the Fibonacci series, so you take the 22nd number (0,1 pegs correspond to 1 option, 2 pegs has 2 options, 3 pegs has 3 options, 4 pegs has 5 options etc.) and that is:

[(0,1),(1,1),(2,2),(3,3),(4,5),(5,8),(6,13),(7,21),
(8,34),(9,55),(10,89),(11,144),(12,233),(13,377),
(14,610),(15,987),(16,1597),(17,2584),(18,4181),
(19,6765),(20,10946),(21,17711),(22,28657),
(23,46368),(24,75025),(25,121393),(26,196418),
(27,317811),(28,514229),(29,832040)]

So, that's 28657. No, I didn't calculate that row myself, I let haskell do it for me:

Code: Select all

numfibrow :: [(Int, Integer)]
numfibrow = zip [0..] fibrow

fibrow :: [Integer]
fibrow = 1 : 1 : zipWith (+) fibrow (tail fibrow)

Posted: **Sat Jan 21, 2006 1:12 pm**

That sounds suspiciously like a homework question...

Posted: **Sat Jan 21, 2006 1:55 pm**

no i re-made a puzzle, just wanna make sure its not re-made with dangerous bugs. ;D

Posted: **Sat Jan 21, 2006 2:15 pm**

rich_m wrote: no i re-made a puzzle, just wanna make sure its not re-made with dangerous bugs. ;D

Was my solution sort of helpful?

Posted: **Sat Jan 21, 2006 8:24 pm**

Was my solution sort of helpful?

tanx a lot for tht solution,,i'm still trying to understand the second part, anyway heres the original puzzle

There are 22 steps. A person is starting from the bottom climbing to the top. A person can climb, at a time, one or two steps. In how many ways can he climb the steps and reach the top?

Posted: **Sun Jan 22, 2006 6:06 pm**

Candy wrote: Requires one peg: Each can either contain a hanger or not contain a hanger. So, that's 2^22 == 4194304 possible ways.
....................

None of the pegs should remain empty.

Posted: **Mon Jan 23, 2006 12:51 am**

rich_m wrote:
Candy wrote: Requires one peg: Each can either contain a hanger or not contain a hanger. So, that's 2^22 == 4194304 possible ways.
....................
None of the pegs should remain empty.

Even though I didn't answer your original question, the answer is still in there.

Posted: **Mon Jan 23, 2006 5:56 am**

rich_m wrote: In how many different ways can you occupy all the pegs?

42

(sorry. couldn't resist)

Posted: **Thu Jan 26, 2006 7:30 am**

Candy wrote:......................................
Requires two pegs: That's harder. From the start you can either hang one on and skip two pegs, or you can not hang one there and skip one peg. So, for length(N) the options are 1*length(N-1) (for not hanging one) + 1*length(N-2) (for hanging one). That's identical to the Fibonacci series, so you take the 22nd number (0,1 pegs correspond to 1 option, 2 pegs has 2 options, 3 pegs has 3 options, 4 pegs has 5 options etc.) and that is:

[(0,1),(1,1),(2,2),(3,3),(4,5),(5,8),(6,13),(7,21),
(8,34),(9,55),(10,89),(11,144),(12,233),(13,377),
(14,610),(15,987),(16,1597),(17,2584),(18,4181),
(19,6765),(20,10946),(21,17711),(22,28657),
(23,46368),(24,75025),(25,121393),(26,196418),
(27,317811),(28,514229),(29,832040)]

So, that's 28657. No, I didn't calculate that row myself, I let haskell do it for me:
Code: Select all
numfibrow :: [(Int, Integer)]
numfibrow = zip [0..] fibrow

fibrow :: [Integer]
fibrow = 1 : 1 : zipWith (+) fibrow (tail fibrow)

I'm not sure if i understood that right, but this is my solution to the puzzle.
Answer:: There are 2048 ways to place those two types of hangers on 22 nails.

Solution:: We need consider only the number of ways the hanger type-II can be placed on the nails.
lets consider * = 2nails(tht are placed beside each other)
therefore 22 nails will be

* * * * * * * * * * * ( 11 *'s) = 11 X 2 = 22nails

let 0 and 1 represent if a * is occupied or not.

so the different possibilities are

* * * * * * * * * * *
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1 1
. .
. .
. .
1 1 1 1 1 1 1 1 1 1 1

which is equal to 2^11=2048

So actually '0' reprsents that theres a type-I hanger on the nails.
And '1' represents tht a type-II.

Posted: **Thu Jan 26, 2006 8:09 am**

rich_m wrote: I'm not sure if i understood that right, but this is my solution to the puzzle.
Answer:: There are 2048 ways to place those two types of hangers on 22 nails.

Solution:: We need consider only the number of ways the hanger type-II can be placed on the nails.
lets consider * = 2nails(tht are placed beside each other)
therefore 22 nails will be
...
which is equal to 2^11=2048

So actually '0' reprsents that theres a type-I hanger on the nails.
And '1' represents tht a type-II.

Simplify the problem first:
From the start. We have 0 pins. How many ways can you hang hangers on them? Well, 1 way, not hanging anything.

We have 1 pin. How many ways can you hang them? 1 way, just the 1-pin hanger.

We have 2 pins. How many ways can you hang them? 2 ways, either by hanging one 2-pin hanger or two 1-pin hangers.
Answer: 2 (= number for one pin + number for 0 pin)
Example:
1 1
2 2

we have 3 pins and both types of hangers, infinitely many. How many ways can you hang them?
type 1 needs 1 pin, type 2 needs 2 pins.

Answer: 3 (= number for 2 pins + number for one pin)

From the two-pin solution you get:
1 1 1
1 2 2

From the one-pin solution you get:
2 2 1

How many ways can you place them on 4 pins? Answer: 5 ways. Your previous answer: 4.

From the 3-pin solution you get:
1 1 1 1
1 1 2 2
1 2 2 1 -> you missed this one, yet it's entirely valid.

From the 2-pin solution you get:
2 2 1 1
2 2 2 2

5 pins? Well... each way you can make one with 4 long, plus a 1 at the start, plus each way you can make a 3-long with two 2's at the start.

So:

From the four-pin solution you get:
1 1 1 1 1
1 1 1 2 2
1 1 2 2 1
1 2 2 1 1
1 2 2 2 2

From the three-pin solution you get:
2 2 1 1 1
2 2 1 2 2
2 2 2 2 1

These are all. How many are there for 6 pins? Well, if you hang hanger type 2 first, you get the number of options for 4 pins, plus those for hanging type 1 first, which is the unmber for 5 pins. So, 5 + 8 = 13.

Generalizing from there, hangers(pins) = H(P) = H(P-1) + H(P-2). Type this out (or work it out yourself) to get the above numbers.

The series is known as the fibonacci series.

Posted: **Thu Jan 26, 2006 9:19 am**

ok i get it now, my solution is completly wrong, wont work for even 4 pegs.

OSDev.org

Puzzle on combinations

Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations

Re:Puzzle on combinations