Lesson Library> Number Bases

Number Bases

A PHP Error was encountered

Severity: Notice

Message: Undefined variable: clasis

Filename: views/algebra.php

Line Number: 333

Backtrace:

File: /home/u948765561/domains/eurekaacademy.co/public_html/application/views/algebra.php
Line: 333
Function: _error_handler

File: /home/u948765561/domains/eurekaacademy.co/public_html/application/controllers/FrontAlgebraController.php
Line: 45
Function: view

File: /home/u948765561/domains/eurekaacademy.co/public_html/index.php
Line: 315
Function: require_once

">Repetition of Powers

In this lesson powers will be used a lot. If you never worked with powers before, we recommend you look at the beginner lesson: Exponents & Radicals. Here we just give a quick repetition. Instead of writing repeated multiplication like $7\cdot7=49$ we can write $49$ as a power $7^2=49$. The $7$ is called the base and the $2$ is called the exponent. If a power is multiplied with the base, the exponent is increased by $1$, for instance $7^2\cdot7=7^3$. If a power is divided with the base, the exponent is decreased by $1$, for instance $7=\frac{7^2}{7}=7^1$ and $1=\frac{7^1}{7}=7^0$.

Introduction to Number Bases

There are many different ways to represent numbers. For instance, the Romans represented eight as VIII, while we represent eight as $8$. A system that represents numbers is called a numeral system. An example of a very simple numeral system is when a prisoner counts days by carving a new dot on the wall each day. In this system, a dot means $1$, and all dots are added together. A more practical numeral system is letting the position of the symbols give information. This is the case in the numeral system we normally use today called the decimal system. To see how our decimal system works we look at one example, the number $705$:
$$705= 7\cdot100 +0\cdot10+5\cdot1= 7\cdot10^2 +0\cdot10^1+5\cdot10^0$$
The decimal system uses $10$ digits $0,1,...,9$ and each position in a number is interpreted as a power of $10$. The decimal system is also called base $10$. The choice of using $10$ digits is quite arbitrary. For instance, why not use just $7$ digits $0,1,...,6$ and interpret each position in a number as a power of $7$. We can call this system: base $7$. To emphasise that we work in base $7$ we label numbers with a subscript $7$. A subscript is a small symbol that is lowered slightly. For instance $31_7$ is written in base $7$ and means: $$31_7=3\cdot7^1+1\cdot7^0=22$$
Both base $7$ and base $10$ are number base systems. Another example of a number base system is base $9$ which uses $9$ digits and each position in a number is interpreted as a power of $9$. For instance $31_9$ is written in base $9$ and means: $$31_9=3\cdot9^1+1\cdot9^0=28$$
We are used to add in base $10$. But addition works similarly in all number base systems. We show this with an example.


Example 1

Calculate $14_7+55_7$

Solution

Start by rewriting the expression as: 
$$14_7+55_7=(10_7+50_7)+(4_7+5_7)$$
Add $(4_7+5_7)=4+5=1\cdot7+2=12_7$. Put this in the expression:
$$(10_7+50_7)+12_7=$$
$$=(10_7+50_7+10_7)+2_7$$
Add together $(10_7+50_7+10_7)=7\cdot10_7=10_7\cdot10_7=100_7$.  Lastly put together:
$$100_7+2_7=102_7$$
The answer is $102_7$.


Exercise 1

Calculate $472+29.$

We do this by carrying over digits: 

$$472+29=$$
$$=400+90+11=$$
$$=400+(90+10)+1=$$
$$=400+100+1=$$
$$=501$$
Answer: $501$.


Exercise 2

Calculate $120_3+22_3$ and answer in base $3$.

We do this in a similar way by carrying over digits:
$$120_3+22_3=$$
$$=100_3+(20_3+20_3)+2_3=$$
$$=100_3+110_3+2_3=$$
$$=212_3$$
Answer: $212_3$.


Exercise 3

Calculate $33_5-24_5$ and answer in base $5$.

We get: $33_5-24_5=(30_5-20_5)+(3_5-4_5)=10_5-1_5=4_5.$ Answer: $4_5$.


Exercise 4

