Intereting Posts

Laurent series of $\frac{1}{(z-1)(z-2)}$
Prove that the sphere is the only closed surface in $\mathbb{R}^3$ that minimizes the surface area to volume ratio.
A finitely additive measure is a measure if and only if we have continuity from below
Evaluating $\lim_{n\to\infty} \frac{1^{99} + 2^{99} + \cdots + n^{99}}{n^{100}}$ using integral
Coupon collector's problem using inclusion-exclusion
Are all mathematicians human calculators?
Derivative of piece-wise function given by $x\sin\frac1x$ at $x=0$
suggest textbook on calculus
How many arrangements of $\{a,2b,3c,4d, 5e\}$ have no identical consecutive letters?
Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.
Interesting properties of Fibonacci-like sequences?
Characterizing continuous functions based on the graph of the function
Number of monomials of certain degree
Strong Law of Larger Numbers with Coin flips
What is the second principle of finite induction?

So given any binary string B:

$$b_1 b_2 \dots b_n$$

$$b_i \in \{0,1\}$$

It would seem it is always possible to make a partitioning of B:

- Mathematical induction - what makes it true?
- How many solutions are there to the equation $x + y + z + w = 17$?
- How many ways are there to position two black rooks and two white rooks on an 8X8 chessboard
- Distinguishing powers of finite functions
- In how many ways can three numbers be selected from the numbers $1,2,\dots,300$ such that their sum is divisible by $3$?
- Quantifiers, predicates, logical equivalence

$$ b_1 b_2 \dots b_{p_1}|b_{p_1 + 1}b_{p_1 + 2}\dots b_{p_2}|\dots|b_{p_m + 1}b_{p_m + 2}\dots b_n$$

$$= P_0 | P_1 |\dots|P_m$$

such that when $P_i$ is interpreted as the binary representation of an integer then:

$$\exists{k}:\sum_{i=0}^{m}P_i = 2^k$$

For example here is the first few:

```
1 = 1
10 = 2
1|1 = 2
100 = 4
1|01 = 2
11|1 = 4
1000 = 8
1|00|1 = 2
10|10 = 4
1|0|11 = 4
...
```

Additional examples are here: http://pastebin.com/3B2P4asC

How can we prove this for all binary strings?

- Egyptian fraction representations of real numbers
- Number of primes less than 2n
- $i'=i^{-1} \bmod p$, prove or disprove that $\lim_{p\to \infty}\dfrac{1}{p^3}\sum_{i=1}^{p-1}ii'=\frac{1}4$
- Finding all possible values of a Function
- Prove that $\{\frac{\phi (n)}{n}\}_{n \in \Bbb N}$ is dense in $$
- Find all conditions for $x$ that the equation $1\pm 2 \pm 3 \pm 4 \pm \dots \pm n=x$ has a solution.
- $a =\prod_{i = 1}^{r} p_{i}^{ai}$ with $a_{i} > 0$ for each $i$ is the canonical representation of $a$…
- Is zero a cluster point of $n\sin n$?
- Distinguishing powers of finite functions
- If a plane is divided by $n$ lines, then it is possible to color the regions formed with only two colors.

This is (essentially) problem 6 in the MSRI newsletter, Emissary, for Fall 2011:

You are allowed to transform positive integers $n$ in the following

way. Write $n$ in base 2. Write plus signs between the bits

at will (at most one per position), and then perform the indicated

additions of binary numbers. For example, $123_{10} = 1111011$

can get + signs after the second, third and fifth bits to become

$11+1+10+11 = 9_{10}$; or it can get + signs between all the bits

to become $1+1+1+1+0+1+1 = 6_{10}$; and so on.

Prove that it is possible to reduce arbitrary positive integers to 1 in

a bounded number of steps. That is, there is an absolute constant $C$

such that for any $n$ there is a sequence of at most $C$ transformations

that starts with $n$ and ends at 1.

Comment: The best possible bound is a real shocker.

No solution is given.

Look at two and three bit strings starting with 1, and the minimum and maximum ways they can contribute to the sum.

$$

\begin{array}{c|c|c}

T & A(T) & B(T) \\

\hline \\

1 & 1 & 1 \\

10 & 1 & 2 \\

11 & 2 & 3 \\

100 & 1 & 4 \\

101 & 2 & 5 \\

110 & 2 & 6 \\

111 & 3 & 7

\end{array}

$$

For example, we can count 110 as $1+1+0=A(110)$ or as $6=B(110)$ (the only other possibilities are $1+2$ and $3+0$). So for the two-bit strings $B(T)=A(T)+1$, and for the three-bit

strings $B(T)-A(T)\in\{3,4\}$.

Now consider a number $k$ and let $w(k)\ge 6$ be the number of 1 bits in

its binary representation.

Split $k$ into components like this:

$$

(k)_2 = T_1 0^* T_2 0^* T_3 \ldots T_{c+3} 0^* T_{end}

$$

where each $T$ starts with 1, each of $T_1,T_2,T_3$ has exactly two

bits, and each of $T_4,\ldots,T_{c+3}$ has exactly three bits, and $T_{end}$ can be empty or can contain 1,10 or 11 if $(k)_2$ ends that way without allowing another 3-bit term. In

