Using a pool of problems, 16 tests will be formed.
- Every test should have the same number of problems.
- Any problem should be included in at most 8 tests.
- For every 4 tests, there should be at least 1 problem common to all of them.
- Within a test a single problem cannot be used more than once.
- Some tests may be formed of exactly the same problems.
What can be the minimum number of problems in this pool?
What I have done so far is as follows, Since as it is said for every 4 tests, first I calculate C(16,4)=1820 and a question can be asked at most 8 tests, for a question the contribution to the universal space is C(8,4) and that is 70. So, at least there should be 26 questions.
My algorithm finds always the biggest number of four combinations which not already added to the array so far.
Let me suppose the first array is (1, 2, 3, 4, 5, 6, 12, 15) and this means the first question is asked in these tests and the count of 4 combinations is 70. My algorithm calculates the next biggest count of 4 combinations, (1, 4, 5, 7, 8, 13, 14, 16) and the other step is (2, 6, 9, 10, 12, 13, 14, 16) and each one makes the same number contribution which is 70, and totaly 210. After then, at the fourth step, the biggest contribution is 68. (3, 4, 5, 9, 10, 11, 13, 15). I have to get at least 1820 totally. This algorithm runs about 20 minutes on my machine, it is slow.
of course, I don't think this algorithm quarantees the best solution, any ideas what methods/algorithms can be used to solve the problem? I checked the bin packing algorithms but I don't think that works for this special problem.