Until today, I was absoltely sure that "No Free Lunch Theorem" is rather proverb to say "There is no easy way to solve problem in very general case, better results can be obtained only in particular cases".

I'd never expect there is really a mathematical theorem which proves that (for optimization problems):