The bound isn’t always achievable if you don’t know Y. Suppose X,Y∈{1,2,3} with X≠Y uniform over the 6 possible outcomes. You find out that X=1 (without loss of generality). You must construct a function S st S(2)=S(3)=1. Because as far as you know, Y could be 2 or 3, and you have to be able to construct X from S and Y. But then we just take the most common output of S, and that tells us X=2 so Y≠2.
(If you had some other procedure for calculating X from S and Y, then you can make a new function that does that, and call it S, so an arbitrary function from X to Y+{err} is the most general form of S.
The bound isn’t always achievable if you don’t know Y. Suppose X,Y∈{1,2,3} with X≠Y uniform over the 6 possible outcomes. You find out that X=1 (without loss of generality). You must construct a function S st S(2)=S(3)=1. Because as far as you know, Y could be 2 or 3, and you have to be able to construct X from S and Y. But then we just take the most common output of S, and that tells us X=2 so Y≠2.
(If you had some other procedure for calculating X from S and Y, then you can make a new function that does that, and call it S, so an arbitrary function from X to Y+{err} is the most general form of S.
Nice argument—I’m convinced that the bound isn’t always achievable. See my response to cousin_it’s comment for some related questions.