Help with some math.

thestuff

thestuff

CAGiversary!
Feedback
11 (100%)
Hey guys, I need some help with my descrete math homework.

The question is...

How many integers between 1500 and 8000 (inclusive) contain no repeated digits?

Now, I know its possible to go through and count each one, but the answer is not the point. I need to figure out how it is done. There is a trick of some kind that I am finding difficult to pinpoint. Any help would be very appreciated.

Also, I guess some background may be helpful. We are in the middle of a shallow study of combinatorics. This includes combinations and permeatations. I just cant figure out how in the world this can be done simplisticly... Thanks!
 
Code: 
class perm{
	public static void main(String args[]){
		int bottom = 1500;
		int top = 8000;
		
		int digit1, digit2, digit3, digit4;	
		
		int temp;
		int cur;
		int total=0;
		int totalc=0;
		
		for (int j=bottom; j
 
[quote name='int80h']
Code: 
class perm{
	public static void main(String args[]){
		int bottom = 1500;
		int top = 8000;
		
		int digit1, digit2, digit3, digit4;	
		
		int temp;
		int cur;
		int total=0;
		int totalc=0;
		
		for (int j=bottom; j
 
No, I understand it completly. I am a comp sci major. But, its not really something I can write down. This is a math class, not a programming class. Thank you for the attempt though.

This is where the problem is. I realize that I could write a program or count, but I need a more... intuitive solution...

Any other ideas?
 
[quote name='thestuff']Hey guys, I need some help with my descrete math homework.

The question is...

How many integers between 1500 and 8000 (inclusive) contain no repeated digits?

Now, I know its possible to go through and count each one, but the answer is not the point. I need to figure out how it is done. There is a trick of some kind that I am finding difficult to pinpoint. Any help would be very appreciated.

Also, I guess some background may be helpful. We are in the middle of a shallow study of combinatorics. This includes combinations and permeatations. I just cant figure out how in the world this can be done simplisticly... Thanks![/quote]

The first thing you should ever do is scale down the problem, and draw it out. Discrete Math is more logic than actual computation, and when I took it it always helped to draw out the problem and try to see what was going on. Same thing for probability. Draw it out, look for patterns, and hope for the best.
 
There are 504 non-repeating integers for every 1000 number; ie: 2000-2999, 3000-3999, etc. For 1500-1999, there are 5 sets of one hundred numbers (15XX, 16XX, 17XX, 18XX, 19XX), every one hundred number in this 1500-1999 block has 56 non-repeating integers. So 56x5=280. Then there are six one-thousand sets of numbers, 2000, 3000, 4000, 5000, 6000, 7000. So 6x504=3024. 3024+280 = 3304.

To find 504 integers per one thousand block, only 9 one-hundred sets of numbers can be counted as they're non-repeating:

20XX
21XX
23XX
24XX
25XX
26XX
27XX
28XX
29XX

And within one set of any of those listed, you can only have 8 non-repeating subset:

230X
231X
234X
235X
236X
237X
238X
239X

Within one of those subset, you can only have 7 non-repeating sub-subsets:

2310
2314
2315
2316
2317
2318
2319

So now you take the numbers I've listed and multiply, 9x8x7=504.


Someone write a cliff note. :D
 
How many integers between 1500 and 8000 (inclusive) contain no repeated digits?

Let's see. How many integers between 2000 and 2999 contain to repeated digits?
The first digit is 2. You get 9 choices for the 2nd digit, 8 for the 3rd, and 7 for the 4th, so 9*8*7 numbers between 2000 and 2999.
Same goes for the 3 thousands, 4, 5, 6, and 7 thousands. So altogether you have 6*9*8*7 between 2000 and 7999 (8000 obviously doesn't count.

Between 1500 and 1599 you have 8*7 possiblities. Same for the 1600s, 1700s, 1800s and 1900s.
Altogether between 1500 and 1999 you have 5*8*7
Your grand total would be 6*9*8*7 + 5*8*7
 
[quote name='thestuff']No, I understand it completly. I am a comp sci major. But, its not really something I can write down. This is a math class, not a programming class. Thank you for the attempt though.

This is where the problem is. I realize that I could write a program or count, but I need a more... intuitive solution...

Any other ideas?[/quote]

I figured you were a comp sci major, taking discrete and all, I just didn't think it would meet your needs. Looks like SOSTrooper handled that though.
 
Hey guys, thanks a lot. This should work!

I knew it was somthing along these lines... I was just having problems.
Ha.

Anyways, thanks everybody!
 
You must log in or register to reply here.
bread's done
Back
Top