Author 
Topic: Forcing a test (Read 5132 times) 

Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Forcing a test
« on: Feb 3^{rd}, 2009, 4:52pm » 
Quote Modify

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?

« Last Edit: Feb 3^{rd}, 2009, 4:59pm by Leo Broukhis » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #1 on: Feb 4^{th}, 2009, 2:17am » 
Quote Modify

I can do the variation with 29 30, and so also a). 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]

« Last Edit: Feb 4^{th}, 2009, 3:44am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #2 on: Feb 4^{th}, 2009, 6:01am » 
Quote Modify

I think I can do the original in 21+1, and it may still be improved. 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. [e]Shaved off one more attempt by splitting in 2 x 11 + 8, which tells you the correct answers in 20 tries, so you get it right on the 21th. And due to computational limitations that's as far as my current approach can bring me.[/e]

« Last Edit: Feb 4^{th}, 2009, 6:55am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #3 on: Feb 4^{th}, 2009, 8:48am » 
Quote Modify

Thanks, towr! I did not know about the decision tree algorithms before. My first idea  to do a binary search  happened to solve b). Is your solution 2 x 11 + 8 due to the fact that 30/e = 11?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #4 on: Feb 4^{th}, 2009, 9:36am » 
Quote Modify

on Feb 4^{th}, 2009, 8:48am, Leo Broukhis wrote:Thanks, towr! I did not know about the decision tree algorithms before. 
 The problem is that it doesn't give very nice solutions. It's a long list of "if this than that else if this", etc Quote:My first idea  to do a binary search  happened to solve b). 
 I tried something similar, but only got to 31. Could you elaborate on how you get to 25? Quote: Is your solution 2 x 11 + 8 due to the fact that 30/e = 11? 
 I wouldn't dare say. It's just the limit of what my computer could handle calculating. So it's more likely a coincidence. 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: 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] 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 15 would only take 9, which means you can do it in 18 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 )

« Last Edit: Feb 6^{th}, 2009, 1:39am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #5 on: Feb 4^{th}, 2009, 11:09am » 
Quote Modify

on Feb 4^{th}, 2009, 9:36am, towr wrote: Could you elaborate on how you get to 25? 
 Sorry, I miscalculated. Binary search solves a).


IP Logged 



Hippo
Uberpuzzler
Gender:
Posts: 919


Re: Forcing a test
« Reply #6 on: Feb 4^{th}, 2009, 11:18am » 
Quote Modify

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.


IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #7 on: Feb 4^{th}, 2009, 12:00pm » 
Quote Modify

on Feb 4^{th}, 2009, 11:18am, Hippo wrote:It seems to me it should do something with theory of codes. (At least the variant with filling all tests at once). 
 I've guessed as much. Quote: Lower bound seems to be eight ... as 15^{7}<2^{30} and inverse test gives the same information. 
 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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #8 on: Feb 4^{th}, 2009, 12:03pm » 
Quote Modify

[e] I = too slow [/e] on Feb 4^{th}, 2009, 11:18am, Hippo wrote:Lower bound seems to be eight ... as 15^{7}<2^{30} and inverse test gives the same information. 
 You never get lg(15)=3.9 bits of information out of a test. At best it's lg(2^{30}/C(30,15)) ~= 2.79 So you need at minimum 11 tests. And you get increasingly less new information from a test, since it overlaps.

« Last Edit: Feb 4^{th}, 2009, 12:04pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Hippo
Uberpuzzler
Gender:
Posts: 919


Re: Forcing a test
« Reply #9 on: Feb 4^{th}, 2009, 2:11pm » 
Quote Modify

on Feb 4^{th}, 2009, 12:03pm, towr wrote:[e] I = too slow [/e] You never get lg(15)=3.9 bits of information out of a test. At best it's lg(2^{30}/C(30,15)) ~= 2.79 So you need at minimum 11 tests. And you get increasingly less new information from a test, since it overlaps. 
 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))?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #10 on: Feb 5^{th}, 2009, 1:55am » 
Quote Modify

For the variation, splitting into 3 x 10 gives the same number of tries as the original 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) Same disclaimer as before applies: ID3 isn't guaranteed to be optimal, and in any case the split may not be optimal.

« Last Edit: Feb 5^{th}, 2009, 1:56am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #11 on: Feb 5^{th}, 2009, 11:30am » 
Quote Modify

on Feb 5^{th}, 2009, 1:55am, towr wrote:For the variation, splitting into 3 x 10 gives the same number of tries as the original 21 attempts to find the answer key 
 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?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #12 on: Feb 5^{th}, 2009, 11:53am » 
Quote Modify

on Feb 5^{th}, 2009, 11:30am, Leo Broukhis 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? 
 You can start with a 'baseline' of answering "true" to everything. And then each pattern of n (except the last) is run independently, i.e. only changing those n questions, leaving the rest "true". For the last block of n, you can skip the first test, because you know how many true answers there are in total and how many there are in the first (k1) blocks and therefore know the result of the first test.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #13 on: Feb 5^{th}, 2009, 12:11pm » 
Quote Modify

Thank you. Sometimes thinking parallel is bad.


IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #14 on: Feb 5^{th}, 2009, 4:46pm » 
Quote Modify

towr, my minimax algorithm gives 10 for n=15. my max inf. gain algorithm gives 9 for n=15

« Last Edit: Feb 5^{th}, 2009, 5:46pm by Leo Broukhis » 
IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #15 on: Feb 5^{th}, 2009, 9:09pm » 
Quote Modify

I was not able to find a 9element static set for n=15. The best 10element set is 0 127 1927 6553 10922 14659 6884 5993 14387 1 Where the last probe is needed to disambiguate 24 pairs.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #16 on: Feb 6^{th}, 2009, 12:01am » 
Quote Modify

on Feb 5^{th}, 2009, 4:46pm, Leo Broukhis wrote:towr, my minimax algorithm gives 10 for n=15. my max inf. gain algorithm gives 9 for n=15 
 Could you share the algorithm?


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Leo Broukhis
Senior Riddler
Gender:
Posts: 459

Oh well, as they say, please excuse our dust. Hope that the attachment works.


IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #19 on: Feb 6^{th}, 2009, 1:45am » 
Quote Modify

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) This should make it O(n log n) rather than O(n^2) and, in conjunction with the sparse bitmap, will allow to run the algorithm for n=30 in a reasonable time.

« Last Edit: Feb 6^{th}, 2009, 5:19pm by Leo Broukhis » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #20 on: Feb 6^{th}, 2009, 2:16am » 
Quote Modify

on Feb 6^{th}, 2009, 1:45am, Leo Broukhis wrote: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) 
 It seems to save about half to check pivot & group_or == pivot.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #21 on: Feb 6^{th}, 2009, 5:18pm » 
Quote Modify

Further, the pivot values that have 0 where the whole group has 1 can be filtered as well.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #22 on: Feb 13^{th}, 2009, 3:42am » 
Quote Modify

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.

« Last Edit: Feb 13^{th}, 2009, 6:49am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #23 on: Feb 13^{th}, 2009, 9:04am » 
Quote Modify

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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Forcing a test
« Reply #24 on: Feb 13^{th}, 2009, 11:31am » 
Quote Modify

on Feb 13^{th}, 2009, 9:04am, Leo Broukhis wrote:I have a feeling that your algorithm will do no better than the result achieved by splitting the bit vector in smaller pieces. 
 Without an improvement to the heuristics, I'd have to agree. But I don't think the approach is necessarily a lost cause and beyond improvement. 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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



