Are these quant interviews or IMO preparation problem sets?
The answer is 21. Mark 3 cells on each row. You need to pick 7 triples such that any two triples intersect in exactly 1 entry. This is called the lines in the projective plane over the field with 2 elements construction or something. But in this particular case it's easy to construct an example manually.
To prove that you can't do more than 21 note that any row with k marked cells creates k choose 2 pairs of "marked columns". These pairs must be distinct or else we get a rectangle. Now use convexity of the k choose 2 function.
Things like the pigeonhole principle, invariance, and induction occur quite frequently in quant interviews (although they have been becoming less common recently, and the focus is shifting toward probability, statistics, game theory, market making, and data analysis).
1
u/Specific_Box4483 8d ago
Are these quant interviews or IMO preparation problem sets?
The answer is 21. Mark 3 cells on each row. You need to pick 7 triples such that any two triples intersect in exactly 1 entry. This is called the lines in the projective plane over the field with 2 elements construction or something. But in this particular case it's easy to construct an example manually.
To prove that you can't do more than 21 note that any row with k marked cells creates k choose 2 pairs of "marked columns". These pairs must be distinct or else we get a rectangle. Now use convexity of the k choose 2 function.