Classical Solution
Solving the 2-to-1 version deterministically requires queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires queries.
This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. Thus, queries suffice. If we are unlucky, then the first queries could return distinct answers, so queries is also necessary.
If we allow randomness, the problem is easier. By the birthday paradox, if we choose (distinct) queries at random, then with high probability we find a collision in any fixed 2-to-1 function after queries.
Read more about this topic: Collision Problem
Famous quotes containing the words classical and/or solution:
“Several classical sayings that one likes to repeat had quite a different meaning from the ones later times attributed to them.”
—Johann Wolfgang Von Goethe (1749–1832)
“Who shall forbid a wise skepticism, seeing that there is no practical question on which any thing more than an approximate solution can be had? Is not marriage an open question, when it is alleged, from the beginning of the world, that such as are in the institution wish to get out, and such as are out wish to get in?”
—Ralph Waldo Emerson (1803–1882)