Math Is Fun Forum

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

You are not logged in.

#1 2012-09-03 10:42:03

RichieSG
Member
Registered: 2012-09-03
Posts: 8

Combinations

I hope I can explain this is a way that you are able to understand my question...

If we have 8 numbers and select 4, what is the minimum number of times that just 3 numbers will appear in these combinations of 4 without repetition ?

I will add an example - if there are 5 numbers `1` `2` `3` `4` and `5` and 4 are selected, then what is the fewest number of combinations of 3 that cover all the combinations of 4 ?

As we know, there are 5 combinations of 4 for those 5 numbers, i.e. 1-2-3-4, 1-2-3-5, 1-2-4-5, 1-3-4-5 and 2-3-4-5 but only 3 combinations of 3 are required to show up in all of the combinations of 4. They are 1-2-3, 1-4-5 and 3-4-5.

1-2-3-4 contains 1-2-3
1-2-3-5 contains 1-2-3
1-2-4-5 contains 1-4-5
1-3-4-5 contains 1-4-5
2-3-4-5 contains 3-4-5

So, applying the same scenario but using 8 numbers, what is the fewest number of combinations of 3 that cover all the combinations of 4 ?

Does anyone know ?

If you can help us to solve this puzzle, then it would be great. I myself am not very mathematically minded so if you can help, could you also please show me those combinations like I have done above ?

The reason why I ask is so that I can give some help and encouragement to my son who is trying to work this out. I would like to help him but I cannot. dizzy

Thanks

Offline

#2 2012-09-03 19:29:51

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

Re: Combinations

Hi RichieSG;

I do not understand what you are asking. Can you provide a couple of more examples?


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 2012-09-04 05:32:18

RichieSG
Member
Registered: 2012-09-03
Posts: 8

Re: Combinations

My apologies, it is difficult to try and describe because I don't really understand myself. Let me try again...

Combinations of 4 will be referred to as "quad".
Combinations of 3 will be referred to as "triple".
A point of clarification, we are looking for combinations and not permutations.

There are five number 1, 2, 3, 4, and 5. As we know, there are 5 different quad combinations. They are 1-2-3-4, 1-2-3-5, 1-2-4-5, 1-3-4-5 and 2-3-4-5. We also know that there are 10 triples possible i.e. 1-2-3, 1-2-4, 1-2-5, 1-3-4, 1-3-5, 1-4-5, 2-3-4, 2-3-5, 2-4-5, 3-4-5.

What I am looking for, is to find the minimum number of triples where the numbers appear in the quads. For example the triple 1-2-3 appears in 1-2-3-4 and 1-2-3-5. This leaves 3 other quads which do not feature the triple 1-2-3. For those quads that remain 1-4-5 appears in 1-2-4-5 and 1-3-4-5 and 3-4-5 covers 2-3-4-5.

This means that the minimum of triples required to appear in all the quads is  3.

8 numbers produces 70 quads and 56 triples.

The triple 1-2-3 appears in 5 quads, i.e. 1-2-3-4, 1-2-3-5, 1-2-3-6 1-2-3-7 and 1-2-3-8, leaving the other 55 triples to cover the remaining 65 quads but not all are required.

My question is - "what is the minimum number of triples required in order to appear in quads which are made up from 8 numbers ?"


Another example

I have done some more research and found that for 6 numbers there are 15 quads and there are just 6 triples that appear in all of the quads.

1-2-3 appears in 1-2-3-4, 1-2-3-5 and 1-2-3-6.
Of the 12 quads remaining, 1-5-6 appears in 1-2-5-6, 1-3-5-6 and 1-3-5-6.
Of the 9 quads remaining, 3-4-5 appears in 1-3-4-5, 1-3-4-5 and 13-4-5.
This now leaves 6 quads for which 1-2-4 appears in 1-2-4-5 and 1-2-4-6, 3-4-6 which appears in 1-3-4-6 and 2-3-4-6 and finally 2-5-6 which appears in the last 2, 2-3-5-6 and 2-4-5-6.

Unless I am wrong, it means that the minimum number of triples needed to appear in all 15 quads, is 6.

I hope this makes my puzzle easier to understand. up

Last edited by RichieSG (2012-09-04 05:34:13)

Offline

#4 2012-09-04 05:47:27

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations

So, basically, you want to find out the minimum number of "triples" such that each "quad" that can be formed contains at least one of the "triples" chosen?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#5 2012-09-04 08:12:23

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

Re: Combinations

Hi RichieSG;

I think I understand the problem now well enough to try. Thanks for the explanation.


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

#6 2012-09-04 09:49:49

RichieSG
Member
Registered: 2012-09-03
Posts: 8

