Zsolt Adam Wagner

Let S be the set {1, 2, ... n²-1}. Prove or disprove the following claim: whenever we are given 2n subsets of S, each having size n, we can choose n numbers such that each of the 2n subsets contain at least one of our chosen numbers.

Example: if n=3, and we are given sets {1,2,3}, {2,3,4}, {1,3,5}, {2,5,8}, {6,7,8}, {1,4,5} then each of these contains either 3, 5 or 8.

It feels like this shouldn't be too hard to prove (or to find a counterexample), but so far I had no success at all. Note that a greedy approach shows that we can choose ~1.5n numbers that cover all given subsets.

I am a recent college graduate, currently undertaking a summer internship in the UK. I have never signed any contract of employment. I am expected to work 8 hours a day for a duration of 11 weeks, for a total salary of £2600, which is less than the UK minimum wage for employees. When I asked about this, I was told that this isn't actually a salary - half of this money is my stipend, the other half is to cover living costs. I have already received this money. My relationship with my boss is really bad, we can't get along at all, today she threatened to fire me. Can she fire me if I have never signed a contract and she is paying me below the minimum wage? Do I have to pay some amount of money back in that case?

Thanks in advance for any advice you can give.