1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is there a way to do this without brute force ?

  1. Mar 17, 2013 #1
    Is there a way to do this without "brute force"?

    1. The problem statement, all variables and given/known data

    A number is chosen at random from among all 5-digit numbers containing exactly one of each of the digits 1, 2, 3, 4, 5. Find the probability that no two adjacent digits in the number are consecutive integers?

    2. Relevant equations

    n choose k
    n factorial

    3. The attempt at a solution

    So I know there are 5!=120 different combos. I need to figure out how many have the property that there are no two adjacent consecutive numbers (i.e. 13524 would work but 12534 wouldn't). Should I break it off into cases where 1 is the first digit, 2 is the second, etc.? That would be a brute force approach. Is there an easier way to think about this?
     
    Last edited: Mar 17, 2013
  2. jcsd
  3. Mar 17, 2013 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Jamin2112! :smile:

    Hint: call the first digit "a" …

    what is the probability that the second digit is not adjacent ? :wink:
     
  4. Mar 17, 2013 #3
    Depends. If a is 1 or 5, then the probability is 3/4. If a is 2, 3, or 4, then the probability is 1/2.
     
  5. Mar 17, 2013 #4

    I like Serena

    User Avatar
    Homework Helper

    I'd suggest a "smart" brute force approach.
    There are not that many combinations allowed but too many exceptions to easily generalize.
    With "smart" I mean for instance that after you've done the numbers starting with 1, you already know that there are just as many numbers starting with 5.
     
  6. Mar 17, 2013 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Unfortunately that's not true. There are fewer arrangements starting with 1 than with 5.

    I would suggest starting with the N=3 case. So the digits are 1,2,3. Call F(N) the number of allowed sequences. Then F(3) is easy. It's just 3, [1,3,2], [2,1,3] and [3,1,2]. Let's also call F(N,k) the number of sequences of N digits starting with digit k. Now try to count the N=4 case. If the first digit is 1, then the rest are 2,3,4. Those are sequential so you can arrange them in F(3)=3 ways, but you can't allow the one starting with 2 so there are 2. So F(4,1)=2. So that's F(3)-1. But if you start with 4 then any arrangement of 1,2,3 is allowed after that. So F(4,4)=F(3)=3. Now if you can count F(4,2) and F(4,3) then you've wrapped up F(4).

    Think inductively.
     
    Last edited: Mar 17, 2013
  7. Mar 17, 2013 #6

    I like Serena

    User Avatar
    Homework Helper

    Huh? :confused:

    I was wondering whether the digits had to be ascending or not.
    But that was clarified indirectly in post #3.
     
  8. Mar 17, 2013 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I was assuming you just have to avoid sequential pairs. Work it out. I spelled the difference out for the N=4 case.
     
  9. Mar 17, 2013 #8

    Bacle2

    User Avatar
    Science Advisor

    How about inclusion/exclusion? first with consecutive pairs, then with triples,

    etc.

    Still, sorry to tell you, Jamin, you cannot get any arrangement with the numbers

    in your name (Sorry, I'm too tired for a quality joke)
     
  10. Mar 17, 2013 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, joke's little poor. Did you manage to work it out that way? I do know that the number of admissible orderings depends on the starting number. If it's 1 then it's less than all of the other possibilities. It's not that symmetric. The rest of the leading digits have the same number of orderings. That is a little counterintuitive. And you can figure out those numbers from the N-1 case. This seems a little elaborate. If you've got a simpler way I'd love to hear about it.
     
  11. Mar 17, 2013 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    The way I read the question, 54... is not allowed, so number starting with 5 equals number starting with 1. Likewise 2 and 4.
    Not sure if inclusion/exclusion is quicker, but I think you can be more confident of getting it right that way. Maybe do both.
     
  12. Mar 17, 2013 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Oh, heck. I was so obsessed with what I doing I failed to read it correctly. It's "adjacent", not "sequential". If anybody wants the solution to a different harder problem. I've got it. Sorry all! In that case the number of orderings is small enough you can simply write them all out. That make "brute force" not that hard.
     
    Last edited: Mar 17, 2013
  13. Mar 18, 2013 #12
    "Brute force" gave me an answer of 7/60. That correct?
     
  14. Mar 18, 2013 #13

    Bacle2

    User Avatar
    Science Advisor

    You're right; you have only 120 possible arrangements to make it worthwhile , but

    it may be worthwhile for a general solution to the same problem for {1,2,...,n}.

    Sorry, I will be gone for a while now.
     
  15. Mar 18, 2013 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, there's only 14 orderings. If you misread it like I did (so "45" is disallowed but "54" is allowed) then the are 53. Which is getting large enough to make "by hand" counting a little iffy, at least if I'm the one doing it.
     
  16. Mar 18, 2013 #15
    I read it the way where the only possibilities would be

    13524
    14253
    24513
    24135
    25314
    31524
    31425
    35124
    35241
    41352
    42513
    42531
    53142
    52413,

    which is 14 out the possible 120.
     
  17. Mar 18, 2013 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I agree.
     
  18. Mar 21, 2013 #17

    Bacle2

    User Avatar
    Science Advisor

    O.K, I have this idea that may be simpler than brute force:

    We set up a graph G with vertices 1 thru n , and we draw an edge between

    i,j iff. |i-j|>1 . Then we do the adjacency matrix M_G for G, i.e., the (i,j)-entry is

    1 iff. there is an edge joining i with j, and is 0 otherwise.

    I first tried to use the fact that the (i,j)-entry of (M_G)^n is the number of paths of

    length n between vertex i and vertex j , BUT , the problem is that some of these paths

    may contain a cycle, i.e., some numbers are repeated, e.g., for n=5, 1,3,5,1,3,5 is a path

    of length 5 in the graph G for {1,2,..,5}. So what I now think is the

    answer is counting the number of spanning trees in the graph. There is a method for this,

    but I don't have much time now to try it, but I'll try it later.
     
  19. Mar 22, 2013 #18
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Is there a way to do this without brute force ?
Loading...