Printable View
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
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.
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.
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.
thanks for help