Calculate $10_2\cdot11_2$ and answer in base $2$.

Write the expression in base 10: $10_2\cdot11_2=2\cdot(2+1)=2^2+2=110_2.$ Answer: $110_2$.


Exercise 5

Calculate $\frac{610_7}{10_7}$ and answer in base $7$.

Use the fact that $ 610_7=6\cdot7^2+1\cdot7=7\cdot(6\cdot7+1)=10_7\cdot61_7.$ Division by $10_7$ gives the answer $61_7$.


Exercise 6

a) What happens when you multiply $3$ with a number in base $3$?
b) What happens when you multiply $4$ with a number in base $2$?

a) We know $3=10_3$. And multiplying with $10_3$ gives an extra zero at the end of the number.
b) We know $4=2^2=100_2$. And multiplying with $100_2$ gives two extra zeros at the end of the number.


Go between different number bases

Now it's time to learn how to go between different number bases. But first, we need to look at a property in base $10$. Suppose $x$ is an integer that satisfies the inequalities:
$$ 4\cdot10^2 \leq x < 5\cdot10^2 \qquad (*) $$
then $x$ must be a $3$-digit number starting with a $4$. We can also conclude that $(x-4\cdot 10^2)$ has at most two digits. This principle works similarly in other number bases as well. We illustrate this with an example where we want to write $23$ in base $3$. This is done by writing $23$ as a sum on the form: 
$$23=?\cdot3^0+?\cdot3^1+?\cdot3^2+?\cdot3^3+\dots$$ 
where each question mark will be replaced by a digit $0, 1,$ or $2$. Notice that the following inequalities hold:
$$200_3=2\cdot3^2\leq 23 < 3^3=1000_3 $$
Just like in $(*)$ above, this gives information on how $23$ is written in base $3$. The number $23$ is a $3$-digit number starting with a $2$. Now we only need to investigate $(23-2\cdot3^2)=5$ which is at most a $2$-digit number. Because
$$ 10_3=1\cdot3\leq 5 < 2\cdot3=20_3 $$
we know $5$ starts with $1$. Left to investigate is $5-1\cdot3=2$, which is a $1$-digit number. Putting everything together we get: $23=212_3$. It's now easy to go back to base $10$ to check the answer.
$$212_3=2\cdot3^2+1\cdot3^1+2\cdot3^0=18+3+2=23$$
So the conversion from base $10$ to base $3$ worked.

One application

On example where different number bases is used is in calculators. Calculators add numbers in base $2$ (which is called the binary number system). For instance, if you write $17+45$ on your calculator it will first convert $17$ and $45$ to base $2$. Which is $17=10001_2$ and $45=101101_2$. In the next step the calculator add the numbers in base $2$: $10001_2+ 101101_2= 111110_2$. Finally the calculator convert the sum to base $10$, which is $111110_2=62$.


Exercise 1

Write the number $28$ in base $3$.


We see that:
$$1000_3=1\cdot3^3\leq28 < 2\cdot3^3=2000_3 $$

Therefore $28$ is a $4$-digit number starting with a $1$ in base $3$. Only thing left is $28-1\cdot3^3=1$ which is $1$ in all number bases. Putting everything together: $$28=1\cdot3^3+1\cdot3^0=1000_3+1_3=1001_3$$ Answer: $1001_3 .$


Exercise 2

Write the number $7777_9$ in base $10$.

We get:
$$7777_9=$$
$$=7_9\cdot1111_9=$$
$$=7\cdot(9^3+9^2+9^1+9^0)=$$
$$=7\cdot(10\cdot9^2+10)=$$
$$=70\cdot82=$$
$$=5740$$
Answer: $5740.$



Exercise 3

Write the number $667$ in base $9$.

We see that:
$$ 8\cdot9^2=648 < 667 < 9^3 $$
Therefore $667$ is a $3$-digit number starting with an $8$ in base $9$. The rest is done on the fly: $$667-8\cdot9^2=19=2\cdot9+1=21_9$$
Putting everything together: $667=800_9+21_9=821_9.$
Answer: $821_9.$


Exercise 4

Write the number $43_8$ in base $7$.