Re: Combinations

anonimnystefy wrote:

So, basically, you want to find out the minimum number of "triples" such that each "quad" that can be formed contains at least one of the "triples" chosen?

Yes, that is correct.

If we use the terminology that at the start, all quads are "open" then how many triples when applied one at a time, will "close" all 70 quads.

For example, we start with 70 quads and the first triple applied is 1-2-3, then this "closes" quads 1-2-3-4, 1-2-3-5, 1-2-3-6 1-2-3-7 and 1-2-3-8, There are now 65 quads left to be "closed" using the remaining triples.

What is the minimum number of triples required to close all 70 quads ?

As mentioned above, I have managed to work out the answer for 5 numbers and 6 numbers, but only by a process of elimination. I am sure that there is a mathematical way of calculating this. I have tried looking for a pattern but I could not find one, i.e. first 3 numbers, last 3 numbers, then first number with 4th and 5th numbers.

If there is a way, then we should be able to calculate 9, 10, 11 12 and so on.

Last edited by RichieSG (2012-09-04 09:52:11)

Offline

#7 2012-09-04 10:23:13

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations

You could try the "greedy" solution, that is, try to find a "triple" which closes the least possible number of already closed "quads". That should give you a good first approximation, if not the real answer.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#8 2012-09-04 10:35:45

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

Re: Combinations

Hi;

I am sure that there is a mathematical way of calculating this

Why are you sure? Why are you sure you will find a pattern? The stakes have gone up. If you are just interested in an answer then I can run it off by computer, maybe... A mathematical solution maybe much more difficult or may not be known or may not exist.

Do you know that there are many solutions?

Is also a solution to the {1,2,3,4,5} problem and there are others. This makes a math solution less likely.

For {1,2,3,4,5,6} you are correct it takes a minimum of 6 triples but there are 30 of them!

For {1,2,3,4,5,6,7} the smallest I found was 13 triples.

For {1,2,3,4,5,6,7,8} the smallest I found was 25 triples.


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

#9 2012-09-05 02:54:09

RichieSG
Member
Registered: 2012-09-03
Posts: 8

Re: Combinations

bobbym wrote:

Hi;

I am sure that there is a mathematical way of calculating this

Why are you sure? Why are you sure you will find a pattern? The stakes have gone up.

I think you have taken me too literally, perhaps it could be reworded as "I think that this can be worked out using a mathematical formula, I don't know if it could I am just assuming it could."

The reason why I asked the question is because I thought that there would be a way of calculating this and maybe someone knew.

If you are just interested in an answer then I can run it off by computer

Yes please.

I see you have put some answers down, thank you for this. I can't help feeling 25 is a bit high, i.e. not the minimum.

I have come up with a lower number. I believe that all 70 quads are covered with the following 22 triples...

These triples each cover 5 quads...
1    2    4
1    3    8
1    6    7
2    3    5
2    7    8
3    4    6
4    5    7
5    6    8
This means that there are just 30 quads remaining that are not "closed".
       
These triples each cover 3 of the remaining "open" quads...
1    4    8
1    5    6
1    5    7
2    3    6
2    4    6
3    4    7
This now leaves just 12 that are "open".

These triples each cover 2 quads...
2    5    8
3    5    8
5    6    7
6    7    8

Meaning that there are just 4 quads left which are covered by....
1    2    3
1    2    6
2    3    4
3    4    5

What I would like to know is - "is this the minimum ?".

Thanks for your input so far, it has helped me to understand a bit more.

Last edited by RichieSG (2012-09-05 03:00:32)

Offline

#10 2012-09-05 06:13:55

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

Re: Combinations

Hi;

Yes, that is a working 22. Unfortunately my program is a probabilistic one and is not guaranteed to find the shortest one. It will just find a decent answer.

What did you get for {1,2,3,4,5,6,7}?

Also if you have any other answers please provide them.


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

#11 2012-09-06 01:32:13

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations

Of course, you could always write a code that tries out all of the
possibilities to try to get 21. big_smile

Last edited by anonimnystefy (2012-09-06 01:32:28)


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#12 2012-09-06 01:35:38

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

Re: Combinations

I have a method that is now somewhat better then before but still not optimal it gets 13 and 23 which is close.


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

#13 2012-09-06 01:48:26

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations

Which method?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#14 2012-09-06 01:53:21

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

Re: Combinations

It is similar to a greedy algorithm but it is not quite good enough. You see, I suspect that the answer for {1,2,3,4,5,6,7} might be 12 rather than my 13.


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

#15 2012-09-06 02:10:47

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations

I will try coding a greedy.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#16 2012-09-06 03:44:01

