Results 1 to 5 of 5

Math Help - hard task

  1. #1
    Newbie
    Joined
    Sep 2005
    Posts
    4

    hard task

    I don't know how to solve this task:

    Participants of math competition are solving six tasks. For each task
    you can get one of marks - 6,5, 3 or 0 .
    It transpired that for each pair of participants we can indicate two
    tasks , that in each of them participant A got different mark from
    participant B.
    Delimit the highest number of participants for which this situation is
    possible.

    Could anybody help me?

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    In other words, you need a set of 6-tuples of elements drawn from the set {0,3,5,6} such that any two distinct 6-tuples from the set differ in at least two places.

    I claim that there can be at most 4^5 elements in this set, and that this number is achievable.

    To show that the upper bound is 4^5, consider what happens if you delete the last element in the 6-tuples. They must all still be different: for if two 5-tuples were now the same, then the original 6-tuples would only differ in one place. BBut there are only 4^5 different 5-tuples drawn from a set of 4 things.

    To show that 4^5 is achievable, replace the scores by {0,1,2,3} regarded as numbers modulo 4. Take all possible distinct 5-tuples and extend each one by a sixth element such that the six entries in the 6-tuples add up to zero modulo 4. There are now 4^5 distinct 6-tuples and I claim that any two of them differ in at least two places. Suppose if possible that two of them differ only in one place. It cannot be the last places, because the sixth place is uniquely determined by the first five: similarly it cannot one of the first fice places, beacuse if we subtract correspond entries we find exactly one non-zero difference: but in each case the entries must add up to zero.

    By the way, this is an application of the singleton bound in Coding Theory.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2005
    Posts
    4
    I don't understand this proof:

    >To show that 4^5 is achievable, replace the scores by {0,1,2,3} regarded >as numbers modulo 4. Take all possible distinct 5-tuples and extend each >one by a sixth element such that the six entries in the 6-tuples add up to >zero modulo 4. There are now 4^5 distinct 6-tuples and I claim that any >two of them differ in at least two places. Suppose if possible that two of >them differ only in one place. It cannot be the last places, because the >sixth place is uniquely determined by the first five: similarly it cannot one of >the first fice places, beacuse if we subtract correspond entries we find >exactly one non-zero difference: but in each case the entries must add up >to zero.

    How will it change when for each task you can get one of marks - 6, 5, 2, 0 or 6, 5, 4, 0.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    It doesn't affect things at all: the scores on the test are simply 4 different symbols which I choose to relabel as 0,1,2,3. The rule for appending the sixth symbol is then easy to describe in terms of modulo 4 arithmetic.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2005
    Posts
    4
    thanks for help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Matlab task
    Posted in the Math Software Forum
    Replies: 10
    Last Post: June 14th 2011, 09:36 PM
  2. plane task
    Posted in the Statistics Forum
    Replies: 1
    Last Post: June 5th 2011, 09:16 PM
  3. Can somebody complete these task?
    Posted in the Algebra Forum
    Replies: 5
    Last Post: December 8th 2010, 11:34 AM
  4. Can somebody complete these task?
    Posted in the Algebra Forum
    Replies: 4
    Last Post: December 4th 2010, 12:18 PM
  5. Application Task
    Posted in the Calculus Forum
    Replies: 2
    Last Post: June 18th 2010, 08:09 AM

Search Tags


/mathhelpforum @mathhelpforum