Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2010-10-26 08:28:48

jngrim
Member
Registered: 2010-10-26
Posts: 2

Combinatorics and unique pairs with a twist

Here is the problem  I have a dataset =1,2,3,4,5,6
If each number can only be used a maximum of 4 times, what is the maximum number of 2 digit and unique pairs can I create.
?
I know that if c(6,2)=6!/(2!(6-2)!)=15 but that would mean I used each number 5x's. after writing out the answer manually  I know that the the answer is 11.
I know I cant get the following numbers 16,26,36 45 which is 4, so 15-4=11 but I don't know how to maximize and exclude pairs with digits over 5. Can someone help me understand how to create this formula and create it?


Thanks alot

Offline

#2 2010-10-26 10:21:33

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinatorics and unique pairs with a twist

Hi jngrim;

I do not understand what you mean. Why cannot 16 be made? Do you add the numbers you pick? Do you put them side by side? Can you show me what you mean by making a number?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2010-10-26 11:19:28

jngrim
Member
Registered: 2010-10-26
Posts: 2

Re: Combinatorics and unique pairs with a twist

Sure,
My data set is really (1,1,1,1) (2,2,2,2) (3,3,3,3) (4,4,4,4) (5,5,5,5) (6,6,6,6)

So I must pair each number with another unique number...for example 12, 13, 14, 15, 16...however, I can use only 4 1s so I have to drop one number, so I just chose 16 but it doesn matter which one I drop so long as  use up to 4 numbers without replicating a pair.


 


for the purposes of this excerise  my numbers are
12,13,14,15
23,24,25
34,35
46
56

I used all the 1s in available 12,13,14,15
I used all the 2s available 12,23,24,25
I used all the 3s in 13,23,34,35
I used all the 4s, 14,24,34,46
I used 3 5s 15,25,56
I used 1 6 56

This gives me 11 unique numbers without using a number more than 4 times. but as you can see I there is no way to use the last 5 or the other 3 6s...

As I was saying I am understant that I how to get the 15 total unique combinations, but how can I calculate the 4 (5,6,6,6) not being used.
This would also happen on larger sets at well depending on teh number of datasets and how they were populated. There's go to be a formula.

Last edited by jngrim (2010-10-26 11:19:58)

Offline

#4 2010-10-27 09:49:13

Avon
Member
Registered: 2007-06-28
Posts: 80

Re: Combinatorics and unique pairs with a twist

Hi jngrim,

I think you are miscounting something here.
In your numbers
12,13,14,15
23,24,25
34,35
46
56
you have used four 5s, 15,25,35,56 and two 6s 46, 56 so you only have (6,6) left over.

You could change your numbers slightly to
12,13,14,16
23,25,26
34,35
45,46
56
and use all of the numbers available.
I could have constructed this by taking a set of pairs that uses each number once 15,24,36, and then taking all of the other pairs.

It's not entirely clear to me how you want to generalise this problem, but here is one way.
Let S(n,k) be the maximum size of a set of pairs of numbers 1,2,...,n with the property that each number is used at most k times.
It is easy to see that





all of which attain the upper bound

I'll have to think a little more to see if this upper bound can always be attained.

Offline

Board footer

Powered by FluxBB