Author |
Topic: Forcing a test (Read 5315 times) |
|
Leo Broukhis
Senior Riddler
Gender: 
Posts: 459
|
 |
Forcing a test
« on: Feb 3rd, 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 30-question 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 3rd, 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 4th, 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 4th, 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 4th, 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 4th, 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 4th, 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 4th, 2009, 9:36am » |
Quote Modify
|
on Feb 4th, 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 6th, 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 4th, 2009, 11:09am » |
Quote Modify
|
on Feb 4th, 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 4th, 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 157<230 and inverse test gives the same information.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Forcing a test
« Reply #7 on: Feb 4th, 2009, 12:00pm » |
Quote Modify
|
on Feb 4th, 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 157<230 and inverse test gives the same information. |
|
According to my calculations, the least information of a popcount of a 30-bit 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 4th, 2009, 12:03pm » |
Quote Modify
|
[e] I = too slow [/e]
on Feb 4th, 2009, 11:18am, Hippo wrote:| Lower bound seems to be eight ... as 157<230 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(230/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 4th, 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 4th, 2009, 2:11pm » |
Quote Modify
|
on Feb 4th, 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(230/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(230/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 5th, 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 5th, 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 5th, 2009, 11:30am » |
Quote Modify
|
on Feb 5th, 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 5th, 2009, 11:53am » |
Quote Modify
|
on Feb 5th, 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 (k-1) 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 5th, 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 5th, 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 5th, 2009, 5:46pm by Leo Broukhis » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Forcing a test
« Reply #15 on: Feb 5th, 2009, 9:09pm » |
Quote Modify
|
I was not able to find a 9-element static set for n=15.
The best 10-element 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 6th, 2009, 12:01am » |
Quote Modify
|
on Feb 5th, 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 6th, 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 6th, 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 6th, 2009, 2:16am » |
Quote Modify
|
on Feb 6th, 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 6th, 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 13th, 2009, 3:42am » |
Quote Modify
|
I've tried a new approach with comes pretty close to log-linear 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(#bits2). Which means the total is O(2#bits * #bits2)
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 13th, 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 13th, 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 13th, 2009, 11:31am » |
Quote Modify
|
on Feb 13th, 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
quiz3.cc