In the last time I did lot's of preparations for future math contests and I discovered a problem where I don't know how to start with.
Here is the problem:
In a spa there are 100 showers. In every shower is a faucet which controlles the water for this shower. Due to a mistake every faucet controlles the water for exactly 5 other showers as well.
Show that you can ever select 10 showers so that you don't notice the defect, when you close the remaining 90 showers.
I already tried it with a graph, so every shower is connected to 5 other showers. Then I tested wether ther is a peculiarity. But that's where it ends.
Maybe I don't know about specific techniques for such problems? I hope that I can look at some example solutions (for this and simmilar problems;I would be very grateful if you could post links to similar problems with solutions) and discover a own way to attack such problems.
Maybe you have other advices as well.
problem source: German Mathmatic Olympiade 2010 for 11th graders (PDF)
Warm regards CodeCrafter1
This is a directed graph in which every vertex has out-degree $5$; if we forget the orientation of the edges, then the average degree in the graph is $10$. (Though it's possible for some vertices to have higher degree; maybe every single shower toggles shower #1.)
There's a fairly standard greedy algorithm here, but it's not the obvious greedy algorithm (which doesn't work) so that trips people up.
The key is this: in any set $S$ of showers, there will be a shower $x \in S$ which interacts with (toggles, or is toggled by) at most $10$ showers in $S$. This is just because the subgraph induced by $S$ has $|S|$ vertices and at most $5|S|$ edges (maybe fewer, if a shower in the set $S$ toggles showers outside that set) so the average degree is $10$ or less.
We can start by letting $S$ be the set of all showers, and let $x_1$ be this shower. Then, remove both $x_1$, and all the showers it interacts with, from $S$. We are left with at least $100-11 = 89$ showers.
Let $x_2$ be the shower which interacts with at most $10$ showers in the new $S$. Again, remove both $x_2$ and the showers it interacts with from $S$, and repeat.
We lose $11$ showers at each step, so after $9$ steps we'll still have at least $100-9 \cdot 11 = 1$ shower left to pick.
(The general result of this argument is that a graph with $n$ vertices and average degree $d$ has an independent set of size $\lceil \frac{n}{d+1}\rceil$, which is a restatement of Turán's theorem.)