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

My question is:
►Can a student deduce the correct answers from this information?

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.

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

ignore

4. ## Re: Interesting math/programming problem....

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