while solving a computer science problem, I came up with this question. I would like to find an algorithm to, given a number with n bits, I remove a bit such that the number formed by the other n-1 bits (in the same order) tell us whether the removed bit is a 0 or an 1.
For instance, if n = 7, if it is given the number 0110101, I must be able to choose a bit such that the remaining number tells me if the removed bit is a 0 or an 1. If the number 010101 corresponds to an 1, then I can remove the second (or the third) bit from 0110101 and, with the remaining number (010101) i would know that I removed an 1.
If I found a correspondence between each number of n-1 bits and a 0 or a 1 such that for every n-bit number I am able to remove a bit that is the correspondent of the remaining (n-1)-bit number, I would have the problem solved, but I still couldn't find such a correspondence. May anyone if there is such a correspondece and what is the correspondence, please?
There does not exist a unique "correspondence" between all n-bit numbers and all n-1 bit numbers. So the algorithm in question cannot exist with the given parameters.
Observe: (My apologies for the notation. I'm just getting started on stack overflow and have yet to learn how to use nice symbols [specifically those used in set theory would have been helpful])
Let A be the set of all n-bit numbers. Let X be the set of all n-1 bit numbers which are obtained by removing a 1 from all elements in set A. Let Y be the set of all n-1 bit numbers which are obtained by removing a 0 from all elements in set A.
Now, suppose we have an n-1 bit value b. We would like to determine whether b belongs in the set X or the set Y, and note that it cannot be in both (your algorithm). The only way this would be able to work is if the intersection of X and Y is empty.
So, we can prove that the intersection of X and Y is not empty by showing that there exists some n-1 bit value z where z is an element in X and z is an element in Y.
Let z be the n-1 bit number 11010. To obtain z in X we start with the n-bit value in A 110110, then we remove a 1 to obtain 11010 (which is z), which by our definition of set X it belongs in set X. So, z=11010 is an element of X.
Let z be the n-1 bit number 11010. To obtain z in Y we start with the n-bit value in A 110010, then we remove a 0 to obtain 11010 (which is z), which by our definition of set Y it belongs in set Y. So, z=11010 is an element of Y.
Since we can see that there exists a value z which is an element of X and an element of Y, we can see that the intersection of X and Y cannot be empty. Therefore, the algorithm in question cannot exist as there is no unique relation.