Author 
Topic: Forcing a test (Read 5180 times) 

Azgard
Senior Riddler
Just gonna drive around the planet, check it out.
Posts: 453


Re: Forcing a test
« Reply #25 on: Feb 16^{th}, 2009, 8:26am » 
Quote Modify

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...


IP Logged 
Lots of opportunities are missed because they come dressed in overalls and look like work.



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #26 on: Mar 4^{th}, 2009, 11:29am » 
Quote Modify

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: 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.

« Last Edit: Mar 4^{th}, 2009, 11:30am by Leo Broukhis » 
IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #27 on: Mar 5^{th}, 2009, 9:46am » 
Quote Modify

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.

« Last Edit: Mar 5^{th}, 2009, 10:44am by Leo Broukhis » 
IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Forcing a test
« Reply #29 on: Mar 12^{th}, 2009, 6:44pm » 
Quote Modify

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...


IP Logged 



