How many combinations? (High school math problem)

[YouAreAwesome]

Summary:: Year 11 Extension 1 Math problem (Australia)

How many combinations can be made from a 4 digit pin code if we can only use two numbers to form our pin code, and we MUST use 2 distinct numbers. E.g. 1112, 4334, 9944, 3232. But NOT 1111, 2113, 0992 etc. We're using the numbers 0-9 and 0001 is the first combination.

Thanks

 

[Office_Shredder]

What have you done so far to attempt the problem?

 

[YouAreAwesome]

What have you done so far to attempt the problem?

Well, I've been thinking about it for a day and simplifying the problem to 3 digits pin code with only 4 numbers to choose from. But straight after posting this I think I figured out the answer. Maybe you can confirm for me?

For the 4 digit pincode the first number is arbitrary, and I'll call it x. After it is chosen, the second number can only be x or some other number, I'll call it y. The third can also only be x or y. And the fourth also. So this makes 2*2*2=8 combinations. However, we have to discount xxxx so we have 2^3-1 combinations. And now we note that x can be any of 10 numbers, 0-9. y can be only 9 numbers because we remove the number, x.

Putting it together we get 10*9*(2*3-1)=630.

Is this correct? And is there a different way to solve this that is simpler/easier?

Thanks

 

[Delta2]

I did the problem with another approach and i also get 630.
Will post my approach soon..

Suppose we have choose the 2 numbers (say 0 and 1). Then the possible codes are $2^4$. But we must remove 0000 and 1111 so they actually are $2^4-2=14$.

Now the possible ways from which we can choose two numbers from ten numbers are $10C2=\frac{10!}{2!8!}=45$

Hence by the multiplicative principle the total number of codes are 45x14=630.

 

[YouAreAwesome]

I did the problem with another approach and i also get 630.
Will post my approach soon

Great, I would appreciate that, thanks

 

[Delta2]

Great, I would appreciate that, thanks

I updated my previous post.

 

[YouAreAwesome]

I did the problem with another approach and i also get 630.
Will post my approach soon..

Suppose we have choose the 2 numbers (say 0 and 1). Then the possible codes are $2^4$. But we must remove 0000 and 1111 so they actually are $2^4-2=14$.

Now the possible ways from which we can choose two numbers from ten numbers are $10C2=\frac{10!}{2!8!}=45$

Hence by the multiplicative principle the total number of codes are 45x14=630.

Thank you, this makes a lot of sense, disappointed I didn't see this solution. Cheers

 

[Delta2]

Thank you, this makes a lot of sense, disappointed I didn't see this solution. Cheers

No need to be disappointed, I didn't see your solution either (which seems correct too). We aren't Gods we just can't see every possible solution to a problem.

 

[mjc123]

On a point of terminology, you appear to be asking about permutations, not combinations. For example, 0001, 0010, 0100 and 1000 are different permutations (where the order matters), but the same combination (three 0s and one 1, irrespective of the order). By my reckoning, there are 135 possible combinations:
90 of the type 0001, each with 4 permutations (360 permutations)
45 of the type 0011, each with 6 permutations (270 permutations). Total 630 permutations.

 

[phinds]

Now the possible ways from which we can choose two numbers from ten numbers are $10C2=\frac{10!}{2!8!}=45$

Since it has been about 60 years since I took what was in my day called "finite math" (which in my high school included little more than combinations and permutations), I assume I have something wrong, but I just can't figure out why this is 45 and not 90.

I mean, you have 10 ways to choose the first number and then 9 ways to choose the second one, so I get 90 (and thus 1,260 as the answer to the problem). What am I missing?

 

[Delta2]

Since it has been about 60 years since I took what was in my day called "finite math" (which in my high school included little more than combinations and permutations), I assume I have something wrong, but I just can't figure out why this is 45 and not 90.

I mean, you have 10 ways to choose the first number and then 9 ways to choose the second one, so I get 90 (and thus 1,260 as the answer to the problem). What am I missing?

