We are given collection of sets $A = \{A_1, \dots A_k\}$, where each set $A_i \subset \{1,\dots n\}$.
Colouring $\{1, \dots n\}$ into $s$ colours would be called 'rainbow' for given $A$, if $\forall A_i$ contains at least one element of each colour.
We are also given that $|A_i| = s^2$ and $\forall x \in \{1,\dots n\} : x$ contained by no more than $s$ subsets of $A$.
Task is to prove that for $s > 100$ exists $s$-colour rainbow colouring for $A$.
Any hints would be appreciated.
Edit
After sitting on in a bit more, the problem boils down to the $s^2$-uniform hypergraph rainbow colouring.
Now problem looks much more managable.
Our graph is $H(\{1,\dots, n\},E)$ and have following constraints:
$E = A$, $\forall e \in E: |e| = s^2$,
$\forall x \in \{1, \dots n\} : deg(x) \le s$
After that, we are able to put upperbound on the $|E|$:
$\sum_{x = 1}^n deg (x) = 2|E| \Rightarrow |E| \le \frac {ns} 2$
Also I noted a naming conflict. Mostly rainbow colouring of hypergraph is defined in papers as a colouring, when all elements of hyperedge have different colours.
I spent a while googling it, but I failed to find commonly known name for my colouring.
We will stick to the hypergraph iterpretation of the problem.
Let $\xi_i$ - indicator random variable.
$$\xi_i = \begin{cases} 1, & \text{i-th hyperedge contains < s colours}\\ 0, & otherwise \end{cases}$$
Then, $\cup_{i=1}^m \xi_i$ is a variable which describe chance of least one hyper edge to have $< s$ colours
and $\overline{\cup_{i=1}^m \xi_i} = \cap_{i=1}^m \overline{\xi_i}$ - describes chance of all hyperedges having elements of all $s$ colours.
Now, formulate Lovasz symmetric local lemma.
Each variable $\xi_i$ depends on $\le d$ variables, $p = P(\xi_i=1)$ and if $ep(d+1) \le 1$ then $P(\overline{\cup_{i=1}^m \xi_i}) > 0$.
For our case, $p = s (\frac {s-1} {s})^{s^2}$. for every colour of $s$, we find probability of colouring $s^2$ elements in any colour but the current.
Value of $d = (s-1)s^2$.
Then $es^3(s-1) (\frac {s-1} {s})^{s^2} \le 1$ definitely holds for $s>100$.
Hence, colouring exists.