Now lets allow entangled states between the kids (states that can only be specified if you have both subsystems, locally if you measured such a state your result will look at least a bit random or even completely random). Then you can prove that the two kids can do the task (that has classical success probability 75%) with success probability ~85% all of a sudden.
You can write down general inequalities that describe such behaviour and that's what Bell inequalities are. The fact that entangled states in quantum mechanics violate the classical bound (which you cannot break if you demand your two kids can only share states allowed by classical physics, even if you allow unspecified hidden variables), proves that nature is not classical. It doesn't prove that nature is quantum, it just proves that nature is not classical. Bell inequalities have also been unambiguously experimentally verified [1].
In conclusion, nature allows for two-party (or multi-party) states that cannot be described by just describing the local parts of it. There is no information in the local parts, but if you look at both parts together then there is information. Think "the whole is more than the sum of its parts". Classically, the whole is the sum of its parts. Classically, you read a book page by page. If your pages are entangled with each other, you could only read your book by looking at all pages together, because if you looked a single pages separately anything written there would look like random garbage to you.
The question that remains is: Where is the information then, physically? In some sense you could say it does not exist before measurement, because only when you look at the correlations between the local measurement results of the two kids will you find out that the underlying state must have been entangled (which you get to know if the state violates a Bell inequality). But that is just one possible interpretation, there still is a lot of scientific debate about what quantum mechanics really means.
These are exactly the scenarios that make quantum so weird but fascinating at the same time.