Flashback to Faces Gameshow

This question was posed by talzamir more than two years ago, and seems it got no response at the time.

[A game show started here a few weeks ago. It's about the recognition of the faces of celebrities, which means I would be terrible at it. But a game there has interesting mathematics. It involves six faces and six attributes. The task is to pair the two up, one attribute per face, so that each claim is true. Such as Napoleon, Ten Bears, and Sarah Palin with "Died in the 1800s", "female", and "French". One attribute can fit more than one name.. e.g. both Ten Bears and Napoleon died in the 1800s.. but there is exactly one way to get six out of six.

As I see it, the more there are false positives such as Napoleon's death in the 1800s, the harder it gets to get all the answers right. So.. if there is exactly one way to six out of six right,

* how many false positives can there be? (15 is obvious but there be more?)
* how many false positives PER FACE can there be? (e.g. can each face fit three attributes and still there would be only one way to get six out of six right?)
* can the answers from the above be generalized to n faces, n attributes?]

Anyone interested in having a go now?.

It seems to me that it might be simplified to:

What is the maximum number of X's that you can fit in a n by n box given that there must by exactly one way of selecting n xs such that there is one x in each row and column?

It therefore seems to be that, as well as having at least one x in each row and column, for the solution to be unique there must be no "loops" such that
x1 and x2 share a column
x2 and x3 share a row
x3 and x4 share a column
.......
xn and x1 share a row

Is that the full set of constraints though...? Is the second constraint enough to eliminate all duplicate solutions....?

I assume the potential "maximum" you have in mind is:
Face 1 matches clues 1 to 6
Face 2 matches clues 1 to 5
Face 3 matches clues 1 to 4
..
Face 8 matches clue 1

So there are 21 clues, 6 clues are the unique match so there were 15 false positives

Originally posted by iamatiger
I assume the potential "maximum" you have in mind is:
Face 1 matches clues 1 to 6
Face 2 matches clues 1 to 5
Face 3 matches clues 1 to 4
..
Face 8 matches clue 1

So there are 21 clues, 6 clues are the unique match so there were 15 false positives

Yes, that is how I see it too. Although I have to admit it wasn't immediately "obvious" to me that there could even be 15 false positives. It seems no one else has any ideas on this.

I think 15 is the maximum. In general if you have an nxn box then the maximum number of false positives is n(n-1)/2.

Suppose you have fixed the nxn box with x's such that there is a unique choice of x's so that each row and column has exactly one x in it. By permuting rows we may assume this choice has the n x's all along the diagonal. Then we have n^2-n=n(n-1) other squares in the nxn box. If more than half of these squares are filled in with x's then there must be a pair of x's in the positions (i,j) and (j,i) for some i not equal to j. This is a contradiction as then we can swap the x's in (i,i) and (j,j) with (i,j) and (j,i). Therefore we cannot have more than half of the n(n-1) squares containing x's. Since we know how to fill in exactly half (fill in all squares above the diagonal) this must be the maximum possible.

Also I think the answer to the second part of the question is 1.

If everyone has 1 or more false attributes then do the following: Take the first person and change their true attribute to a false one. Then take the person who is already assigned to this attribute and change their true attribute to a false one. Continue doing this until a loop is generated in other words you have person A with person B's attribute who has person C's attribute... who has person A's attribute. You've then found an alternative matching of people to attributes by acting this loop on the true matching. This is a contradiction and hence not everyone can have a false attribute and hence the maximum number of attributes that everyone can have is 1.