I'm not sure if I've been able to clearly state my problem here, but here's the extensive problem description:
We have an array of $n$ numbers, and another given number $d$, one step at a time, we are authorized to add $1$ to any number in the array. The question is simple, what is the minimum number of steps in order to make sure that the sum of all subsets of length $d$ of the given is even?
I am not sure where to begin. Any hint is appreciated.
For instance:
For $n = 5, d = 3$ and the array itself being $1,3,0,5,2$, I just need to add one to the last index of my array [the "2"], so the answer is $1$.
Here are some observations which may help.
The minimum number of steps depends on the specific array you are given, of course. Call the elements of the array $a_1, a_2 \dots a_n$
If $d=1$ you simply have to flip all the odds to evens, and all the numbers might start off odd.
If $d\gt 1$ and the sum of the first $d$ elements is even, consider the sum from $a_2$ to $a_{d+1}$ - this must be even too, and therefore $a_1$ and $a_{d+1}$ have the same parity. You therefore can split your array into $d$ subsets depending on their position modulo $d$ in the array.
Can I suggest two questions.
How can you economically change all these subsets so the elements of each subset have the same parity?
And if you do this as economically as possible, you might end up with all the sums odd instead of even. How much do you need to lose to make the sums even?
For the first question, the number of changes you need to make in each of the subsets to make every element the same parity in each subset is $\le$ half the number in each subset. So adding all these up you can meet the parity constraint with $\le \frac n2$ changes
Then for the second question you can think as follows.
If you have succeeded with $\frac n2$ changes, well and good. Otherwise all your sets of length $d$ sum to odd numbers. Changing the parity of just one of the subsets will fix that, because each subset hits each sum just once.
Now examine the situation in more detail. The subset $s_r$ corresponding to the original elements in positions $\equiv r \bmod d$ originally consisted of $o_r$ odd numbers and $e_r$ even numbers, and had a total of $t_r=o_r+e_r$ members. We gave them all the same parity by changing $c_r=\min (o_r, e_r)\le \frac {t_r}2$ of these. Suppose that $s_p$ is the set for which we made the most changes (max value of $c_p$), and if relevant, that amongst these sets we choose one for which $t_p$ is least. We changed $c_p$ elements to make them all odd, but we could instead have changed $t_p-c_p$ to make them all even. Now let $t_p-c_p=c_p+2f$ so that $c_p+f=\frac {t_p}2$.
Then we have, for $q\neq p$, $2c_q+2f=2c_q+t_p-2c_p\le 2c_q+t_q-2c_q=t_q$ and $c_q\le \frac {t_q}2-f$.
By changing to make everything even, we've had to make $2f$ more changes in set $s_p$, and $f$ more changes than would have brought us to exactly half the set. But in each of the other sets we were already $f$ short of half the elements, so provided we have at least one, i.e. $n\ge 2$, our total number of changes will remain $\le \frac n2$.
You can't do better than $\frac n2$ because if $n$ is even you can just choose the first half equal to zero and the second half equal to $1$.
Note that if $d\gt \frac n2$ you will only have to change at most $n-d+1\le \frac n2$ numbers at most.