We convert to base $7$ on the fly:
$$43_8=4\cdot8+3=35=5\cdot7=50_7$$
Answer: $50_7.$


Exercise 5

Write the number $9998$ in base $5$.

We want to use the fact that $9998$ almost equals $10^4$. So start by writing $10^4$ in base 5:
$$10^4=16\cdot5^4=(3\cdot5+1)\cdot5^4=310000_5$$
Use this to write $9998$ in base 5:
$$9998=10^4-2=310000_5-2_5=304443_5$$
Answer: $304443_5.$


Exercise 6

Calculate $54_7+221_3$, answer in base $7$.

Write $221_3$ in base $7$:
$$221_3=2\cdot9+2\cdot3+1=25=3\cdot7+4=34_7$$
Now do the addition:
$$54_7+34_7=$$
$$=(50_7+30_7)+(4_7+4_7)=$$
$$=8\cdot10_7+8\cdot1_7=$$
$$=9\cdot10_7+1_7=$$
$$=12_7\cdot10_7+1_7=$$
$$=121_7$$
Answer: $121_7.$


Exercise 7

Calculate $135_6+44_8$, answer in base $5$.

We do this on the fly:
$$135_6+44_8=(36+18+5)+(32+4)=95=19\cdot5=(3\cdot5+4)\cdot5=340_5$$
Answer: $340_5.$


Using base 2 in a game

It's sometimes an advantage to use base $2$ instead of base $10$. An example of this is a mathematical game called Nim. Nim is a 2-player game. In the game, there exists a certain number of piles of coins. For example, three piles with $5, 7$, and $2$ coins respectively. The two players take turns in removing coins from the game. In each turn, the player chooses one of the piles and removes a positive number of coins from that pile. The removed coins disappear from the game. The player who removes the last coin wins the game.
To get comfortable with the rules, we look at one made up example of the game. Let's say the two players are called A and B, and A will be starting the game. The game starts with three piles with $5, 7$, and $2$ coins respectively. We can denote this by $(5,7,2)$. Let's say player A starts by picking $3$ coins from the pile with $7$ coins. We can denote this move by:
$$ (5,7,2)\overset{\mathrm{A}}{\rightarrow}(5,4,2) $$Using the same notation we can write down all the moves in this made up game.
$$ (5,7,2)\overset{\mathrm{A}}{\rightarrow}(5,4,2)\overset{\mathrm{B}}{\rightarrow}(5,4,1) \overset{\mathrm{A}}{\rightarrow}(5,0,1)\overset{\mathrm{B}}{\rightarrow}(1,0,1)\overset{\mathrm{A}}{\rightarrow}(0,0,1) \overset{\mathrm{B}}{\rightarrow}(0,0,0)$$We see that B removed the last coin, and won the game. Now that we've seen the game Nim in action we're ready for exercises on the game. It can be good to know that some of these exercises are very challenging. We will be given a starting setup for a game of Nim and our job is decide which player is guaranteed to win, given that the player plays perfectly. 


Exercise 1

A game of Nim starts with just one pile with $3$ coins. Who wins?

Of course the player who starts wins. The starting player removes all $3$ coins from the single pile and wins the game.


Exercise 2

A game of Nim starts with two piles with $7$ coins in each. Who wins?

Let the players be named A and B, and assume A starts. There're equally many coins in the two piles. Every move that player A makes in one of the pile, player B can copy by picking equally many coins in the other pile. When player A empties one pile, player B empties the other pile and wins the game. So the player who starts loses.


Exercise 3

A game of Nim starts with three piles with $1, 2,$ and $3$ coins respectively. Who wins?

