Let $n\in\mathbb N$. Then a binary string of length $n$ has the form $a_1a_2...a_n$ such that each $a_i$ is either 0 or 1. Define $E_n$ to be the set of all binary strings of length $n$ with even number of 1's, and define $O_n$ to be the set of all binary strings of length $n$ with odd number 1's.
Define a bijection $f: E_n \to O_n$.
Now, I'm really confused as to how to apply the idea of a bijection in an example like this and I'm not sure how to start. Any help would be appreciated..
On
Hint: Start with the case that $n$ is odd, and think about what happens if you simply flip all the 0's to 1's and flip all the 1's to 0's.
On
Hint:
Case1: $n$ is odd. Let's say you have $k$ number of $1's$ where $k$ is even. Then send this string to the string obtained by "flipping" $0's$ and $1's$. This has $n-k$ (which is odd) number os $1's$. Check that this is a bijection.
Case 2: $n$ is even. Let's say you have $k$ number of $1's$, with $k$ even. If the left most $a$ is $1$ then consider the string $a_2a_3 \cdots a_n$. This has length $n-1$ (which is even) and $k-1$ number of $1's$ (which is odd). Apply the inverse of the bijection from previous part.
If $a_1=0$ then you have $a_2a_3 \cdots a_n$ a string of length $n-1$ (even) with $k$ number of $1's$. Apply the previous case.
Easiest answer as I see it: flip $a_1$. This is a bijection as the inverse function is given by flipping $a_1$.