Results 1 to 4 of 4

Math Help - Interesting math/programming problem....

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    52
    Thanks
    17

    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.
    Last edited by ChessTal; July 20th 2013 at 02:08 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,545
    Thanks
    1394

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2012
    From
    Erewhon
    Posts
    164
    Thanks
    108

    Re: Interesting math/programming problem....

    ignore
    Last edited by zzephod; July 20th 2013 at 10:48 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2010
    Posts
    52
    Thanks
    17

    Re: Interesting math/programming problem....

    Quote Originally Posted by HallsofIvy View Post
    "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)....
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: June 9th 2011, 11:45 AM
  2. Replies: 4
    Last Post: January 13th 2010, 06:42 AM
  3. Interesting Math Problem
    Posted in the Statistics Forum
    Replies: 3
    Last Post: February 7th 2009, 07:07 AM
  4. linear programming, quantitive math
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: February 24th 2008, 07:50 PM
  5. discrete math programming
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 14th 2008, 12:47 PM

Search Tags


/mathhelpforum @mathhelpforum