wu :: forums « wu :: forums - Forcing a test » Welcome, Guest. Please Login or Register. Oct 3rd, 2023, 10:30pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, ThudnBlunder, Grimbal, Icarus, Eigenray, towr, william wu)    Forcing a test « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Forcing a test  (Read 5204 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.

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
 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
 Re: Forcing a test   quiz3.cc « Reply #17 on: Feb 6th, 2009, 1:07am » Quote Modify

Oh well, as they say, please excuse our dust.
Hope that the attachment works.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Forcing a test   « Reply #18 on: Feb 6th, 2009, 1:25am » Quote Modify

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/c-stuff/bithacks.html#CountBitsSetParallel
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
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
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »