  The Kochen-Specker (KS) theorem is a cornerstone result in quantum
foundations, establishing that quantum correlations in Hilbert spaces of
dimension $d \geq 3$ cannot be explained by (consistent) hidden variable
theories that assign a single deterministic outcome to each measurement.
Specifically, there exist finite sets of vectors in these dimensions such that
no non-contextual deterministic ($\{0,1\}$) outcome assignment is possible
obeying the rules of exclusivity and completeness - that the sum of value
assignments to any $d$ mutually orthogonal vectors be equal to $1$. Another
central result in quantum foundations is Gleason's theorem that justifies the
Born rule as a mathematical consequence of the quantum formalism. The KS
theorem can be seen as a consequence of Gleason's theorem and the logical
compactness theorem. Notably, Gleason's theorem also indicates the existence of
KS-type finite vector constructions to rule out other finite alphabet outcome
assignments beyond the $\{0,1\}$ case. Here, we propose a generalisation of the
KS theorem that rules out hidden variable theories with outcome assignments in
the set $\{0, p, 1-p, 1\}$ for $p \in [0,1/d) \cup (1/d, 1/2]$. The case $p =
1/2$ is especially physically significant. We show that in this case the result
rules out (consistent) hidden variable theories that are fundamentally binary,
i.e., theories where each measurement has fundamentally at most two outcomes
(in contrast to the single deterministic outcome per measurement ruled out by
KS). We present a device-independent application of this generalised KS theorem
by constructing a two-player non-local game for which a perfect quantum winning
strategy exists (a Pseudo-telepathy game) while no perfect classical strategy
exists even if the players are provided with additional no-signaling resources
of PR-box type (with marginal probabilities in $\{0,1/2,1\}$).
