Splitting Piles

Imagine you divide the cards randomly, and there are $B$ black cards on the left, and $R$ red cards on the right. If $B < R$ , move the division to the right one space. One card will be taken away from the red side and brought to the black side.

If this card is black, then $B$ increases by $1$ , while $R$ remains unaffected. If this card is red, then $R$ decreases by $1$ , while $B$ remains unaffected. Either way, $B$ and $R$ are now closer together by exactly $1$ card. If this process is repeated, $B$ and $R$ will eventually be equal.

If $B > R$ , move the division left instead. The same logic applies, so it is always possible to divide the cards such that $B = R$ .

Proof by induction

Any arrangement of cards may be constructed in a finite number of steps, by starting with one card, and adding cards to the right, one by one. We will show that it always possible to maintain the condition during the building process.

Base step : With one card, if it is black draw the line to the left; if it is red, draw the line to the right.

Induction step : Suppose the situation is $\underbrace{\text{part 1}}_{x\ \text{black}}\ \|\ \underbrace{\text{part 2}}_{x\ \text{red}}.$ We add a card on the right side. There are three cases to consider.

Case I. The new card is black: there is no need to move the line. $\underbrace{\text{part 1}}_{x\ \text{black}}\ \|\ \underbrace{\text{part 2}}_{x\ \text{red}}\ \ B.$

Case II. The new card is red, and part 2 is either empty or starts with a red card. In this case, move the line one step to the right. There will still be $x$ black cards on the left and $x$ red cards on the right. $\underbrace{\text{part 1}}_{x\ \text{black}}\ \ R\ \ \| \ \underbrace{\text{rest of part 2}}_{x-1\ \text{red}}\ \ R.$

Case III. The new card is red, and part 2 starts with a black card. In this case, move the line one step to the right. There will be $x+1$ black cards on the left and $x+1$ red cards on the right. $\underbrace{\text{part 1}}_{x\ \text{black}}\ \ B\ \ \| \ \underbrace{\text{rest of part 2}}_{x\ \text{red}}\ \ R.$

Count cards one by one off the top of the pile; if the magician has x red cards and his assistant has y black cards with x>y, then either: 1. He loses a red card and his assistant gains a red card, making x-1 red cards and y black cards, or: 2. He loses a black card and his assistant gains a black card, making x red cards and y+1 black cards. In either case, we see that we increment x toward y by 1, and eventually can make them equal.

1) Put the division-line on the left side of the arrangement of cards.

2) Count the number of red cards on the arrangement, and call this number N.

3) Move the division-line N places to the right.

In this way the number of black cards in the left side of the division-line is always equal to the number of red cards in the right side. To proof this, count the number of black cards in the left side of the division-line and call this number K. Notice that the number of red cards in the left side is N - K. Next, notice that the number of red cards in the right side is just the total number of red cards minus the number of red cards in the left side, and this is N - (N - K) = K. So we have K black cards in the left side and K red cards in the right side.

Notice that this works even with no cards on the table or with cards only of one color. You can check on the example above that the division-line is exactly after the fourth card and that the total number of red cards is exactly four. Furthermore, this kind of division is unique. This is because moving the line towards one side will increase the K number of one color or decrese it on the other side, always breaking the balance. To get a better intuition put one by one cards on a table and for every red card that appears move the division-line one space to the right, and if a black card appears leave the line in the same place.

Sort the cards : every red on the right and every black on the left. Draw a line between blanc and red cards. Without losing generality, assume there is more red than black. Take red cards to the black side until you satisfy the problem's condition. To get to any random line of cards, it is sufficient to perform permutations of cards, and permutations won't break the problem's conditions.

Here is a symmetric solution, using an invariant.

It involves two dividers $\ell$ and $r$ with invariants:

• $\ell \le r$
• the number of red cards to the left of $\ell$ equals the number of black cards to the right of $r$ .

Initialization puts $\ell$ to the far left, and $r$ to the far right, in which case both counts equal zero.

We are done when $\ell = r$ .

When $\ell < r$ , consider the color of the card immediately to the right of $\ell$ , say $a$ , and the color of the card immediately to the left of $r$ , say $b$ . These cards are between $\ell$ and $r$ . (N.B. It could be a single card, in which case $a = b$ ).

• if $a \ne b$ , then there are at least two cards between $\ell$ and $r$ , and the invariant is preserved by moving $\ell$ one card to the right, and $r$ one card to the left. Either both counts stay the same, or both counts increase by one.
• if $a = b = \mathit{red}$ , then the invariant is preserved by moving $r$ one card to the left (both counts stay the same).
• if $a = b = \mathit{black}$ , then the invariant is preserved by moving $\ell$ one card to the right (both counts stay the same).

So, in all cases, the dividers are moved closer together while preserving the invariant.

Yes, and: The divider will always be as many red cards as you have from the left edge, counting the left edge itself as having 0 red cards in the distribution, regardless of how the cards are laid out.

Consider a random selection of cards and arrange them such that all red cards are to the left of all black cards.

Place the divider between the red and black cards. There are now 0 black cards to the left of the divider and 0 red cards to the right of the divider.

Any swap of two cards will have one of the following effects:

• Two cards on the same side of the divider are swapped, meaning the counts we care about on either side do not change.
• The two cards being swapped across the divider have the same color, meaning the counts we care about on either side do not change.
• We swap a red card from the left to the right with a black card from the right to the left, meaning we increase both counts by 1.
• We swap a red card from the right to the left with a black card from the left to the right, meaning we decrease both counts by 1.

...in all instances, both counts remain the same.

Any arrangement of the cards we have can be reached by making a finite number of 2-card swaps. (See Bubble Sort or any sorting algorithm from computer science.)

Thus, if we pick a random arrangement and keep our divider in the prescribed position (as many cards to the left of the divider as there are red cards in the selection), we will have as many black cards to the left of the divider as we have red cards to the right.

Let the number of cards be equal to n . Now,let's say n is the number of bits in a binary number. Let black card be denoted by 1 and red card be demoted by 0 . We have to prove solution exist for one and two bits of binary number i.e. solution exist for 0,1,00,01,10,11. 0=>|0 1=>1| 00=>|00 01=>0|1 10=>1|0 11=>11|

Since the solution exists for two bit numbers which are created by concatenating one bit number in any manner we can prove the solution exists when we concatenate the above numbers in any manner and any number of times,to get any possible number in binary. We considered one bit number to create numbers with odd number of bits.