Let the players be named A and B, and assume A starts. The game starts with piles with $1,2$ and $3$ coins respectively, which we denote $(1,2,3)$. Player A has $1+2+3=6$ possible opening moves. Three of the opening moves is to empty one of the piles, leaving the game with two piles with unequal number of coins:
$$ (1,2,3)\overset{\mathrm{A}}{\rightarrow} (0,2,3), (1,0,3), \text{or } (1,2,0) $$
B can then make these two piles have an equal number of coins. The three cases are:
$$ (0,2,3)\overset{\mathrm{B}}{\rightarrow} (0,2,2) $$ $$ (1,0,3)\overset{\mathrm{B}}{\rightarrow} (1,0,1) $$ $$ (1,2,0)\overset{\mathrm{B}}{\rightarrow} (1,1,0) $$
The other three opening moves for A is not emptying a pile, leaving three piles, two of which have an equal number of coins:
$$ (1,2,3)\overset{\mathrm{A}}{\rightarrow} (1,1,3), (1,2,2), \text{or } (1,2,1) $$
B can then empty the pile which has different number of coins then the other two, leaving two piles with an equal number of coins. The three cases are: 
$$ (1,1,3)\overset{\mathrm{B}}{\rightarrow} (1,1,0) $$ $$ (1,2,2)\overset{\mathrm{B}}{\rightarrow} (0,2,2) $$ $$ (1,2,1)\overset{\mathrm{B}}{\rightarrow} (1,0,1) $$
So regardless of which of the six possible opening moves A chooses, B can then always make a move such that there're only two piles left with equally many coins. According to the argument in the solution of Exercise 2, B will win. So the player who starts loses.


Exercise 4

A game of Nim starts with five piles with $1$, $2$, $3$, $7$, and $7$ coins respectively. Who wins?

Let the players be named A and B, and assume A starts. In this setup we can use what we've learned from Exercise 2 and 3. We can divide the piles into two sets. One set has two piles with $7$ coins in each, we call this set $G$. The other set has three piles with $1,2$ and $3$ coins respectively, we call this set $H$. The idea is that player B will consider this game of Nim as two separate games. Every time player A removes coins from set $G$, then player B should play in the next move as if only the set $G$ exists. From Exercise 2 we then know that player B will remove the last coin in set $G$. And similarly, every time player A removes coins from set $H$, then player B should play in the next move as if only set $H$ exists. From Exercise 3 we then know that player B will remove the last coin in set $H$. Player B will remove the last coin from both sets, and thereby remove the last coin from the entire game and win the game. So the player who starts loses.


Exercise 5

Consider the previous exercises 1,2,3,4 again. Write the number of coins in each pile in base $2$. Guess a rule for when a player will lose the game?
Hint: If you need more inspiration look at the made up game in the text above.

A rule that tells us when someone will lose, must have certain features. In a game with a single pile, the starting player will always win. And from Exercise 4 we realise that adding two piles with equally many coins doesn't change the game. To figure out a reasonable guess for the rule we use the tip and write the number of coins in each pile in base 2:
$$ \text{Exercise 1 (winning):} \qquad 11_2 $$
$$ \text{Exercise 2 (losing):} \qquad \qquad 111_2, \qquad 111_2$$
$$ \text{Exercise 3 (losing):} \;\qquad 1_2,\quad,10_2,\quad 11_2,\quad $$
$$ \text{Exercise 4 (losing):} \quad 1_2,\,10_2,\; 11_2, \; 111_2, \; 111_2 $$
After some trial and error we might test summing the $1_2$-digits from each pile. 
$$ \text{Exercise 1 (winning):} 1 $$
$$ \text{Exercise 2 (losing):} 1+1=2$$
$$ \text{Exercise 3 (losing):} 1+0+1=2$$
$$ \text{Exercise 4 (losing):} 1 + 0 + 1 + 1 + 1 =4$$
We see that the Exercises, where someone is losing, all have an even sum. The same happens to be true also when we sum the $10_2$-digits and sum the $100_2$-digits from each pile. So a reasonable guess for the rule is that someone is losing when the sum of the $1_2$-digits, $10_2$-digits, etc, is even. Notice that adding two identical piles doesn't change if the sums are even or odd, this is something that we required. We also required that the rule worked for a single pile. Which it does because when a positive number is written in base $2$, at least one digit is odd.


Exercise 6

A game of Nim starts with three piles with $7$, $9$, and $14$ coins respectively. Who wins?

Background
This problem has too many coins, to test all possible moves. This makes the problem difficult. When you're faced with a difficult problem, it's often a good idea to look at simpler version of that problem, for instance Exercise 1,2,3,4. Then in Exercise 5 we guessed a rule for when someone will lose the game. Now we test if that guess is correct.


