There is a simple and elegant solution for the case of 3 people (i.e. part 1), which doesn't require much formal math. However, this is not the case for more than 3 people. The solution requires using the error correct coding theory, specifically, the distance-3 Hamming code.

However, there is a simple and elegant proof for the upper bound without using much formal math, i.e. it's impossible to come up with a strategy with winning probability > 1 - 1 / 2^k.