Welcome Guest
You last visited December 14, 2017, 7:36 pm
All times shown are
Eastern Time (GMT-5:00)

# Need some help with algorithm

Topic closed. 2 replies. Last post 5 years ago by Newb.

 Page 1 of 1
New Member

Germany
Member #114512
August 1, 2011
2 Posts
Offline
 Posted: January 1, 2013, 1:07 am - IP Logged

Hi, I'm trying so solve following problem:

Let's say, we have a set A={1,2,3,.....49}.

Now, I am defining sets A1, A2, A3,....An as follow: A1={a1,a2,a3,....a30}, A2={b1,b2,b3,...b30}, and so on, where all elements of sets Ai are also elements of set A, which means they are subsets of set A. (All sets Ai have 30 elements).

Now, I am looking for a set C={ {A1},{A2},{A3},....{An} } so, that if I pick randomly 6 elements of set A, they will be (at least) in one of sets Ai.

What is n? Let's see: first of all, how much possibilities are to pick 6 elements of set A? There are (49*48*47*46*45*44)/6!=13.983.816

Secondly, how much of these posibilities covers one of sets Ai? Because set Ai has 30 elements, it covers (30*29*28*27*26*25)/6!=593.775

Now dividing both results, it gives 23,55 what means, that we need at least n=24 (probably more, I don't sure).

So the question is, how to find this set C?

Let's say, we can start so: A1={1,2,3,....30}, this will be first set. But what next? With some algorithm I can implement it in C or Java, but I dont know how to start. Thanks.

United States
Member #124493
March 14, 2012
7023 Posts
Offline
 Posted: January 6, 2013, 11:19 pm - IP Logged

Hi, I'm trying so solve following problem:

Let's say, we have a set A={1,2,3,.....49}.

Now, I am defining sets A1, A2, A3,....An as follow: A1={a1,a2,a3,....a30}, A2={b1,b2,b3,...b30}, and so on, where all elements of sets Ai are also elements of set A, which means they are subsets of set A. (All sets Ai have 30 elements).

Now, I am looking for a set C={ {A1},{A2},{A3},....{An} } so, that if I pick randomly 6 elements of set A, they will be (at least) in one of sets Ai.

What is n? Let's see: first of all, how much possibilities are to pick 6 elements of set A? There are (49*48*47*46*45*44)/6!=13.983.816

Secondly, how much of these posibilities covers one of sets Ai? Because set Ai has 30 elements, it covers (30*29*28*27*26*25)/6!=593.775

Now dividing both results, it gives 23,55 what means, that we need at least n=24 (probably more, I don't sure).

So the question is, how to find this set C?

Let's say, we can start so: A1={1,2,3,....30}, this will be first set. But what next? With some algorithm I can implement it in C or Java, but I dont know how to start. Thanks.

Is this going to help me wheel better?

United Kingdom
Member #31295
January 27, 2006
73 Posts
Offline
 Posted: February 4, 2013, 8:27 am - IP Logged

There would be more than 24 sets each using 30 numbers. For example assume the following sets have 30 numbers in sequence ie an increase of 1 from one number to the next number in sequence.

{1...30},  {2...31} {3...32}, {4...33}, {5...34}, {6...35}, {7...36}, {8...37}, {9...38}, {10...39}, {11...40}, {12...41}, {13...42}, {14...43}, {15...44},
{16...45}, {17...46}, {18...47}, {19....48}, {20...49}

If you were to pick numbers 1,2,5,17,30,49 these numbers would not be covered by any of the above sets because 1 and 49 are not in the same set

That's 20 sets so far. Now add the following set which also has 30 numbers

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,31} - I have dropped number 30 and replaced it with 31. Only four numbers would match this set as 30 has been dropped and 49 is still not in this set.

If you keep removing and adding new numbers to create a new set you would end up with more than 24 sets in total.

 Page 1 of 1