RichieSG
Member
Registered: 2012-09-03
Posts: 8

Re: Combinations

bobbym wrote:

Hi;

Yes, that is a working 22. Unfortunately my program is a probabilistic one and is not guaranteed to find the shortest one. It will just find a decent answer.

What did you get for {1,2,3,4,5,6,7}?

Also if you have any other answers please provide them.

My original target was to find the minimum for 10 numbers and to try and get there quickly, I went straight from 6 to 8, so I don't have an answer for 7.

Thanks again for all your help on this, also to Stefy. up

Offline

#17 2012-09-06 03:50:10

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

Re: Combinations

Hi;

I got 13 for 7 numbers but it would much nicer if it were 12. Since you seem to have a good knack for these can you find a 12?


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

#18 2012-09-06 03:59:33

RichieSG
Member
Registered: 2012-09-03
Posts: 8

Re: Combinations

bobbym wrote:

It is similar to a greedy algorithm but it is not quite good enough. You see, I suspect that the answer for {1,2,3,4,5,6,7} might be 12 rather than my 13.

My assumption has been a sequence of 3-6-10-15-21 i.e.
a minimum of 3 for 5 numbers
a minimum of 6 for 6 numbers
a minimum of 10 for 7 numbers
a minimum of 15 for 8 numbers

This using a basis of differentials, e.g. for 3 the minimum is 1, for 4 it is 2 for 5 it is 3, therefore the minimum increases by an increment of 1 on top of the previous answer i.e.

a minimum of 1 for 3 numbers = 1 (1 = base figure)
a minimum of 2 for 4 numbers = 2 (1 + 1 = 2)
a minimum of 3 for 5 numbers = 3 (1 + 2 = 3)
a minimum of 6 for 6 numbers = 6 (1 + 2 + 3 = 6)
a minimum of 10 for 7 numbers = 10 (1 + 2 + 3 + 4 = 10)
a minimum of 15 for 8 numbers = 15 (1 + 2 + 3 + 4 + 5 = 15)

This is probably incorrect thinking, as there are more triples than quads for 4 numbers, the same for 5 numbers and less for 6 or more numbers.

Another thought I have had, is to assume that if 5 quads is the maximum coverage by any single triple, then the total of 70 quads divided by 5 is 14 and maybe that is the minimum. Again, this is probably incorrect, as for 6 numbers there are 15 quads and not all the triples closed 3 quads. Some closed 3, others closed 2.

Last edited by RichieSG (2012-09-06 04:02:46)

Offline

#19 2012-09-06 04:25:44

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

Re: Combinations

Hi RichieSG;

Those estimates are probably too low, 10 for 7 and 15 for 8.


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

#20 2012-09-09 09:21:39

RichieSG
Member
Registered: 2012-09-03
Posts: 8

Re: Combinations

Best I can get for 7 is 13 triples

Just have to keep trying I suppose.

Thanks for all the help from those that could big_smile

Offline

#21 2012-09-09 09:59:45

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

Re: Combinations

Hi RichieSG;

That is what I get for 7 also.


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

#22 2012-09-11 19:30:39

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

Re: Combinations

Hi;

For 9 the smallest I could get was 34.

So far the sequence is 1,3,6,13,22,34... The bad part is I do not recognize the sequence.


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

#23 2012-09-11 20:58:13

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Combinations

hi RichieSG

Sorry, I don't have a solution either.  Looks one tough problem.  sad

If your son has been set this by a teacher then either they didn't realise just how hard it is or they want to see the fruits of an investigation.  In which case all the evidence gathered so far should be worth marks; and is probably more than any of his class mates will come up with.  So make sure he understands it and he can write up what he has.

Then go  fishing (or whatever) - another worthy thing for a son and his dad to do together.  smile

Bob (maths teacher, retired)


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#24 2012-09-16 07:15:24

RichieSG
Member
Registered: 2012-09-03
Posts: 8

Re: Combinations

Fishing sounds good. big_smile

It was something given to the kids as work to do over the summer holidays and the teacher wanted to see what they would come up with. More like project work that actually finding an answer.

Offline

#25 2012-09-16 07:26:24

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

Re: Combinations

Hi RichieSG;

More like project work that actually finding an answer.

If he invented that problem then it looks like he never worked on it himself. Seems more like a computing problem than a math one.

I found a shorter 8 that consists of only 21 and not 22 moves. That gives the sequence
1,3,6,13,21,34... but I still do not recognize it.

Found a new 9 it is 32 moves long. New sequence:

1,3,6,13,21,32...

Hot off the presses! Found a 10 it is 48 moves long. Sequence is now

1,3,6,13,21,32,48...


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

Board footer

Powered by FluxBB