

Title: Forcing a test Post by Leonid Broukhis on Feb 3^{rd}, 2009, 4:52pm This is a puzzle offered at last Fall's Russian "Tournament of Cities" with a variation by me. Original: There is a 30question online test with "true/false" answers. Submitting it (all questions must be answered) yields a score  the number of correct answers. You don't know the topic of the test at all; you can only guess. a) Can you guarantee yourself a score of 30 at the 30th attempt? b) At the 25th attempt? c) At some Nth (N < 25) attempt? d*) What is the min. N for which it is possible? Variation: A written test (30 true/false questions) is administered on two days with the same answer key; the scores are known at the end of the day. A test sheet is not scored unless all 30 questions are answered. How many proxies do you need to send the first day to fill out the test to be able to get a score of 30 the next day? 

Title: Re: Forcing a test Post by towr on Feb 4^{th}, 2009, 2:17am I can do the variation with I'll have to think more about how to improve on it. [edit]I think I miscounted, and my method gives 30, rather than 29. Which unfortunately means I can't get it right on the 30th attempt.[/edit] 

Title: Re: Forcing a test Post by towr on Feb 4^{th}, 2009, 6:01am I think I can do the original in [hide]21+1[/hide], and it may still be improved. [hide]I used the ID3 decision tree algorithm, for 10 questions the tree has a depth of 7 to find out which questions are right. Splitting the questions into 3 groups doesn't seem to actually cost you an attempt.[/hide] [e]Shaved off one more attempt [hide]by splitting in 2 x 11 + 8, which tells you the correct answers in 20 tries, so you get it right on the 21th.[/hide] And due to computational limitations that's as far as my current approach can bring me.[/e] 

Title: Re: Forcing a test Post by Leo Broukhis on Feb 4^{th}, 2009, 8:48am Thanks, towr! I did not know about the [hide]decision tree[/hide] algorithms before. My first idea  [hide]to do a binary search[/hide]  happened to solve b). [hide] Is your solution 2 x 11 + 8 due to the fact that 30/e = 11?[/hide] 

Title: Re: Forcing a test Post by towr on Feb 4^{th}, 2009, 9:36am on 02/04/09 at 08:48:13, Leo Broukhis wrote:
Quote:
Could you elaborate on how you get to 25? Quote:
I think you can probably do better. And the ID3 algorithm doesn't necessarily give the shallowest decision tree in the first place (it's heuristic). Here's my list of how many attempts you need to find the correct list of answers: [hide]N tries 1  1 2  2 3  3 4  4 5  4 6  5 7  6 8  6 9  7 10  7 11  7 12  8 [edit] using leo's program 13  8 14  9 15  9 [/edit] [/hide] So I'd expect more savings later on. But the way I compute it each next step takes 4 times as much memory, and I hit 44% already. For example it seems in line with the pattern that [hide]15 would only take 9[/hide], which means you can do it in [hide]18[/hide] attempts or less. But I'd need a more clever way to calculate it to confirm this suspicion. (Or wait for SMQ to inevitably set his teeth into it ;) ) 

Title: Re: Forcing a test Post by Leo Broukhis on Feb 4^{th}, 2009, 11:09am on 02/04/09 at 09:36:20, towr wrote:
Sorry, I miscalculated. Binary search solves a). 

Title: Re: Forcing a test Post by Hippo on Feb 4^{th}, 2009, 11:18am It seems to me it should do something with theory of codes. (At least the variant with filling all tests at once). Lower bound seems to be eight ... as 15^{7}<2^{30} and inverse test gives the same information. 

Title: Re: Forcing a test Post by Leo Broukhis on Feb 4^{th}, 2009, 12:00pm on 02/04/09 at 11:18:19, Hippo wrote:
Quote:
According to my calculations, the least information of a popcount of a 30bit vector is 2.79 bits (when you get 15), therefore the lower bound is 11. 

