Interesting math/programming problem....

• Jul 20th 2013, 03:06 PM
ChessTal
Interesting math/programming problem....
The problem is simple, let me describe it:

Suppose i ask 5 questions to 3 students and they give their answers.
Every student is able to see what every student had answered.
All the questions have a YES/NO answer.
The correct answers are not given be me to the students, but i give to all students how many questions got right each of the students.

•Example for the questions Q1,Q2,Q3,Q4,Q5 let's suppose the correct answers are 11001 (1 for YES and 0 for NO, so we have that question 1 has as an answer the YES, while question 4 has an answer of NO and question 5 has also an answer of YES.) and the students don't know about it.
•Also let's suppose the student-1 gave the answer to all questions 10000, student-2 gave 11111 and student-3 gave 10110 and all 3 students know the answers all the others gave.
•So now i give to the students the information that the student-1 had 3 correct answers, the student-2 had 3 correct answers also, while the student-3 had only 1 correct answer.

My question is:
►Can a student deduce the correct answers from this information?
IMPORTANT NOTE: I'm NOT speaking about this specific example, i'm interested in the general problem!

So let's see the general problem:
Let's say we have N questions being asked to K students.
So we get the answers Ak1, Ak2, ..., AkNby the k-th students with k from 1 to K and Akx = 0 or 1 for every k at 1 to K and x at 1 to N.
And the numbers of total student's correct answers is denoted by Cj with j from 1 to K.

Example (6 questions, 4 students, random answers, random Cj numbers of correct answers) we are given the information:
Student-1: 100111
Student-2: 100001
Student-3: 001101
Student-4: 010111
C1= 4 (I.e student-1 answered correctly 4 questions)
C2= 4
C3= 1
C4= 5

►Given that information, can we deduce with a GENERAL and STRAIGHTFORWARD(i.e to be programmed) way what all the correct answers are? I.e to find the string of 1's and 0's with length N, that validates the above information that had been given.
►Is the aforementioned string unique?

(Note: any Cj equal to 0 or N gives us the desired string with the correct answers immediately.)
Special cases of the problem can be solved by taking multiple different cases and by deductive reasoning we obtain the solution, but that's a non general solution since we have to use different cases and different type of reasoning each time depending on what the N,K,Cj numbers are.
I tried to solve the above with using the XOR operator but i couldn't go anywhere.

Can you help me find the solution to the ► questions?
Thanks.(Worried)
• Jul 20th 2013, 05:10 PM
HallsofIvy
Re: Interesting math/programming problem....
"Given that information, can we deduce with a GENERAL and STRAIGHTFORWARD(i.e to be programmed) way what all the correct answers are? I.e to find the string of 1's and 0's with length N, that validates the above information that had been given."

No, not always. For example, it might be that the n students all answer the m questions in exactly the same way. Knowing that each had i questions correct and m- i questions wrong tells us nothing about which answer were correct and which wrong.
• Jul 20th 2013, 11:41 PM
zzephod
Re: Interesting math/programming problem....
ignore
• Jul 21st 2013, 12:45 AM
ChessTal
Re: Interesting math/programming problem....
Quote:

Originally Posted by HallsofIvy
"Given that information, can we deduce with a GENERAL and STRAIGHTFORWARD(i.e to be programmed) way what all the correct answers are? I.e to find the string of 1's and 0's with length N, that validates the above information that had been given."

No, not always. For example, it might be that the n students all answer the m questions in exactly the same way. Knowing that each had i questions correct and m- i questions wrong tells us nothing about which answer were correct and which wrong.

Indeed, but in that case i should transform my question to ask about a GENERAL and STRAIGHTFORWARD(i.e to be programmed) way to find if the string of the correct answers can be found or not and if it can, to find it(with a general and straightforward way)....(Smile)