The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2023: Arithmetic of Power Monoids

G
Topic
First Poster
Last Poster
Exercise 3.2
smileapple   6
N Jun 15, 2023 by felixgotti
& here's a solution to Exercise 3.2. as usual, pls let me know if there are any errors in my reasoning
Problem: Construct a monoid that is almost atomic but not nearly atomic.
-----
-----
Solution: Let $S$ contain the reciprocals of the powers of $2$; that is $$S=\left\{\frac12,\frac14,\frac18,\frac1{16},\cdots\right\}.$$Now let $$M=\left\langle S\cup\left\{\frac13\right\}\right\rangle.$$In other words, if $b\in M$, we can write $$b=\left(\frac{p_1}2+\frac{p_2}4+\frac{p_3}8+\frac{p_4}{16}+\cdots\right)+\frac{r}3.$$-----
Now we determine $\mathcal{A}(M).$ Clearly, if $a\in\mathcal{A}(M),$ it must be in the generating set of $M$; that is, either $a=\frac{1}{2^q}$ or $a=\frac13.$ However, the former case is invalid, as $a=\frac{1}{2^q}=\frac{1}{2^{q+1}}+\frac{1}{2^{q+1}}.$ It is easy to see that the latter case works. Thus $\mathcal{A}(M)=\left\{\frac13\right\}.$
-----
Note that the some of the $\frac{p_i}{2^i}$ on the right hand side must terminate at some point; for instance, we cannot say that $$\frac17=\frac18+\frac1{64}+\frac1{512}+\frac1{4096}+\cdots$$is in $M$; we can only conclude that there exist an infinitude of elements in $M$ that approach $\frac17.$ Under this logic, it follows that there must exist some $q$ such that $p_i=0$ for all $i>q.$ We can thus write $$\frac{p_1}2+\frac{p_2}4+\frac{p_3}8+\frac{p_4}{16}+\cdots+\frac{p_q}{2^q}=\frac{p}{2^q}$$for some $p\in\mathbb{N}.$ Thus, if $b\in M$, then we can write $$b=\frac{p}{2^q}+\frac{r}3.$$It is easy to see that all elements of this form must work as well.
-----
We claim that $M$ is almost atomic. Specifically, for $b=\frac{p}{2^q}+\frac{r}{3},$ let us define $c=\frac{2^q-p}{2^q},$ so that $b+c=1+\frac{r}3=\frac{r+3}3,$ which is truly atomic, reusing the same notation from $\S$3.1.
-----
However, we will also prove that $M$ is not nearly atomic. Suppose by contradiction that there exists some $c=\frac{p_0}{2^{q_0}}+\frac{r_0}3$ such that $b+c$ is truly atomic for all $b\notin\mathcal{U}(M).$ However, setting $b=\frac{1}{2^{q_0+1}},$ we have $$b+c=\frac{2p_0+1}{2^{q_0+1}}+\frac{r_0}3.$$Since $2p_0+1$ is odd and $2^{q_0+1}$ is even, it is clear that $\frac{2p_0+1}{2^{q_0+1}}$ cannot be written in the form $\frac{r_1}3$ for some $r_1\in\mathbb{N}$ and thus $b+c$ is not truly atomic, a contradiction. Thus our $M$ works by construction. $\blacksquare$
6 replies
smileapple
May 13, 2023
felixgotti
Jun 15, 2023
No more topics!
a