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 16th, 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 4th, 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 N-dimensional vectors with coordinates equal to 1 or -1 which partial sums are all distinct. It was done in a spreadsheet.
|
| « Last Edit: Mar 4th, 2009, 11:30am by Leo Broukhis » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Forcing a test
« Reply #27 on: Mar 5th, 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 5th, 2009, 10:44am by Leo Broukhis » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Forcing a test
« Reply #29 on: Mar 12th, 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(N-1)+1 - but a solution mentioned above of 9 probes for 15 questions stands out.
More things to discover...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
