More questions on binary numbers

Question

I host a Mathematics workshop and I love to work with problems that bring out unexpected lessons.

I hope to design a lesson on number bases. I found Josephus' problem as an interesting activity to start with.

Are there more problems that start out as having nothing to do with number bases but bring out the use of number bases later? Any place that lists them would be cool too.

Answer 1

I'm sorry this is in french, you'll find a great explanation of how to count in base 4 below.

The shaddoks have only four words (and also only four symbols) : "GA" "BU" "ZO" and "MEU". For them, counting to five is rocket science, until one of them decides that GA equals $0$.

Here's the idea of Professor Shadoko :

• If there is no shadok, one writes GA.
• If there is one shadok, one writes BU.
• If there is two shadoks, one writes ZO.
• If there is tree shadoks, one writes MEU.
• If there is four shadoks, one puts them into a bin. Now there is one (BU) bin and zero (GA) shadoks and one writes BU GA.
• five shadoks is one bin plus one shadok : BU BU, six is BU ZO, seven is BU MEU.
• eight shadoks is a bin and four shadoks, we can fill a new bin! Now we have two (ZO) bins and no shadok left, and we write ZO GA
• ...
• When we have four bins, one put all bins in a super-bin. Sixteen shadoks is a super-bin and no extra bin and no extra shadok : BU GA GA.
• Of course, if you have four super-bins, you put them in a super-super-bin etc.

Answer 2

Themes directly connected to numeration bases :

• Sierpinski's triangle (see the amazing site http://www.oftenpaper.net/sierpinski.htm) with "depth" $n$. This triangle can be constructed in many ways, two of them at least use bases :

a) triangles coding with a sequence of numbers with $n$ digits in base 4, keeping those that do not contain digit $3$, or

b) (discrete version) using Pascal triangle modulo 2. (in connection with the very nice Lucas Theorem (https://en.wikipedia.org/wiki/Lucas%27s_theorem)).

c) The "Towers of Hanoi" puzzle of Lucas (him again !). See here, with elaborate coding of states, and an unexpected graphical representation in connection with Sierpinski triangle...

See as well this recent paper with connection to Apollonian gaskets, a fascinating subject as well. A more intricate version can be found here.

Fig. 1 : Possible states and moves for "Tower of Hanoi" puzzle with 2 disks (issued frome the Wikipedia reference).

• In the same vein, the "3 Jugs puzzle".

• The rotating drum problem (http://mathonline.wikidot.com/the-rotating-drum-problem), once used for coding wheels : see figure below borrowed to this article. This is the tip of a big iceberg :

• The "De Bruijn sequences of order n on a size-k alphabet" using numeration base k and any number of digits n. Reference : https://en.wikipedia.org/wiki/De_Bruijn_sequence. See also this recent extension https://arxiv.org/pdf/1505.04065.pdf. See as well an answer of mine in an interesting issue about a jigsaw puzzle Proving a jigsaw is possible. There are different ways to generate such sequences, using for example matrices associated with irreducible polynomials in Galois fields, particular (recurring) decimal extensions, etc.

Fig. 2 : "Rotating drum" able to generate every number with a binary representation of 6 bits (from '000000' to '111111') by selecting 6 consecutive digits on the drum (De Bruijn sequence $B(6,2)$).

• Different algorithms like "exponentiation by squaring"

• Solving "Lights out" puzzle via base 2 computations :

https://www.xarg.org/2018/07/lightsout-solution-using-linear-algebra/, https://math.stackexchange.com/q/3029158

• Gray codes (https://en.wikipedia.org/wiki/Gray_code) and issues related to it like this challenging question.

• non-conventional bases: http://datagenetics.com/blog/december22015/index.html lists some of them, for example

a) Base (-2) (signed binary) a particular case of negative bases (https://en.wikipedia.org/wiki/Negative_base) studied in particular by Knuth.

b) Base (1+i) in which you can understand the "dragon curve" (https://www.math.uwaterloo.ca/~wgilbert/Research/MathIntel.pdf)

c) Basis $e$ (see for that the interesting answer of Benjamin Dickman to a question of mine (Looking for examples of Discrete / Continuous complementary approaches)),

• On the side of algebra, some formulas like this one :

$$(1+x)(1+x^2)(1+x^4)\cdots(1+x^{2^{n}})=\sum_{k=0}^{2^{n+1}-1}x^k$$

whose proof is a direct consequence of the unicity of binary decomposition of any integer $k$.

• Besides, don't miss the (more general) book "The Penguin Dictionary of Curious and Interesting Numbers" by David Wells : https://proofwiki.org/wiki/Book:David_Wells/Curious_and_Interesting_Numbers#David_Wells:_The_Penguin_Dictionary_of_Curious_and_Interesting_Numbers with plenty interesting things for a mathematics' club.

• see the nice presentation here including in particular the game of Nim.

• curious facts like this one : MGFs and a string of 9's in a particular number.

• (not directly connected with bases but helpful) Have a look at tools like spirograph in order to gain intuition about LCM and GCD and see nice figures ! See the amazing simulation in https://nathanfriend.io/inspirograph/. See as well the versatile mode of generation of curves that can be found [here}(https://math.stackexchange.com/q/3531556)

Answer 3

First some pedantry. Binary is an alternative way to represent numbers rather than a different type of number. The numbers will have the same properties (e.g. commutative addition, primeness, etc), they will just be written differently. Many people use calculators and computers to perform arithmetic without knowing or caring that binary is probably being used inside.

An alternative base that I find different and amusing is Balanced Ternary. As the name suggests it uses three symbols but $0, 1, -1$ rather than the $0, 1, 2$ of regular ternary. It is convenient to use a single symbol for $-1$ otherwise expressions become ambiguous and confusing. It is not used often enough to have a well agreed symbol but I will use $\bar 1$. Sometimes $T$ is used as an approximation to this and sometimes an upside down $1$. So, how do you represent $2$? A little thought leads to $1 \bar 1$ which is one of the base ($3_{10}$) less $1$.

There are a number of uses but here is a simple and amusing one. Consider a simple old style weighing scales with two identical pans. You can place objects into the pans and read off whether they are equal in weight. You need to choose a set of $n$ weights which allow you to weigh the greatest range of whole number weights starting with $1$. Many people will jump to a powers of $2$ set e.g. $1, 2, 4, 8, 16$. This is quite good but you can do better by realising that you can place a weight in the same pan as the sample as well as the other pan. This allows negative weights. Now just $1$ and $3$ allow you to weigh $1, 2, 3, 4$ which is a bit better than $1, 2$. As the set gets bigger, the benefit increases. Try $1, 3, 9, 27, 81$ against the $5$ piece binary set just mentioned. Now if you label the weights in balanced ternary $1, 10, 100, ...$ and read those in the sample pan as negative $\bar 1, \bar 10, \bar 100, ...$ then the weights display the sample weight in balanced ternary.