Is there a way to do this without brute force ?

  • Thread starter Jamin2112
  • Start date
  • #1
986
9
Is there a way to do this without "brute force"?

Homework Statement



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?

Homework Equations



n choose k
n factorial

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:

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,836
251
Hi Jamin2112! :smile:

Hint: call the first digit "a" …

what is the probability that the second digit is not adjacent ? :wink:
 
  • #3
986
9
Hi Jamin2112! :smile:

Hint: call the first digit "a" …

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

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
I like Serena
Homework Helper
6,579
176
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
Dick
Science Advisor
Homework Helper
26,263
619
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.

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:
  • #6
I like Serena
Homework Helper
6,579
176
Unfortunately that's not true. There are fewer arrangements starting with 1 than with 5.

Huh? :confused:

I was wondering whether the digits had to be ascending or not.
But that was clarified indirectly in post #3.
 
  • #7
Dick
Science Advisor
Homework Helper
26,263
619
Huh? :confused:

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

I was assuming you just have to avoid sequential pairs. Work it out. I spelled the difference out for the N=4 case.
 
  • #8
Bacle2
Science Advisor
1,089
10
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
Dick
Science Advisor
Homework Helper
26,263
619
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)

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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
36,389
6,933
I was assuming you just have to avoid sequential pairs. Work it out. I spelled the difference out for the N=4 case.

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
Dick
Science Advisor
Homework Helper
26,263
619
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.

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:
  • #12
986
9
"Brute force" gave me an answer of 7/60. That correct?
 
  • #13
Bacle2
Science Advisor
1,089
10
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
Dick
Science Advisor
Homework Helper
26,263
619
"Brute force" gave me an answer of 7/60. That correct?

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
986
9
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.

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
Dick
Science Advisor
Homework Helper
26,263
619
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.

I agree.
 
  • #17
Bacle2
Science Advisor
1,089
10
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.
 

Related Threads on Is there a way to do this without brute force ?

Replies
4
Views
1K
Replies
5
Views
1K
Replies
2
Views
2K
Replies
25
Views
3K
Replies
11
Views
1K
Replies
6
Views
1K
Replies
6
Views
1K
Replies
1
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
7
Views
2K
Top