
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. 1234, 1235, 1245, 1345 and 2345 but only 3 combinations of 3 are required to show up in all of the combinations of 4. They are 123, 145 and 345.
1234 contains 123 1235 contains 123 1245 contains 145 1345 contains 145 2345 contains 345
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.
Thanks
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
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 1234, 1235, 1245, 1345 and 2345. We also know that there are 10 triples possible i.e. 123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
What I am looking for, is to find the minimum number of triples where the numbers appear in the quads. For example the triple 123 appears in 1234 and 1235. This leaves 3 other quads which do not feature the triple 123. For those quads that remain 145 appears in 1245 and 1345 and 345 covers 2345.
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 123 appears in 5 quads, i.e. 1234, 1235, 1236 1237 and 1238, 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.
123 appears in 1234, 1235 and 1236. Of the 12 quads remaining, 156 appears in 1256, 1356 and 1356. Of the 9 quads remaining, 345 appears in 1345, 1345 and 1345. This now leaves 6 quads for which 124 appears in 1245 and 1246, 346 which appears in 1346 and 2346 and finally 256 which appears in the last 2, 2356 and 2456.
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.
Last edited by RichieSG (20120905 03:34:13)
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?
The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
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 123, then this "closes" quads 1234, 1235, 1236 1237 and 1238, 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 (20120905 07:52:11)
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.
The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
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 (20120906 01:00:32)
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
Re: Combinations
Of course, you could always write a code that tries out all of the possibilities to try to get 21.
Last edited by anonimnystefy (20120906 23:32:28)
The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
Re: Combinations
The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
Re: Combinations
I will try coding a greedy.
The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
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.
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
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 36101521 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 (20120907 02:02:46)
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
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
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 bob bundy
 Moderator
Re: Combinations
hi RichieSG
Sorry, I don't have a solution either. Looks one tough problem.
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.
Bob (maths teacher, retired)
You cannot teach a man anything; you can only help him find it within himself..........Galileo Galilei
Re: Combinations
Fishing sounds good.
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.
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