other words, gather terms in a greedy fashion starting with the next

available 1-bit taking two or three bits as required, skipping

extra zeros, and assigning the left-over to $T_{end}$. For example

$$

(999999)_2 = 11~~11~~0~~10~~000~~100~~0~~111~~111

$$

so for $n=999999$ we would get

$$T_1=T_2=11,T_3=10,T_4=100,T_5=111,T_6=111,c=3,T_{end}=\text{empty}$$

For each type of term $A(T)$ counts the bits in $T$, so $\sum A(T_i) =

w(k)$ (including $T_{end}$ in the sum).

Now we can use our terms as a counter as follows.

- Start counting each term with $A(T)$ to sum to $w(k)$.
- To increment, count $T_1$ as $B(T_1)$ to get $w(k)+1$.
- Count $T_2$ as $B(T_2)$ to get $w(k)+2$.
- Count $T_3$ as $B(T_3)$ to get $w(k)+3$.
- Count $T_4$ as $B(T_4)$ and reset to $A(T_i),i=1,2,3$ to get either

$w(k)+3$ or $w(k)+4$.

Repeat this, counting more 3-bit terms as $B(T)$ to add 3 or 4 at a time (and finally $B(T_{end})$ if applicable),

counting $T_1,T_2,T_3$ as $A$ or $B$ to get the increments in between.

By this counting method we find partitions that sum to each number between $w(k)=\sum A(T_i)$ and $\sum B(T_i)$.

Let $z$ be the number of terms that are $T=111, A(T)=3, B(T)=7$.

Then

$$

\begin{align}

w(k) = \sum A(T_i) & \le 6+(2c+z)+2 \\

w(k)-8 & \le 2c+z \le 3c \\

c & \ge w(k)/3-8/3 \\

\sum B(T_i) & \ge \sum A(T_i)+3+3c+z \\

& \ge w(k)+3+w(k)/3-8/3+w(k)-8 \\

& = 7w(k)/3-23/3

\end{align}

$$

So for any $k$ we can find a partition that sums to each value in $[w(k),\max(w(k)+3,7w(k)/3-23/3)]$. For all $w(k)\ge 6, w(k)\ne 9, w(k)\ne 10$ this interval contains a power of 2.

We handle the remaining possible values for $w(k)$ as special cases.

For $w(k)=10$ we can just use a refinement of the bound above. In this case $c\ge 1$, so $\sum B(T_i) \ge \sum A(T_i)+6$, so 16 will be included.

$w(k)=1,2,4$ are immediate, just add the bits. For $w(k)=3$ we can always partition the number into $10,1,1$ or $11,1$ and possibly some zeros. For $w(k)=5$ if all 1 bits are adjacent, we can write it as $1111,1$, otherwise we can write it as $101,1,1,1$ or $100,1,1,1,1$.

For $w(k)=9$ if all bits are adjacent, then we can take $11111111,1$. Otherwise there is either a 100 or 101 which we take as $T_1$. From the remaining bits make a three-bit term $T_2$ and a two-bit term $T_3$. Then either $B(T_1)+B(T_2)$ or $B(T_1)+B(T_2)+B(T_3)$ plus the remaining bits makes 16.

This answers the original question.

As an addendum, we can extend this technique taking longer terms, e.g. for 4-bit terms $A(T)+7 \le B(T) \le A(T)+11$, so we can take 11 two-bit terms and $c$ 4-bit terms and count from $w(k)$ to at least $w(k)+11+7c$.

For 5-bit terms $A(T)+15 \le B(T) \le A(T)+26$ and with 26 two-bit terms we can count from $w(k)$ to $w(k)+26+15\lfloor (w-26)/5\rfloor$. For $w(k)$ large enough this upper bound is larger than $3w(k)$, so the interval will contain a power of 3.

Carrying it further, taking $l$-bit terms for larger $l$ we can extend this interval to any multiple of $w(k)$. Thus, for choice of any $q>1$ there is a bound $W(q)$ so that any number $k$ with Hamming weight large enough $w(k)>W(q)$ can be partitioned into $P_i$ with $\sum P_i = q^m$ for some $m$.

- Question on the infinite direct product of projective modules
- Which is bigger among (i) $\log_2 3$ and $\log _3 5$ (ii) $\log_2 3$ and $\log _3 11$.
- Intersection of two arcs on sphere
- $10$ Equations in $10$ variables
- Why is polynomial convolution equivalent to multiplication in $F/(x^n-1)$?
- Power-reduction formula
- Categorial definition of subsets
- Explanation of the binomial theorem and the associated Big O notation
- Transformation of state-space that preserves Markov property
- Find the area of the region which is the union of three circles
- Lebesgue measure on Riemann integrable function in $\mathbb{R}^2$
- condition for a cubic to have a repeated root
- A series related to $\zeta (3)$.
- Integrals involving reciprocal square root of a quartic
- Investigate the convergence of $\sum a_n$, where $a_n =\int_{0}^{1} \frac{x^n \sin(\pi x)}{1-x} dx$.