Title: Re: Forcing a test Post by towr on Feb 4^{th}, 2009, 12:03pm [e] I = too slow [/e] on 02/04/09 at 11:18:19, Hippo wrote:


Title: Re: Forcing a test Post by Hippo on Feb 4^{th}, 2009, 2:11pm on 02/04/09 at 12:03:41, towr wrote:
Of course it was not tight lower bound ;). I am not sure with the test dependency ... at least parity is fixed so you can avoid result 15. So may be lg(2^{30}/C(30,14))? 

Title: Re: Forcing a test Post by towr on Feb 5^{th}, 2009, 1:55am For the variation, splitting into 3 x 10 gives the same number of tries as the original [hide]21 attempts to find the answer key For 10, here is one possible list of patterns that can be used 0000000000  0 0000011111  31 0001100011  99 0011010101  213 0100100101  293 0010111011  187 0000000110  6 (They're in the order in which the heuristic of maximum local information gain gave them)[/hide] Same disclaimer as before applies: ID3 isn't guaranteed to be optimal, and in any case the split may not be optimal. 

Title: Re: Forcing a test Post by Leo Broukhis on Feb 5^{th}, 2009, 11:30am on 02/05/09 at 01:55:50, towr wrote:
While it is easy to see how the cost of the first attempt is saved in case of splitting in the "online" version, I don't understand how that works in this case, i.e. how do you replicate the patterns for a multiple of n? 

Title: Re: Forcing a test Post by towr on Feb 5^{th}, 2009, 11:53am on 02/05/09 at 11:30:58, Leo Broukhis wrote:


Title: Re: Forcing a test Post by Leo Broukhis on Feb 5^{th}, 2009, 12:11pm :[ Thank you. Sometimes thinking parallel is bad. 

Title: Re: Forcing a test Post by Leo Broukhis on Feb 5^{th}, 2009, 4:46pm towr, my max inf. gain algorithm gives 9 for n=15 ;D 

Title: Re: Forcing a test Post by Leo Broukhis on Feb 5^{th}, 2009, 9:09pm I was not able to find a 9element static set for n=15. The best 10element set is [hide]0 127 1927 6553 10922 14659 6884 5993 14387 1[/hide] Where the last probe is needed to disambiguate 24 pairs. 

Title: Re: Forcing a test Post by towr on Feb 6^{th}, 2009, 12:01am on 02/05/09 at 16:46:22, Leo Broukhis wrote:


Title: Re: Forcing a test Post by Leo Broukhis on Feb 6^{th}, 2009, 1:07am Oh well, as they say, please excuse our dust. Hope that the attachment works. 

Title: Re: Forcing a test Post by towr on Feb 6^{th}, 2009, 1:25am It performs a lot better than my program, albeit in part because it's c++ rather than python. You can get a little bit improvement by using a different bitcounting technique*, it shaves about 5% off. * http://www.cs.utk.edu/~vose/cstuff/bithacks.html#CountBitsSetParallel 

Title: Re: Forcing a test Post by Leo Broukhis on Feb 6^{th}, 2009, 1:45am Sure, I just didn't bother typing it. The data structure to improve is the set; vector helps but not by much. A sparse bitmap should work well. Another big improvement would be to only test pivots whose bits are proper subsets of the OR of the values within a group (as all other bits won't affect the result; HAKMEM should have a fast function to iterate over all subsets of a bitset somewhere) 

Title: Re: Forcing a test Post by towr on Feb 6^{th}, 2009, 2:16am on 02/06/09 at 01:45:54, Leo Broukhis wrote:


Title: Re: Forcing a test Post by Leo Broukhis on Feb 6^{th}, 2009, 5:18pm Further, the pivot values that have 0 where the whole group has 1 can be filtered as well. 

Title: Re: Forcing a test Post by towr on Feb 13^{th}, 2009, 3:42am I've tried a new approach with comes pretty close to loglinear runtime (in the number of numbers). Unfortunately it doesn't give quite as good results. To find a pivot, what I do is first find the best bit, the find the bit I can best add to that, etc until I have the best pivot that I can find in that way. This takes around O(#bits^{2}). Which means the total is O(2^{#bits} * #bits^{2}) Here's a list of my results so far: #bits : max steps 1 : 1 2 : 2 3 : 3 4 : 4 5 : 5 6 : 6 7 : 6 8 : 7 9 : 7 10 : 8 11 : 8 12 : 9 13 : 9 14 : 10 15 : 11 16 : 11 17 : 12 18 : 12 19 : 13 20 : 14 21 : 14 22 : 15 23 : 15 24 : 16 25 : 16 26 : 17 27 : 17 So generally it's a bit worse than the previous algorithm, but it's much faster. And I have some ideas on how to maybe improve performance. 

Title: Re: Forcing a test Post by Leo Broukhis on Feb 13^{th}, 2009, 9:04am towr, I have a feeling that your algorithm will do no better than the result achieved by splitting the bit vector in smaller pieces. Consider 11 that it gives for 15: the best splitting is 10 and 5 using 7 and 4 steps (using the original algorithm). Or 17 that it gives for 27: that's 8 + 9 for pieces of sizes 13 and 14. 

Title: Re: Forcing a test Post by towr on Feb 13^{th}, 2009, 11:31am on 02/13/09 at 09:04:11, Leo Broukhis wrote:
For example there is room to reuse the previous better results. If not all the bits of the numbers in a group change (staying either 0 or 1 for all), then you can remove them from the number, and so reduce it to a problem of less complexity. And one might do better by not searching for the best improvement locally, but for example consider the next step as well. 

Title: Re: Forcing a test Post by Azgard on Feb 16^{th}, 2009, 8:26am I don't suppose that when scoring the test they tell you which questions were answered correctly and which were not...? Because that would make scoring perfect on the test attainable on the second try! Then again, if that were the solution, the question would not be in the "Hard" section of the forum... 

Title: Re: Forcing a test Post by Leo Broukhis on Mar 4^{th}, 2009, 11:29am I know a solution (verified by an exhaustive test) for 30 questions that uses 16 probes: 16730 4701400 7718455 7880704 8010479 8534452 26199916 29343619 43779229 110902898 260266666 262217797 526377246 526432041 528341489 534958022 (obviously, the first probe can be made 0 by xoring everything by 16730, but that's how it was sent to me). Here's how it has been found: [hide]by manually constructing a set of 30 Ndimensional vectors with coordinates equal to 1 or 1 which partial sums are all distinct. It was done in a spreadsheet.[/hide] 

Title: Re: Forcing a test Post by Leo Broukhis on Mar 5^{th}, 2009, 9:46am A small program implementing the algorithm above has found a (verified) solution of 8 probes for 13 questions: 0 4478 3646 3038 5262 2038 6370 7936 This solution can be extended to 9 probes for 15 questions: 0 4478 3646 3038 5262 2038 6370 7937 < NB the low bit set 10218 The algorithm claims that 16 probes can resolve up to 33 (!) questions. 

Title: Re: Forcing a test Post by towr on Mar 5^{th}, 2009, 10:38am Impressive. 

Title: Re: Forcing a test Post by Leo Broukhis on Mar 12^{th}, 2009, 6:44pm My collaborator on this problem has observed the similarity of what we're trying to find with Hadamard matrices. Indeed, the solutions for 8 and 16 probes include the matrices as subsets. As there exist a Hadamard matrix of order 12, I was able to construct a solution for 20 questions using the matrix as the basis, and then to extend it to 21 questions (losing the Hadamard property, so it remains unclear how to search for the maximal vector set). A good approximation to the max number of questions that can be solved by N probes is given by A000788(N1)+1  but a solution mentioned above of 9 probes for 15 questions stands out. More things to discover... 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 