# Is there a way to do this without brute force ?

1. Mar 17, 2013

### Jamin2112

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. Mar 17, 2013

### tiny-tim

Hi Jamin2112!

Hint: call the first digit "a" …

what is the probability that the second digit is not adjacent ?

3. Mar 17, 2013

### Jamin2112

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.

4. Mar 17, 2013

### I like Serena

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.

5. Mar 17, 2013

### Dick

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
6. Mar 17, 2013

### I like Serena

Huh?

I was wondering whether the digits had to be ascending or not.
But that was clarified indirectly in post #3.

7. Mar 17, 2013

### Dick

I was assuming you just have to avoid sequential pairs. Work it out. I spelled the difference out for the N=4 case.

8. Mar 17, 2013

### Bacle2

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)

9. Mar 17, 2013

### Dick

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.

10. Mar 17, 2013

### haruspex

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.

11. Mar 17, 2013

### Dick

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
12. Mar 18, 2013

### Jamin2112

"Brute force" gave me an answer of 7/60. That correct?

13. Mar 18, 2013

### Bacle2

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.

14. Mar 18, 2013

### Dick

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.

15. Mar 18, 2013

### Jamin2112

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.

16. Mar 18, 2013

### Dick

I agree.

17. Mar 21, 2013

### Bacle2

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.

18. Mar 22, 2013