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)
“I can’t quite define my aversion to asking questions of strangers. From snatches of family battles which I have heard drifting up from railway stations and street corners, I gather that there are a great many men who share my dislike for it, as well as an equal number of women who ... believe it to be the solution to most of this world’s problems.”
—Robert Benchley (1889–1945)