Preparation
In this game of Nim, we've got three piles with $7$, $9$, and $14$ coins respectively. We write the number of coins in each pile in base $2$:
$$ \;\;7=0111_2 $$
$$ \;\;9=1001_2 $$
$$ 14=1110_2 $$ 
We notice that when the game starts the sum of the $1_2$-digits, $10_2$-digits, $100_2$-digits, and $1000_2$-digits, are even. During the game the number of coins will change, so we introduce variables $a,b,c$ for the number of coins in the three piles. Similarly as above, we write $a,b,c$ in base $2$, where the digits are also variables:
$$a=(a_3a_2a_1a_0)_2$$
$$b=(b_3b_2b_1b_0)_2$$
$$c=(c_3c_2c_1c_0)_2$$
Remember that the digits, for example $a_0$, is either $0$ or $1$. Let the players be named A and B, and assume A starts. To test our guess from Exercise 5 we will look at two cases. The first case is when it's players A:s turn and the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, are even. The second case is when it's players B:s turn and at least one the sum of the $1_2$-digits,$\dots$ ,$1000_2$-digits, is odd. 


First Case: Player A:s turn
Suppose, at some point in the game, it's player A:s turn and the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, are even. So the sums:
$$ a_0+b_0+c_0,\quad a_1+b_1+c_1,\quad a_2+b_2+c_2,\quad a_3+b_3+c_3$$
are even. Either all piles are empty and player A has lost. Or the piles are not empty and A must choose a pile. Say player A chooses the pile with $a$ coins and leaves behind $a'=(a_3'a_2'a_1'a_0')_2$ coins in the pile. The numbers $a$ and $a'$ are different and must have at least one digit different. This means at least one of the sums:
$$ a_0'+b_0+c_0,\quad a_1'+b_1+c_1,\quad a_2'+b_2+c_2,\quad a_3'+b_3+c_3$$
is odd. So at least one the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, is odd after A:s move.


