wu :: forums
wu :: forums - Forcing a test

Welcome, Guest. Please Login or Register.
Dec 4th, 2022, 4:43pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Grimbal, william wu, ThudnBlunder, towr, Eigenray, Icarus, SMQ)
   Forcing a test
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Forcing a test  (Read 5043 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 Quote Modify 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: male
Posts: 459
Re: Forcing a test  
« Reply #26 on: Mar 4th, 2009, 11:29am »
Quote Quote Modify 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: male
Posts: 459
Re: Forcing a test  
« Reply #27 on: Mar 5th, 2009, 9:46am »
Quote Quote Modify 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
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Forcing a test  
« Reply #28 on: Mar 5th, 2009, 10:38am »
Quote Quote Modify Modify

Impressive.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Leo Broukhis
Senior Riddler
****





   


Gender: male
Posts: 459
Re: Forcing a test  
« Reply #29 on: Mar 12th, 2009, 6:44pm »
Quote Quote Modify 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
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board