Welcome Guest
Log In | Register )
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
PrintE-mailLink
Avatar
Thread Starter
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?

      Avatar

      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.