Well I took only discrete math and combinatorial analysis during my undergraduate studies, I am not much better on this.
I think what you doing wrong is that you double counting the pairs of numbers for example the pair {9,1} you count it two times (as 91 and as 19) while you should count it only once. So you have to divide 90 by 2.

 

[phinds]

Well I took only discrete math and combinatorial analysis during my undergraduate studies, I am not much better on this.
I think what you doing wrong is that you double counting the pairs of numbers for example the pair {9,1} you count it two times (as 91 and as 19) while you should count it only once. So you have to divide 90 by 2.

But a PIN of 91 is different than a PIN of 19, so I'm still puzzled.

 

[Delta2]

But a PIN of 91 is different than a PIN of 19, so I'm still puzzled.

You have to count the pair of numbers as unordered pairs (so (9,1) is the same as (1,9)) not as an ordered pair or as a pin/number. Because you take into account the order when you count the $2^4-2$ pins

 

[phinds]

You have to count the pair of numbers as unordered pairs (so (9,1) is the same as (1,9)) not as an ordered pair or as a pin/number. Because you count the order when you count the $2^4-2$ pins

I'm still not getting it. Must be particularly dense this morning.

In the 14, ABAB, for example, is different than BABA and similarly AAAB is different than BBBA so I don't see how ordering comes into it.

 

[ergospherical]

@phinds there are ${10 \choose 2} = 45$ ways to choose two distinct digits irrespective of internal ordering, say $\{ i,j \}$, then there are $2^4 - 2 = 14$ distinct permutations of those digits such that each appears at least once.

You could try writing them out. There'll be four with $3$ $i$s and $1$ $j$, six with $2$ $i$s and $2$ $j$s and four with $1$ $i$ and $3$ $j$s.

 

[Delta2]

Sorry I find it hard to explain it further, I am not expert in combinatorics, it's not my favorite area of mathematics.

 

[phinds]

@phinds there are ${10 \choose 2} = 45$ ways to choose two distinct digits irrespective of internal ordering,

But this is what I'm not getting. WHY is internal ordering NOT important?
AB is not the same PIN as BA. Since you're all saying the same thing, I continue to believe I'm wrong, but I'm struggling to see why.

 

[ergospherical]

First off: a pin has 4 digits, so neither AB or BA are a pin.

There's two steps to constructing a pin. First, you have a bag containing ten chips, each showing a digit from 0 to 9 on it. You reach into the bag and withdraw two chips - you've now selected one particular combination $\{i,j \}$ of digits [order is not important at this stage].

Then, you write down as many distinct permutations of those two digits as you can, ensuring that each digit appears at least once. To each combination $\{ i,j \}$ corresponds $14$ such permutations.

 

[phinds]

There's two steps to constructing a pin. First, you have a bag containing ten chips, each showing a digit from 0 to 9 on it. You reach into the bag and withdraw two chips - you've now selected one particular combination of digits. [Order is not important at this stage].

Then, you write down as many distinct permutations of those two digits as you can, ensuring that each digit appears at least once. To each combination $\{ i,j \}$ corresponds $14$ such permutations.

I GET that part, what I don't get is why you multiply the 14 by 45 instead of 90. I've never had a problem w/ the 14, that part is completely clear.

What I continue to not get explained to me is how you can choose 2 different digits and not get 10*9 = 90 different ways of doing that.

 

[ergospherical]

That is precisely the distinction between a combination and a permutation; ${10 \choose 2} = 45$ however $^{10}P_2 = 90$.

In the context of the first step, it is only of interest to obtain an unordered combination $\{ i,j \}$ of two digits, as opposed to an ordered permutation $(i,j)$ of two digits. As @Delta2 mentioned earlier, the ordering of the digits in the final pin is accounted for in the second step.

 

[phinds]

... the ordering of the digits in the final pin is accounted for in the second step.

HAH ! Finally, I get it. Thanks. I was not properly considering both steps at the same time but was insisting on keeping them separate.