The tag has no wiki summary.

learn more… | top users | synonyms

9
votes
2answers
371 views

Parity of $\lfloor 1/(x y) \rfloor$ not equally distributed

A curious puzzle for which I would appreciate an explanation. For $x$ and $y$ both uniformly and independently distributed in $[0,1]$, the value of $\lfloor 1/(x y) \rfloor$ has a bias toward odd ...
10
votes
3answers
994 views

Proofs of parity results via the Handshaking lemma

I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency). Let me ...
6
votes
2answers
872 views

How hard is it to solve SAT if the promise is that it has an odd number of solutions?

SAT is NP-complete even if we promise that it has an even number of solutions (by introducing a new dummy variable). However, USAT (when the promise is that it has exactly one solution) is not known ...