Second Case: Player B:s turn
Suppose, at some point in the game, it's player B:s turn and at least one the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, is odd. So at least one of the sums:
$$ a_0+b_0+c_0,\quad a_1+b_1+c_1,\quad a_2+b_2+c_2,\quad a_3+b_3+c_3$$
is odd. We want to show that player B can make these sums even. This is done by first finding the largest integer $n$ such that $ (a_n+b_n+c_n) $ is odd. At least one of the digits $a_n, b_n, c_n$ is $1$. Say for instance that $a_n=1$. Player B then chooses the pile with $a$ coins and and leaves behind some appropriate number of coins $a'=(a_3'a_2'a_1'a_0')_2$ in the pile. Consider an arbitrary digit $a_x'$, for some $x\in\{0,1,2,3\}$. For $x > n$ we know $ (a_x+b_x+c_x) $ is even, so let $a_x'=a_x$. Let $a_n'=0 < a_n$. These choices makes $(a_n'+b_n+c_n) $ even and ensures that $a' < a$. The rest of the digits are chosen such that the sums:
$$ a_0'+b_0+c_0,\quad a_1'+b_1+c_1,\quad a_2'+b_2+c_2,\quad a_3'+b_3+c_3$$
are even. So the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, are even after B:s move.


Conclusion
The game starts with sum of the $1_2$-digits, $\dots$, $1000_2$-digits, being even. So if we look at the First Case, we see that player A is forced to make at least one the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, odd. Now looking at the Second Case, we that that player B can make the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, even again. This puts player A in the original position but with fewer coins in the game. Player B can continue with this strategy until all coins are gone, and B wins (all piles are $0$ means even sum of $1_2$-digits, $\dots$, $1000_2$-digits). So the player who starts loses.


Exercise 7

Now we change the rules in the game Nim. In each turn, the player chooses one or two of the piles and removes a positive number of coins from each chosen pile. A game with these new rules starts with four piles with $8, 10, 11$, and $15$ coins respectively. Who wins?

Background
We start by remembering something about the old game. In the old game someone was losing when $2$ divided the sum of the $1_2$-digits, $\dots$, $1000_2$-digits. This is consistent with the property that we learned in Exercise 4: Adding $2$ extra identical piles don't change the outcome of the old game. 
There's a similar property in this new game were your allowed to choose from one or two piles. Adding $3$ extra identical piles don't change the outcome (do you see why?). And $3$ extra piles won't change if $3$ divides the sum of the $1_2$-digits, $\dots$, $1000_2$-digits. It's therefore a reasonable guess that someone is losing when $3$ divides the sum of the $1_2$-digits, $\dots$, $1000_2$-digits. 


Preparation
In this game of Nim, we've got four piles with $8$, $10$, $11$, and $15$ coins respectively. We write the number of coins in each pile in base $2$:
$$ \;\;8=1000_2 $$
$$ 10=1010_2 $$
$$ 11=1011_2 $$
$$ 15=1111_2 $$
We notice that when the game starts the sum of the $1_2$-digits is $2$, which is not divisible by $3$. During the game the number of coins will change, so we introduce variables $a,b,c,d$ for the number of coins in the four piles. Similarly as above, we write $a,b,c,d$ in base $2$, where the digits are also variables:
$$a=(a_3a_2a_1a_0)_2$$
$$b=(b_3b_2b_1b_0)_2$$
$$c=(c_3c_2c_1c_0)_2$$
$$d=(d_3d_2d_1d_0)_2$$
The sum of the $1_2$-digits, $\dots$, $1000_2$-digits are:
$$ S_0=a_0+b_0+c_0+d_0,\quad S_1=a_1+b_1+c_1+d_1,\quad S_2=a_2+b_2+c_2+d_2,\quad S_3=a_3+b_3+c_3+d_3$$
Let the players be named A and B, and assume B starts. To test our guess of when someone is losing, we will look at two cases.


First Case: Player A:s turn
Suppose, at some point in the game, it's player A:s turn and $3$ divides $S_0, \dots, S_3$. Either all piles are empty and player A has lost. Or the piles are not empty and player A must choose one or two piles. Say player A chooses the pile with $a$ coins and possibly from the pile with $b$ coins. After player A:s move there remains $a'=(a_3'a_2'a_1'a_0')_2$ coins from the first pile and $b'=(b_3'b_2'b_1'b_0')_2$ coins in the second pile. Consider the largest integer $n$ such that: $ a_n' \neq a_n $ or $ b_n' \neq b_n $. We know that $a' < a$ and $b'\leq b$, which implies: 
$$0\leq a_n'+b_n' < a_n+b_n \leq 2 $$
We have assumed that $3$ divides $S_n=(a_n+b_n+c_n+d_n)$. The inequality above then implies that $3$ doesn't divide $(a_n'+b_n'+c_n+d_n)$. So after A:s move, at least one of the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, is not divisible by $3$.



Second Case: Player B:s turn
Suppose, at some point in the game, it's player B:s turn and at least one of $S_0,\dots S_3$, is not divisible by $3$. We want to show that player B can make sure that $3$ divides the sum of the $1_2$-digits, $\dots$, $1000_2$-digits, after the move. Let $n$ be the largest integer such that $3$ doesn't divide $ S_n=(a_n+b_n+c_n+d_n) $. At least one of the digits $a_n, b_n, c_n,d_n$ is $1$. Say for instance that $a_n=1$. Pick the pile with $a$ coins and leave behind some appropriate number of coins $a'=(a_3'a_2'a_1'a_0')_2$ in the pile. Let $a_n'=0$ and for every $x>n$ let $a_x'=a_x$. This ensures that $a'< a$. Assume there exists a largest integer $m\leq n$ such that $(b_m+c_m+d_m)=1$. Either $b_m, c_m, d_m$ is $1$. Say for instance that $b_m=1$. Pick the pile with $b$ coins as a second pile and leave behind some appropriate number of coins $b'=(b_3'b_2'b_1'b_0')_2$ in the pile. If $m$ doesn't exist then let $b'=b$, and the argument will work anyway. Let $b_m'=0$ and for every $x > m$ let $b_x'=b_x$. This ensures that $b'\leq b$. Let's pick the rest of the digits so $3$ divides the sum:
$$ S_x'=a_x'+b_x'+c_x+d_x $$for all $x\in\{0,1,2,3\}$. For $x > n\geq m$ we've already defined $3$ to divide $S_x'=S_x$. For $x=m\leq n$ let $a_m'=0$. This implies that $3$ divides $S_m'$ because: 
$$ S_m'=a_m'+b_m'+(c_m+d_m)=a_m'+b_m'+(1-b_m)=0+0+1-1=0 $$
For $m < x\leq n$, we know $b_x'=b_x$ and $(b_x+c_x+d_x)\neq 1$ from the definition of $m$. It's possible to pick $a_x'=0$ or $1$, so $3$ divides $S_x'$ because:
$$ S_x'-a_x'=b_x'+c_x+d_x=b_x+c_x+d_x=0,2,3 $$
For $x < m$ it's possible to pick $a_x'+b_x'=0,1,$ or $2$, so $3$ divides $S_x'$. Now we've shown that $3$ divides $S_x'$ for all $x$. I.e. the that $3$ divides the sum of the $1_2$-digits, $\dots$, $1000_2$-digits.


Conclusion
The game starts with $3$ not dividing the sum of the $1_2$-digits. So if we look at the Second Case, we see that player B can make $3$ divide the sum of the $1_2$-digits, $\dots$, $1000_2$-digits. Now looking at the First Case, Player A is forced to put player B in the original position but with fewer coins. Player B can continue with this strategy until all coins are gone, and B wins (all piles are $0$ means $3$ divides the sum of $1_2$-digits, $\dots$, $1000_2$-digits). So the player who starts wins.


Problems to Solve

Exercise 1

Which of the numbers $10101_{9}$ or $101_{81}$ is the biggest?

Use the fact that $9^2=81$. We then get:
$$ 101_{81}=81^2+1=9^4+1=10001_9 < 10101_9 $$
Answer: $10101_{9}$ is the biggest.


Exercise 2

 Which number base $x$ satisfies the equation: $331_x=151_x+190_x?$

Start by subtracting $201_x$ from both sides. We get: $$130_x=50_x+90_x$$ Divide both sides by $10_x$. We get $$13_x=5_x+9_x$$ This means that $x+3=5+9$. The solution is $x=11$. Notice that all the digits in the original equation are valid in base $11$, thus the solution $x=11$ is valid.
Answer $x=11$.


Exercise 3

Which of the numbers $2, 3, 6, 7$ divides $500103_{7}$?

We first notice that $7=10_7$ is not a divisor because $500103_{7}$ doesn't end with a zero. We continue to investigate if $6$ is a divisor. We expand our number: $500103_{7}=5\cdot7^5+7^2+3$. Use the fact that $7=6+1$ repeatedly: $$7^5=6\cdot7^4+7^4=6\cdot7^4+6\cdot7^3+7^3=\dots=6k+1$$where $k$ is some integer. We use that result while we expand our number: $$500103_{7}=5\cdot7^5+7^2+3=5\cdot(6k+1)+(6\cdot8+1)+3=5+1+3+6\cdot(5k+8)=9+6\cdot(5k+8)$$ which is divisible by $3$ but not by $2$ or $6$.
Answer: $500103_{7}$ is divisible by $3$, but not by $2,6,7$.


Exercise 4

Is the number $1101100101_8$ divisible by $3$?

Use the fact that $3$ almost divides $8$. More specifically $8+1=3\cdot3$. We expand our number with this in mind: $$1101100101_8=(8^9+8^8)+(8^6+8^5)+(8^2+1)=9\cdot8^8+9\cdot8^5+65$$Because $65$ is not divisible by $3$, neither is $1101100101_8.$
Answer: No, $1101100101_8$ is not divisible by $3$.


Exercise 5

Calculate $11111_2+1$, answer in base $2$.

Notice that $11111_2$ is the biggest $5$-digit number. Thus $11111_2+1$ must be the smallest $6$-digit number, which is $100000_2$.
Answer: $100000_2$.