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

Combinatorics problem

  1. Oct 21, 2012 #1
    While bored in class one day I started to come up with a problem that I kept making more difficult as I solved each step. The overall setup goes like this. Picture an alarm clock or a scoreboard clock. There are 5 sections of the displayed time. 4 places are for where numbers go and the middle, and last place, is for the colon. Each number slot contains 7 elements/segments that allows it to create any of the 10 digits. I also divided the colon into 2 pieces. All 30 elements/segments work independently of each other. For each problem I don't consider anything without a lit colon to be a normal time. Lastly by displayed I mean lit and by not displayed I mean it's turned off.


    To give you a sense of how to attack problem 4 I'll show you each problem that led to me to it. I don't want an answer regarding any problem other than 4 because I've already solved the other ones.

    This forum seems like a group of smart people so I came here with my challenge first.

    1st problem. Given that the probability a segment being lit or not lit is fair what is the probability that a normal time is displayed. By normal time I mean a mod 12 time, not military time, so anywhere from 1 o'clock to 12:59.

    This didn't take me too long to do

    2nd problem. Now consider that a segment has, instead of 2 like the last problem, 3 settings. The settings are off, on-low, on-high. So a segment that is on-low will be dimmer than one on-high. The probability is still fair for all 3. What is the probability that a normal time is displayed? What is the probability that a normal time is displayed and all the displayed segments are on the same setting?

    This took me a bit longer but it's really not that tough to get

    3rd problem. Now consider that a segment has, instead of 2 or 3 like the last problems, n settings. The settings are off, on-1, on-2,...,on-(n-1) where on-k is dimmer than on-j if k<j. What is the probability that a normal time displays? What is the probability that a normal time displays and each displayed segment is lit on the same setting?

    This one I had to finish outside of class

    4th problem. We will use the same setup as problem 3. Let's say that if a segment is turned off that its value is 0 and if it's on-1 its value is 1 and if it's on-i its value is i. What is the probability that a normal time displays AND its total value is λ for any integer valued λ.

    I've done some work on this one but overall it seems beyond me.


    If there's anything missing or wrong please tell me and I will fix it.

    Thanks so much and good luck.
     
    Last edited: Oct 21, 2012
  2. jcsd
  3. Oct 21, 2012 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Re: A Problem I Bet You Can't Solve

    "normal time displayed" means "all segments which are at least on-1 together form a valid time"?

    I think it will be messy case-work (or something for a computer), but here are intermediate steps which can be useful:
    All slots are independent of each other, so we can calculate the probability to get number "x" with value λ as ##P(\lambda_i,x_i)=P(\lambda,x)##. This is related to some binomial coefficients. The colon gets its own function, which is easy to calculate.

    With those coefficients, it is possible to calculate the total result: The colon has to be active, the first digit has to be 0 or 1, if the first digit is 1 the second digit has to be 0 to 2, if the first digit is 0 the second digit has to be 1 to 9 (right?). The third digit has to be 0-5, the last digit has to be some number. That gives a big sum over various ##P(\lambda,x)## and a very long (in terms of expression size) result.
     
  4. Oct 21, 2012 #3
    Re: A Problem I Bet You Can't Solve

    Yes, that definition is fine for normal time.

    In this case, I guess I should have stated that instead of 09:00 being displayed 9:00 should be displayed. In other words the leading slot should be left off for 1-9. In the case of your λ I'm not quite sure it would work like that, unless I am not understanding exactly what you did (which is very possible, haha). But here it seems your λ is being used to represent the value of the digit in a single slot being displayed. What I am looking for is a λ that represents the total value of the time displayed. Therefore, it seems to me at least, that you can't restrict the possible individual values of each digit and the colon since there are many combinations of the same times with different values, different times with different values, and same times with same values, and different times with same values.

    If what I said made any sense then how would you then go about it? If it didn't make any sense then can you possibly explain your steps in more detail so I can follow easier?
     
  5. Oct 22, 2012 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Re: A Problem I Bet You Can't Solve

    The total λ is just the sum of the individual λi, so you have to sum over all possible combinations of λi for the individual digits.

    Another option would be a sum over all possible displays (12*60): For each one, you can determine the number of active elements (and the probability that those elements are active and the others are not). All elements need a "weight" of at least 1, so you have λ-"number of active elements" left to distribute over all "number of active elements" elements. There is a formula to find the number of possible distributions.
    You end up with a sum of 720 components.

    Ok, then you need an additional ##P(0,empty)=1/n^7## and ##P(\lambda_i,empty)=0## for lambda>0. No problem.

    Oh, and I assume that "fair" means "all options have the same probability".
     
  6. Oct 24, 2012 #5
    Long story short I'm looking for an answer in the form of an equation of two variables, f(λ,n) where n is the number of settings and λ is the total value. This equation should output the probability needed.
     
  7. Oct 24, 2012 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    ... and I described a method to get it.

    More specific: All valid times are mutually exclusive - the clock cannot display two different times at the same time (:D). Therefore, the total probability f(λ,n) is just the sum of all individual minutes.

    Let s(t) be the number of active elements at time t (t in minutes from " 0:00" to "12:59" or whatever is used as display). As an example, s("11:23") = 2+2+2+5+5=16.
    30-s(t) is the number of inactive elements.
    Elements are active with a probability of (n-1)/n and inactive with probability 1/n.

    To display some specific time t, the probability that the correct s(t) elements are active is $$P(t,n)=\frac{(n-1)^{s(t)}}{n^{30}}$$

    There are ##(n-1)^{s(t)}## possible ways for those elements to be active (n-1 for each).
    How many ways are there to get a sum of λ? Each element has to be at least 1-on, so we can distribute λ-s(t) freely over s(t) elements. This gives (λ-1 choose s(t)-1) options.

    Therefore, we get the conditional probability:
    $$P(t,n,\lambda | t,n) = {\lambda -1 \choose s(t)-1} \frac{1}{(n-1)^{s(t)}}$$
    (the binomial coefficient is set to 0 if s(t)>λ)
    Combining both gives
    $$P(t,n,\lambda) = {\lambda -1 \choose s(t)-1} \frac{1}{n^{30}}$$

    Your f(λ,n) is now simply the sum over all times:

    $$f(\lambda,n)=\sum_t P(t,n,\lambda) = \frac{1}{n^{30}} \sum_t {\lambda -1 \choose s(t)-1}$$
    If you calculate s(t) for each time, you can resolve the sum into ~20 individual summands (one for each possible value of s(t).
     
  8. Oct 26, 2012 #7
    now let's say all the probabilities aren't necessarily the same
     
  9. Oct 26, 2012 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Then you have to separate those different options, too.
    I don't see the point, feel free to find expressions for that.
     
  10. Oct 26, 2012 #9
    No thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics problem
  1. Combinatorics problem (Replies: 6)

  2. Combinatorics problem (Replies: 3)

  3. Combinatorics problem (Replies: 4)

Loading...