Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete mathematics question

  1. Sep 26, 2011 #1
    1. The problem statement, all variables and given/known data

    There are 17 street lamps along a straight street. In order to save electricity and not affect the regular use at the same time, we can shut down 5 of these lamps. But we cannot turn off a lamp at either end of the street, and we cannot turn off a lamp adjacent to a lamp that is already off. Under such conditions, in how many ways can we turn off 5 lamps?

    2. Relevant equations

    3. The attempt at a solution

    I've looked at this question a few times now and I still don't even know where to begin. Any help would be highly appreciated.
  2. jcsd
  3. Sep 28, 2011 #2

    rude man

    User Avatar
    Homework Helper
    Gold Member

    Hmm .. I would start as follows:

    First, forget about the two end-lights. They're always on. That leaves 15 lights to worry about.

    How many ways can you arrange 15 distinguishable things taken 5 at a time?

    Then, how many states are prohibited by the "no 2 adjacent lights off" rule?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook