wu :: forums « wu :: forums - Forcing a test » Welcome, Guest. Please Login or Register. Jun 6th, 2023, 11:46am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, SMQ, ThudnBlunder, towr, Grimbal, Icarus, Eigenray)    Forcing a test « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 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
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

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

Impressive.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
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
 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 »