adversary argument for finding n-bit strings

Question

Given:
S, a set an odd number of n-bit strings
A, a particular n-bit string

show that any algorithm that decides whether A is in S must examine all n bits of A in the worst case.

Usually of course we would expect to have to look at all the parts of a string to do the matching, but there's something particular about S having an odd size that's escaping me.

Answer 1

Let's say we have an algorithm A that decides membership in S correctly and says, for any input n-bit string, whether the string is in S or not.

Suppose for a given input n-bit string s1, the algorithm A never looks at bit i of s1 and goes on to say "s1 is in (not in) S". Then a string s2 equal to s1 except with bit i flipped is also in (not in) S! That is, for any string we feed into A, if A doesn't look at a particular bit, then there is a second string also in (or not in) S with that bit flipped.

Then what is special about odd-sized sets S? We can't pair up strings in S evenly. That is, there must be a string s3 that A looks at and decides is in S, for which no single bit can be flipped to form another string in S. So A must look at all the bits of s3 (otherwise we could make such a string, as we did before).

Answer 2

I guess the odd number clue is to find the end of your set or array in memory.

Assume you are using a 32 bit system, Perhaps the compiler aligns the data structutres of your program in memory on eight byte boundaries. You have a whole load of string pointers in your data segment.If there is an odd number of strings, the next thing that needs an eight byte alignment has four bytes of padding in front of it. If there is an even number of strings, there is no padding.

Answer 3

If i understand this correctly, it's irrelevant whether S has an odd or even number of strings. For any particular string in S to check that it matches arbitrary string A, you must check against each character in each. You can stop early if either string is shorter than the other or a character you're checking doesn't match.