0 / 0
1 / 1
2 / 10
3 / 11
4 / 100
5 / 101
6 / 110
7
8
9
10
11
12
13
14
15
16
Binary Basics
1.Imagine that you can only count with the digits 1 and 0, how would you be able to add, subtract or do anything else that you normally do with numbers whose digits go from 1 to 10?
A computer can only store information as a 0 or a 1 but it can store lots of these. E.g. the number 123 is stored as 1111011 on the computer.
We call these binary numbers.
Decimal number / Binary number2 / 10
4
8
16
32
64
128
256
2^n
a) Look at the table to the right. Can you figure out what the next numbers in the Binary number column are?
b)
b) powers of two
c) backwards conversion: binary number: 1001, 1111, 10001, 10010.
d)Find a rule for how to convert numbers from decimals to binary.
1,000, 2,000,
e) Addition – directly without/with carry over – convert to check, then convert back. 2000+13=2013. WHY DOES IT WORK? ....
f) How can you write the sum 1+2+2^2+...+2^n in a shorter formula?
Solution:
c) Hint: which number would come directly before or after it?
1001_2=1000_2+1=2^3+1=9
1111_2 comes immediately before 10000_2=2^4=16, so 1111_2 =15.
10001, 10010,
2. A programmer at a party exclaims: there aren't so many people here: I could count us all on the fingers of one hand. How many people were at the party?
3. Guessing game :(
6) Suppose I have four boxes with numbers (between 1 and 15) inside them.
A: 1; 3; 5; 7; 9; 11; 13; 15
B: 2; 3; 6; 7; 10; 11; 14; 15
C: 4; 5; 6; 7; 12; 13; 14; 15
D: 8; 9; 10; 11; 12; 13; 14; 15
If you pick a number between 1 and 15 and tell me all of the boxes it is in, I can tell
you the number (try this if you want!). How do I do it?
This game is a bit lame anyway: if I construct the intersection graph of the sets, it has 4 +6+4 =14 vertices, edges, 2d faces and 1 number on each. No wonder... We could however construct such a 3d object and ask the kids to discover the rules by which the numbers are assigned.
a) Describe a rule for the vertices
b) Describe a rule for the numbers on the edges (in relation to the adjacent vertices...)
c) Describe a rule for the numbers in the middle of the faces
d) For each vertex, write down all the numbers adjacent to a vertex (that is, on an edge or a face containing that vertex. Describe a rule for each of these sets.
- Nim with counters:
Nimis amathematicalgame of strategy. There are many variants but the main game goes like this: two players take turns removing objects from distinct heaps: On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The player who gets to remove the last object wins.
Assume that the two players are very smart: if there is a winning strategy that allows a player to win, he/she will win.
In which of the following cases can the 1st player win:
1, 1 - lose
1, 2,
1, n, n>1
2, 2 - lose
2, n n>2
3, 3 - lose
4, 4 - lose
4, n n>4
1, 1, n
1, 2, 2,
1, 2, 3 – lose (122-22, 121-11, 12-11, 23-22)
1, 2, n n>3
1, 3, n, n>2
1, 4, 4
1, 4, 5 - lose (144-44, 143-123, 142-132, 141-11, 140-11, 135-132, 125-123, 115-11, 105-11, 45-44)
1, 4, n
1, 5, n n>4
2, 2, n n>1
2, 3, n n>1
2, 4, 6 -- lose (245->145, 244->44, 243-213, 242-22, 241-231, 24-22, 236-231, 226-22, 216-213, 26-22, 146-145, 46-44)
2, 5, 7 –lose (256-246, 255-55, 254-154, 253-213, 252-22, 251-231, 25-22, 247-246, 237-231, 227-22, 217-213, 27-22, 157-154, 57-55)
1, 1, 1, 1 – lose
1, 2, 3, n
1, 1, 2, 2 – lose
1, 1, 2, n
1, 2, 4, 7 -- lose
Include about as many losses as wins
CHALLENGE: Take all the numbers on an edge, or a face of the binary tetrahedron and play the nim game with piles of those sizes: e.g. 1, 2, 4, 7.
Is the game biased? Can you explain why? Can you come up with a general rule as to when games might be biased toward certain player?
Can you come up with a general strategy for winning a game?
Ternary (base 3) with digits 0; 1; 2.
- Conversion tables
- Algorithm for conversions
- An addition and conversions
- 222...... 2+1? Write this equation in decimals.
- Weighing game: you are given weighing scales like in the picture and exactly 4 weights of 1, 3, 9 and 27kg.
a) Using these, can you make the following measurements: (i) 2kg (ii) 6kg (iii) 18kg (iv) 24kg
b) What are all the possible weight measurements you can make with the above?
Solution: a)2=3-1. If we place the 3kg weight on the right scale, and the 1kg weight together with the quantity to be measured on the left scale, we can measure 2kg.
Similarly, 6=9-3, 18=27-9, 24=27-3
b) The largest weight we can measure is 1+3+9+27=40. This is 1111_3. All the numbers between 1 and 40 written as ternary numbers are 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, ...., 1111. We need to write them using only the ternary numbers 1, 10, 100 and 1000, each at most once, and the operations + and -.
We already saw how the ternary numbers 2=10-1, 20=100-10, 200=1000-100. We can add any combination of these, and also with 1, 10, 100. The resulting expressions get to use the ternary numbers 1, 10, 100 and 1000, each at most once, with + and -.
For example, 121=100+20+1=100+100-10+1=200-10+1=1000-100-10+1 which in decimal numbers shows 16=27-9-3+1.
1022=222+100=1000-1+100 translates in decimals: 35=27+9-1.
Finally, ternary numbers like those between 1100 and 1111 are formed by adding 1, 10, 100 and 1000, each at most once.
Other bases: Octal
Octal (base 8) with digits 0; 1; 2; 3; 4; 5; 6; 7.
Hexidecimal (base 16) with digits 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; A; B; C; D; E; F.
Because 8 and 16 are powers of 2, they are also convenient ways to package information stored in computers.
1. a) Conversion: decimal to octal to binary to hexa.
b) Explicit conversion to octal and explanation: 2013.
c) Addition in octal with check in decimal.
d) What is 77777777777777+1 in octal? Translate the equation in decimal.
Why do programmers always mix up Halloween and Christmas?
A:Because Oct 31 == Dec 25!
Link to hexa colour codes:
Also see
Babilonian numerals
Other bases
1. An evil king wrote three secret two-digit numbers a; b; c. A handsome prince must
name three numbers X; Y; Z, after which the king will tell him the sum aX + bY + cZ.
The prince must then name all three of the King’s numbers, or he will be executed.
Help out the prince!
Can you write a shorter formula for 5(1+6+6^2+...6^n)? 6 (1+7+7^2+...+7^n) ? Can you factor X^n -1?
Prove that from the set of numbers 0, 1, 2, ..., 3^k -1 written on the number lines, one can choose 2^k such that no point chosen is found at equal distances from two other points chosen.
-- Cantor's set? Sierpinski's carpet?
is an integer whose representation in baseisFind the smallest positive integerfor whichis the fourth power of an integer.
Last problem here:
Having been abducted by aliens from the exoplanet Xari, after an extraordinary journey I was confronted by an extremly angry court martial which accused my species of priding itself with excessive knowledge of prime numbers. There was only one way to redeem myself and that was to determine whether ... is a prime number: a question they have been stumped with for quite too long.
The question seemed simple enough, however I was terrified of getting it wrong, because I had no idea what number base they were using!
Still, after thinking for a minute, I confidently stated that it isn't, as 2323=23\times 101.
They were happy with the answer so they let me go.
a) Was I just plain lucky, or does this work in any number basis? Read left-to-right or right-to-left?
b) Are these numbers primes on Xari: 1224, 1001, 2332? I still have no idea of the number basis, on Xari, but the numbers above exist there as such.
Find a polynomial with nonnegative integer coefficients such that P(2)=2013 and P(1)=9. Are there more than one solution?
Suppose P(x) is an unknown polynomial, of unknown degree, with nonnegative integer coefficients. You have access to an oracle that, given an integer n, spits out
P(n), the value of the polynomial at n. However, the oracle charges a fee for each such
computation, so you want to minimize the number of computations you ask the oracle
to do. Show that it is possible to uniquely determine the polynomial after only two
consultations of the oracle.
Weighing game: you are given weighing scales like in the picture and exactly 7 weights of 1, 1, 5, 5, 25, 25 and 125kg. What are all the possible weight measurements you can make with these?
Fomin, S. Genkin, I. Itenberg “Mathematical Circles (Russian Experience)”
Cut-the-Knot website