Skip to main content

Logs and Bits

This blog can be divided into two parts: In the first part, I would be talking about some basic but useful $\log n$-ish algorithms, and later I would be discussing some construction-based problems whose solution exploits the binary representation of numbers. Both parts can be read independently too.

Let's get started...

For completeness, I define what is an algorithm: A finite sequence of well-defined mathematical or logical steps that when followed would yield an answer to a class of similar problems or a computation. Iteration and Recursion lie at the core of any algorithm. The time complexity of an algorithm is an estimate of how the number of steps in the algorithm grows as the input increases. So we say an algorithm is $O(n)$ if the number of steps in it is bounded above by $cn$ for some $c$.And similarly, you understand $O(\log n)$,$O(n^2)$,etc.

The main purpose of an algorithm is to shorten the number of steps or the memory used in the otherwise brute-force or naive approaches to that problem. A simple example to give is of finding if a subset of $N$ elements has some subset whose elements sum up to a given number $S$. The brute-force method is to list down all the $2^N$ subsets of the set, find the sum for each of them and check if it equals $S$.But there is a different approach that uses at most $N\times S$ steps and is known as the Subset Sum Problem.

There are numerous $log(n)$ algorithms in use today, but I think there are these three core algorithms that form the foundations of almost all others:

Euclid's GCD algorithm

We are asked to find the greatest common divisor of two given positive integers $a$ and $b$ and $a>b$.What is your brute-force approach? I guess it would be iterating over all $g<=b$ and if $g\vert a$ and $g\vert b$ you update $g$ as your answer. But a much better method was proposed by Euclid:
Let $r_0=a$ and $r_1=b$. For $i\geq 2$ define $r_{i}$ and $q_{i-1}$ iteratively as follows:
$$r_{i-1}=q_ir_i+r_{i+1}$$ where $0\leq r_{i+1}<r_i$. Stop this iteration as soon as $r_{n}=0$ for some $n$.Then the gcd is $r_{n-1}$.

The proof of this is simple:  Since gcd$(a,b)$=gcd$(a-kb,b)$ for all integers $k$,
gcd$(r_i,r_{i+1})$=gcd$(r_i-q_{i+1}r_{i+1},r_{i+1})$=gcd$(r_{i+2},r_{i+1})$. 
Therefore gcd$(a,b)$=gcd$(r_{n-1},r_{n})$=gcd$(r_{n-1},0)$=$r_{n-1}$.

Now observe that $\forall i \leq n$  $r_{i-2}=q_{i-1}r_{i-1}+r_i \geq r_{i-1}+r_i > 2r_i$.
Therefore if $n$ is even, $2^{\frac {n-2}{2}}r_{n-1}\leq r_1 =b$ else $2^{\frac{n-3}{2}}r_{n-1}\leq r_1=b$
In short $n\leq c\log_{2}{\frac{b}{r_{n-1}}}\leq c\log_{2}b$ for some $c$. 
Thus the complexity of this $O(\log($min$(a,b)))$

Following is the pseudo-code of the algorithm:

Execute this loop while $b>0$
          Define variable  $q=\lfloor\frac{a}{b}\rfloor$
          Define variable $b'=b$
          Change the value of variable $b$ to $a-bq$
          Change the value of variable $a$ to $b'$

Here, after the $i$th iteration the values assumed by $a$ and $b$ are same as $r_i$ and $r_{i+1}$ respectively. The loop is executed $n-1$ times and the value of $a$ thus obtained is the gcd.

Also for the connection of  Euclid's GCD algorithm with Bezout's theorem, check this out: Extended Euclidean Algorithm

Would Euclid have thought about how effective how his method was when it was discovered thousands of years before the notion of complexity was introduced?

Divide and Conquer

'Divide and Conquer is an umbrella term that I assign to three important algorithms:

Binary Search
You are given a sorted list of $N$ distinct numbers and additionally a number $A$.You need to find whether $A$ is in the list or not.If N is small you can just tell by inspection.  But here we are given a large N. Obviously, the naive approach is to check the numbers of the list one by one and check if any of them is equal to $A$ There is indeed a much better approach. Denote by $a[i]$ the $i$th smallest number in the list. Declare two variables $l$ and $r$ where initially $l=1$ and $r=N$. Here is the pseudo-code for binary search:

Execute the loop till $l<r$ holds:
           declare a variable $m=\lfloor\frac {l+r}{2}\rfloor$ 
           if($a[m]<A$)
                    change the value of $l$ to $m+1$
           else if($a[m]\geq A$)
                    change the value of $r$ to $m$

if($a[l]$ is equal to $A$)
          $A$ is present in the list
else
          $A$ is not present in the list.

Why does this work? The main observation is that after every step if $A$ exists then it has to satisfy $A=a[i]$ where $l\leq i\leq r$.We prove this by induction.
At the first step, it is trivial as we have initialized $l$ and $r$ as the boundaries of the list.
So assume it is true till $k$ steps. So suppose in the $k$th iteration we find $A>a[m]$.It means that $A>a[i] \forall i: l\leq i\leq m$ (sorted list).By induction hypothesis we know that if $A$ exists then $A=a[i]\forall i:l\leq i\leq r$. These two facts imply that if $A$ exists then $A=a[i]$ for some $m+1\leq i\leq r$ .But the $l$ and $r$ after the $(k+1)$th step are $m+1$ and $r$ respectively after the $k$th step by our algorithm. Thus proved. The case $A\leq a[m]$ can be dealt along the same lines.
And why is this log$(n)$? The value of $(r-l)/2$ roughly halves after each loop execution. Thus it would reach $0$ in roughly $log_2 n$ moves. Hence it is $O(\log n)$.

Binary Exponentiation
Given a real $x$ and a natural $n$, you need to evaluate $x^n$.Obviously for small values of $n$ you can do it by hand or with a calculator. But what if I asked you to evaluate $2^{10^{10}}$ modulo some large prime under $1$ second? You would require the help of a computer and an efficient algorithm too. The brute-force approach is of multiplying $1$ by $x$ $n$ times. The clever approach uses recursion. In order to get a feel of recursive programs in case you are unfamiliar with it, refer to Fibonacci number recursion. Here is the pseudo-code of binary exponentiation:

solve(Base $x$, exponent $n$)(This function would return the value of $x^n$)
       if($n$ equals $0$)
                return $1$ from this function.
        else
                Define a variable $z =$ solve(Base $x$, exponent $\lfloor\frac{n}{2} \rfloor$)
                if($n$ is odd) return $xz^2$
                else return $z^2$

 I think you might have already guessed the logic of this algorithm. It is just precomputing $x^{\lfloor\frac {n}{2}\rfloor}$ and expressing $x^n$ in terms of it. As to why this is logarithmic, the size of the exponent roughly halves after each function call, hence the exponent would reach $0$ in approx $log_{2} n$ steps. Thus the complexity is $O(\log n)$.

Merge Sort
 Given an array(just a list) of $N$ numbers, you need to sort them in increasing order. First of all, this algorithm is not $O(\log n)$ but $O(n\log n)$, but its significance and method deserves its mention here. This algorithm is also of recursive nature. Denote by $a[i]$ the $i$th number in the array from the left and call $i$ as this number's index. Define two variables $l$ and $r$ where initially $l=1$ and $r=n$. The idea is this:

For the current value of $l$ and $r$ define $m=\lfloor\frac{l+r}{2}\rfloor$.Now construct two arrays $b_1$ and $b_2$ of sizes $m-l+1$ and $r-m$ respectively such that $b_1$ contains the elements of $a$ having index in the range $[l,m]$ placed in increasing order from left to right and $b_2$ be similarly defined for the index range $[(m+1),r]$. Now you create three variables $i$,$l_1$ and $r_1$ and an empty array $c$ of size $(r-l+1)$ where initially $l_1=l$,$r_1=m+1$ and $i=1$.You perform the following operation(merging step):

Execute this loop while either $l_1<=m$ or $r_1<=r$
            If($l_1$ is equal to $m+1$)
                     Execute this loop while $r_1<=r$
                             Set $c[i]$ equal to $b_2[r_1]$
                             Increase $r_1$ by $1$
                             Increase $i$ by $1$

           Else If($r_1$ is equal to $r+1$)
                     Execute this loop while $l_1<=m$
                             Set $c[i]$ equal to $b_1[l_1]$
                             Increase $l_1$ by $1$
                             Increase $i$ by $1$ 
       
            Else If($b_1[l_1]>b_2[l_2]$)
                     Set $c[i]$ equal to $b_2[l_2]$
                     Increase $l_2$ by $1$
                     Increase $i$ by $1$

            Else
                     Set $c[i]$ equal to $b_1[l_1]$
                     Increase $l_1$ by $1$
                     Increase $i$ by $1$

So let me illustrate the above code with an example.

Suppose at some random stage of the algorithm, $b_1=${$2,5,7,7$},$b_2=${$3,6,7,8$}, $c=${}, $l=l_1=3$ ,$m=6$, $r_1=7$, $r=10$ $i=1$ and merging step needs to be performed on $b_1$ and $b_2$:
After iteration $1:$ $c=${$2$},$l_1=4$,$r_1=7$ $i=2$ and others as it is.
After iteration $2:$ $c=${$2,3$},$l_1=4$,$r_1=8$ $i=2$ and others as it is.
After iteration $3:$ $c=${$2,3,5$},$l_1=5$,$r_1=8$ $i=3$ and others as it is.
After iteration $4:$ $c=${$2,3,5,6$},$l_1=5$,$r_1=9$ $i=4$ and others as it is.
After iteration $5:$ $c=${$2,3,5,6,7$},$l_1=6$,$r_1=9$ $i=5$ and others as it is.
After iteration $6:$ $c=${$2,3,5,6,7,7$},$l_1=7$,$r_1=9$ $i=6$ and others as it is.
After iteration $6:$ $c=${$2,3,5,6,7,7,7$},$l_1=8$,$r_1=10$ $i=7$ and others as it is.
After iteration $6:$ $c=${$2,3,5,6,7,7,7,8$},$l_1=8$,$r_1=11$ $i=8$ and others as it is.
And the loop terminates.

So what have we obtained? $c$ just contains the union of elements in $b_1$ and $b_2$ and they are arranged in increasing order and the main loop was iterated atmost (r-l+1) times. This was the key step in the merge sort algorithm. Now to the main algorithm:

Mergesort(Given $l$ and $r$ and array $a$)
          If($l$ is not equal to $r$)
                    Define a variable $m=$ $\lfloor \frac{l+r}{2}\rfloor$
                    Mergesort(Given $l$ and $m$ and array $a$)            (Denote this by L-M call)
                    Mergesort(Given $m+1$ and $r$ and array $a$)        (Denote this by M-R call)
                    Declare an array $b_1$ of size $(m-l+1)$
                    Declare an array $b_2$ of size $(r-m)$
                    Copy elements in $b_1$ from $a$ such that $b_1[i]=a[i+l-1]$
                    Copy elements in $b_2$ from $a$ such that $b_2[i]=a[m+i]$
                    Declare an array $c$ of size $r-l+1$,initially empty.
                    Declare three variables $i=1$,$l_1=l$ and $r_1=m+1$
                    Carry out the merging step for $b_1$ and $b_2$ with the help of $c$,$i$,$l_1$ and $r_1$.
                     .
                     .
                     .
                     Copy elements in $a$ from $c$ such that $a[i]=c[i-l+1]$

If you are a newbie to recursion, understanding this in the first go might not be easy, so let's try to understand the entire algorithm with the help of an example: $a=$ {7,5,7,2,3,8,6} Let Body $i$ denote the execution of the algorithm inside the $i$th call of the function.

Body 1: $l=1$, $r=7$ and $m=4$. L-M call is made for $l=1$ and $r=4$ (goes to Body 2).
Body 2: $l=1$, $r=4$ and $m=2$. L-M call is made for $l=1$ and $r=2$ (goes to Body 3).
Body 3: $l=1$, $r=2$ and $m=1$. L-M call is made for $l=1$ and $r=1$ (goes to Body 4).
Body 4: $l=1$, $r=1$.Here $l$ is equal to $r$, so return to the body from which it was called (Body 3).
Body 3: L-M call is completed. M-R call is made for $l=2$ and $r=2$ (goes to Body 5).
Body 5: $l=2$, $r=2$.Here $l$ is equal to $r$ so return to the body from which it was called (Body 3).
Body 3:M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {7} and $b_2=${5}. $c$ is declared and empty. Applying  the merging step, $c=${$5,7$}.The elements of $c$ are copied in $a$. So $a$ gets changed to {$5,7,7,2,3,8,6$}.Body 3 is completed, return to the body from which it was called (Body 2).
$a$ gets transformed: {7,5,7,2,3,8,6} $\rightarrow$ {5,7,7,2,3,8,6}.
Body 2:L-M call is completed. M-R call is made for $l=3$ and $r=4$ (goes to Body 6).
Body 6: $l=3$, $r=4$ and $m=3$. L-M call is made for $l=3$ and $r=3$ (goes to Body 7).
Body 7: $l=3$, $r=3$.Here $l$ is equal to $r$, so return to the body from which it was called (Body 6).
Body 6: L-M call is completed. M-R call is made for $l=4$ and $r=4$ (goes to Body 8).
Body 8: $l=4$, $r=4$.Here $l$ is equal to $r$, so return to the body from which it was called (Body 6).
Body 6: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=${7} and $b_2$={2}. $c$ is declared and empty. Applying the merging step, $c=$ {2,7}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$5,7,2,7,3,8,6$}. Body 6 is completed, return to the body from which it was called (Body 2).
$a$ gets transformed: {5,7,7,2,3,8,6} $\rightarrow$ {5,7,2,7,3,8,6}.
Body 2: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {5,7} and $b_2=${2,7}. $c$ is declared and empty. Applying the merging step, $c=$ {2,5,7,7}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$2,5,7,7,3,8,6$}. Body 2 is completed, return to the body from which it was called (Body 1).
$a$ gets transformed: {5,7,2,7,3,8,6} $\rightarrow$ {2,5,7,7,3,8,6}.
Body 1: L-M call is completed. M-R call is made for $l=5$ and $r=7$ (goes to Body 9).
Body 9: $l=5$, $r=7$ and $m=6$. L-M call is made for $l=5$ and $r=6$ (goes to Body 10).
Body 10: $l=5$, $r=6$ and $m=5$. L-M call is made for $l=5$ and $r=5$ (goes to Body 11).
Body 11: $l=5$, $r=5$. Here $l$ is equal to $r$, so return to the body from which it was called (Body 10).
Body 10: L-M call is completed. M-R call is made for $l=6$ and $r=6$ (goes to Body 11).
Body 12: $l=6$, $r=6$. Here $l$ is equal to $r$, so return to the body from which it was called (Body 10)
Body 10: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {3} and $b_2=${8}.
$c$ is declared and empty. Applying the merging step, $c=$ {3,8}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$2,5,7,7,3,8,6$}. Body 10 is completed, return to the body from which it was called (Body 9).
$a$ gets transformed: {2,5,7,7,3,8,6} $\rightarrow$ {2,5,7,7,3,8,6}.
Body 9: L-M call is completed. M-R call is made for $l=7$ and $r=7$ (goes to Body 13).
Body 13: $l=7$,$r=7$. Here $l$ is equal to $r$, so return to the body from which it was called (Body 9).
Body 9: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {3,8} and $b_2=$ {6}.
$c$ is declared and empty. Applying the merging step, $c=$ {3,6,8}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$2,5,7,7,3,6,8$}. Body 9 is completed, return to the body from which it was called (Body 1).
$a$ gets transformed: {2,5,7,7,3,8,6} $\rightarrow$ {2,5,7,7,3,6,8}.
Body 1: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {5,7,2,7} and $b_2=$ {3,6,8}. $c$ is declared and empty. Applying the merging step, $c=$ {2,3,5,6,7,7,8}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$2,3,5,6,7,7,8$}. Body 1 is completed, return to the body from which it was called (Nothing).
$a$ gets transformed: {2,5,7,7,3,6,8} $\rightarrow$ {2,3,5,6,7,7,8$}.

Thus body 1 is exited and $a$ has got sorted.

Here is also a pictorial representation of the process. The arrays made on the arrows indicate the state of $a$ after completion of the body to which the arrow is pointing.













Two easy exercises to try:
1. $13=2\times7-1$ and the array was of size $7$. Is it some coincidence? No. Try to prove that the total number of "bodies" that would be created would be $2n-1$ where $n$ is the size of the input array.
2. For a body $i$, denote its path distance from body $1$ by $d(i)$. For eg. in the above diagram $d(7)=3$,$d(13)=2$,$d(1)=0$,etc. Prove that $\sum_{d(i)=c} (r_i-l_i+1)=n$ for all distinct possible values of $c$. Now, in each body you do the merging step atmost once and copy some array into another array. So basically you do atmost $c(r-l+1)$ steps for some constant $c$.So using the summation you proved above and this fact, can you see why this algorithm is $O(n\log n)$? Hint:What is the approximate maximum possible value of $c$?


Sieve of Eratosthenes

Given a natural number $n$, you intend to find all the prime numbers $\leq n$. What is the brute-force approach? You iterate $i$ from $2$ to $n$ and find out if $i$ is prime. To find out if $i$ is prime you iterate over all $j$ from $2$ to $i-1$, and check if $j|i$ .If there isn't any such $j$, $i$ is prime else it isn't. So the total steps that you carry out in this approach is atmost $\sum_{i=1}^{i=n} i$ $= \frac {n(n-1)}{2}$ So this method is O(n^2).Or if you know the $O(\sqrt n)$ algorithm of testing if a number is prime (using the fact that if $n$ is composite then one of its divisors $\leq \sqrt n$) then your method would become $O(n^{1.5})$. But Eratosthenes, a mathematician probably of the same time as Euclid proposed a much better method. For implementing this method you need a boolean array bool of size $n$, a boolean array basically stores $0$ or $1$ (single bit).It stores $0$ if the index corresponding to that position does not satisfy a certain condition else it stores $1$. So in this boolean array, on completion of the algorithm the $i$th element from the left would be $1$ if $i$ is not a prime. Here is the pseudo-code of the algorithm:

Declare a variable $j$ initially equal to $2$ and set all entries of bool to $0$.
Iterate over this loop while $j\leq n$:
        If (bool $[j]$ is equal to $0$)
                Declare a variable $k=2j$
                Iterate over this loop while $k\leq n$
                        Set bool $[k]$ equal to $1$
                        Increment $k$ by $j$
        Increment $j$ by $1$

Why does this work? Simply because if $i\geq 2$ is composite, then $\exists j_1\geq 2,j_1<i$ such that $j_1|i$. So when $j$ would have become equal to $j_1$ in the loop, if bool[$j_1$] was $0$, then bool[$i$] would also have changed to $1$ by the inside loop. So suppose bool[$j_1$] was $1$, but that means $\exists j_2$ such that when $j$ was equal to $j_2$, the inside loop would have marked bool $[j_1]$ as $1$ $\Rightarrow j_2|j_1\Rightarrow j_2|i$. Thus for $j=j_2$ bool$[i]$ would also have been marked $1$. And if $i$ is prime bool$[i]$ $=1$ $\Rightarrow \exists 1<j<i$ such that $j|i$, a contradiction. This also yields that whenever $j$ takes a value $j_0$ in the first loop for which bool$[j_0]$ is $0$, $j_0$ is guaranteed to be a prime. So the inner loop is executed only when $j$ is a prime. So we are roughly doing $n(\sum \frac{1}{p})$ steps in this algorithm where the summation is over all $p<n$. A result in analytical number theory tells that the summation roughly approaches $\log \log(n)$ for large $n$ Hence the complexity of the algorithm is $O(n\log (\log(n)))$.

Would Eratosthenes have found the number of steps in his algorithm on his own? If he encountered the summation of above, how would he have tackled it? Or is it that he already knew tools of analytical number theory! That is for number theorists to find out...



Enough theory, let's get to the problems! 

Problem 1:
You are given a positive integer $k\geq 2$. Call a natural $n$ $k$-good if $n$ can be written as a sum of distinct powers of $k$. How would you calculate the $m$th smallest $k$-good number ?

Solution:
Let $S$ be the set of all $k$-good numbers. Consider a mapping $f:S\rightarrow \mathbb{N}$ defined as follows: Let $v\in S$. Therefore $v = k^{a_1}+k^{a_2}$...$+k^{a_p}$ where $0\leq a_1<a_2$...$<a_p$. Then $f(v) = 2^{a_1} + 2^{a_2}$...$+2^{a_p}$. Uniqueness of binary representation of a number guarantees that $f$ is injective. Also $\forall n\in \mathbb{N}, n=2^{a_1}+2^{a_2}$...$+2^{a_p}$, $f(k^{a_1}+k^{a_2}$...$+k^{a_p}) = n$. Thus $f$ is a bijective map. If we show that $f^{-1}(n)<f^{-1}(n+1)$, $f^{-1}(m)$ would be the answer. Let $i$ be the least natural such that the $i$th bit from the right in the binary representation of $n$ is $0$. Then $f^{-1}(n+1)-f^{-1}(n) = k^{i-1} -\sum_{j=0}^{j=i-2} k^j>0$ as $k\geq 2$. $\blacksquare$

Comment: 
The main motivation to consider this mapping was that for $k=2$, $S=\mathbb{N}$.

Problem 2:
You are given a positive integer $n$ and a permutation $p$ of {$1,2,$...$n$} is hidden from you. In one move you can choose a subset {$t_1,t_2,$...$t_k$} of {$1,2,$...$,n$} and you would be returned the set {$p[t_1],p[t_2],$...$,p[t_k]$} where $p[i]$ denotes the $i$th element from the left. Think of a strategy to know $p$ in atmost $\lceil log_2 n\rceil$ moves.

Solution:
In the $i$th move you construct the set of all those numbers (denoted by $S_i$) whose $i$th bit from the right is $1$ in their binary representation. So you make exact $\log_2 n$ queries and obtain $\log_2 n$ distinct sets.
Now consider any $i\leq n$ and suppose $i=2^{a_1}+2^{a_2}+$...$+2^{a_k}$, $0\leq a_1<a_2<$...$<a_k$. Then $p[i]$ would be present in the sets $S_{a_1+1},S_{a_2+1},$...$,S_{a_k+1}$ and moreover by uniqueness of binary representation $\nexists j$ such that $p[j]$ belongs to exactly these sets. Hence we can find $p[i]$ $\forall i$ $\blacksquare$

Comment:
The motivation was to force $p[i]$ to be in some sets $S_1,S_2,$...$,S_k$ such that $S_1\cap S_2\cap$...$\cap S_k=$ {$p[i]$}. What else than binary numbers?


Problem 3 (USAMO 2002):
Given a set $S={1,2,...,n-1,n}$ and $M\leq 2^n$, prove that it is possible to divide the collection of $2^n$ subsets of S into two parts $X$ and $Y$, such that the following 3 conditions hold:
1: If $A,B\in X$, $A\cup B\in X$.
2: If $A,B\in Y$, $A\cup B\in Y$
3: $|X|=M$ and $|Y|=2^n-M$
,
Solution: 
For $M=2^n$, simply take $X$ as the collection of all subsets, otherwise, write down the binary representation of $M$ as a $n-$ element string $s$ (i.e you append zeroes if required in the beginning of the representation to make its total length equal to $n$). Denote by $s[i]$ the $i$th element of the string from the left. We construct $X$ as follows:
Start iterating over the string index from $i=1$ to $i=n$: If $s[i]$ is equal to $1$, add all the subsets of $S$ of the form {$i$}$\cup A$ to $X$ where $A$ ranges over all subsets of {$i+1,...,n$}.Thus $2^{n-i}$ subsets would be added to $X$. Also denote by $T_i$ the set {$i,i+1,...,n$}.
Since $s$ represents the binary representation of $M$, it is guaranteed that after the n iterations, $|X|=M$. It remains to verify the first two conditions.

First we make a trivial observation that $T_i\subset T_j$ if $i>j$. Note that it suffices to verify the following two conditions:
1*: If $A,B\in X$, $A\cup B\in X$
2*: If $A\in X$, $\nexists B_1,B_2\in Y$  such that $B_1\cup B_2=A$.

Proof of (1*): Let $a$ and $b$ be the smallest elements of $A$ and $B$ respectively WLOG $b\geq a$. By construction, $A\subseteq T_a$ and $B\subseteq T_b\subseteq T_a$. Therefore $A\cup B \subseteq$ {$a$} $\cup T_{a+1}$, and $a\in A\cup B$. Thus $A\cup B\in X$.
Proof of (2*): Let $a$ denote the smallest element of $A$. If $B_1\cup B_2=A$, $a$ is the smallest element of either $B_1$ or $B_2$, but that would imply one of them belongs to $X$.
The proof is completed $\blacksquare$

Comment: 
I like to think of subsets of a set as a binary number where the $i$th bit is set if the $i$th element is present in the set or otherwise. So seeing the third condition, I got an intuition that we have to do something with the binary representation of $M$. Then I modified $1$ and $2$ to $1*$ and $2*$. And what is the best way to ensure a condition of the form $2*$? You try to fix some element $e$ of $A$ so that if a subset $P$ of $A$ contains $e$, then $P$ and $A$ have same "property" ,else different properties. So on doing some trial and error of various weird constructions, I finally arrived at the solution. The true motivation lies in the binary representation of $M$.

Problem 4 (APMO 2017):
Let $A(n)$ denote the number of sequences $a_1\geq a_2\geq$...$\geq a_k$ such that $a_i+1$ is a power of $2$ and $\sum_{i=1}^{i=k}a_i=n$. Let $B(n)$ denote the number of sequences $b_1\geq b_2\geq$..$\geq b_m$ such that $\sum_{i=1}^{i=m} b_i=n$ and the inequality $b_i\geq 2b_{i+1}$ holds for $\forall i<m$. Prove that $A(n) = B(n)$ for all positive integers $n$.

Solution:
Let $X$ be the set of all sequences $a_1\geq a_2\geq$...$\geq a_k$ such that $a_i+1$ is a power of $2$ and $\sum_{i=1}^{i=k}a_i=n.$ Let Y be the set of all sequences $b_1\geq b_2\geq$..$\geq b_m$ such that $\sum_{i=1}^{i=m} b_i=n$ and the inequality $b_i\geq 2b_{i+1}$ holds for $\forall i<m.$ $X$ is non empty as $a_i = 1\forall i$ lies in $X.$ So let $x\in X,$ $x=$ ($a_1, a_2,$...$,a_k).$ Let $a_i+1=2^{c_i}.$ Define a function $f$ as follows: $f(x)=x$ if $x\geq 1$ else $f$($x$)$=0$. Define a sequence $<b_i>$ as follows: $b_i=\sum_{j=1}^{j=n}f(2^{c_j-i})$. Observe that $b_i=0 \forall i>m$ for some unique $m$. Then we claim that $(b_1,b_2,$...$,b_m)\in Y$. 
$$\sum_{i=1}^{i=m} b_i=\sum_{i=1}^{i=m}\sum_{j=1}^{j=n} f(2^{c_j -i})=\sum_{j=1}^{j=n}\sum_{i=1}^{i=m} f(2^{c_j-i})=\sum_{j=1}^{j=n} a_j = n.$$ It is easy to see that $f(2k)\geq 2f(k) $ $\forall k \geq 0$.Thus, $$b_i=\sum_{j=1}^{j=n}f(2^{c_j-i})\geq \sum_{j=1}^{j=n}2f(2^{c_j-i-1})=2b_{i+1}.$$ Thus $(b_1,b_2,$...$b_m)\in Y$. 
Also note that $b_ m=$ number of indices $j$ such that $a_j=2^m-1$, and $\forall i<m$, $b_i-2b_{i+1}=$ number of indices $j$ such that $a_j=2^i-1$. This proves that this transformation is injective. Thus $|X|\leq |Y|$.
For proving $|X|\geq |Y|$ we just reverse the above transformation and prove it is injective, so let $y\in Y$, $y=(b_1,b_2,$...$,b_m)$ We construct $x\in X$ from $y$ as follows: Add $b_m$ copies of $2^m-1$ to $x$ and $\forall i<m$, add $b_i-2b_{i+1}$ copies of $2^i-1$ to $x$. The sum of the elements in $X$ is $$\sum_{i=1}^{i=m-1}(2^i-1)(b_i-2b_{i+1})+b_m(2^m-1)=\sum_{i=2}^{i=m}b_i(2^i-2.2^{i-1})+\sum_{i=2}^{i=m}b_i(2-1) +b_1=n.$$
To prove injectivity consider $y,y'\in Y$ ,$y=(b_1,b_2,$...$,b_m)$, $y'=(b'_1,b'_2,$...$,b'_{m'})$ and suppose they yield the same $x$ by the above construction. Since $a_1$ generated by both is same, $2^m-1=2^{m'}-1\Rightarrow m=m'$. 
Since both generated same number of $2^i-1$'s $\forall i\leq m$, $b_m=b'_m$ and $b_i-2b_{i+1}=b'_i-2b'_{i+1}$ $\forall i<m$. This forces $b_i=b'_i$ and thus $y=y'$. 
The proof is completed $\blacksquare$

Comment:
 How would you even come up with such construction? Writing $a_i$'s in their binary representation was the key hint for me. Rest was all just formalization.




A pictorial representation of the transformation sending $x$ to $y$.


Problem 5(Based on the Codeforces problem GCD Guess)
Alice and Bob are playing a game. Alice has a secret integer $x$ which Bob has to guess. Alice also tells Bob the value of $t=\lceil \log_2 x\rceil$.Now Bob can make atmost $t$ queries of the following form:
He gives Alice two integers $a$ and $b$ and she answers the value of gcd($x+a,x+b$) truthfully.
Prove that Bob can win the game.

Solution:
Consider a variable $y$ initially set to $0$ We think of $x$ in terms of its binary representation. We iterate a variable $i$ from $1$ to $t$ and after every iteration, we would have successfully determined the $i$th bit from the right. 
In every iteration, Bob asks Alice the GCD of $(x+2^t+2^{i-1}-y,x+2^{i-1}-y)$. If Alice's answer is $2^{i-1}$ it means the $i$th bit from the right is $0$. If it isn't, that bit is $1$ and Bob modifies the value of $y$ to $y+2^{i-1}$. After the $t$ th iteration, the value of $y$ would be the same as the hidden number $x$. The logic of this method is as follows:
gcd $(x+2^t+2^{i-1}-y,$ $x+2^{i-1}-y)=$ gcd $(2^t,$ $x+2^{i-1}-y)$. After the $i$th iteration $y$ basically stores the rightmost $i$ bits of $x$ in that order. For eg if $x=(100101)_2$, then after $3$rd iteration $y=(101)_2$ and after $4$th iteration $y=(0101)_2$. Therefore during the $i$th iteration the  $i-1$ rightmost bits of $x-y$ are $0$. If the $i$th bit is $0$, gcd$(2^t,2^{i-1}+x-y)=2^{i-1}$ and if its $1$ gcd is $>2^{i-1}$ and we update the value of $y$ to store the rightmost $i$ bits of $x$ in that order $\blacksquare$

Comment:
When I first saw this problem the first thought that came to my mind was fixing primes, i.e since gcd$(x+a,x+b)=$ gcd$(x+a,b-a)$, if we fix $a=1$ and $b=p+1$, where $p$ ranges over all primes $\leq 2^t+1$, we can find out the distinct prime divisors of $x+1$. But this method would neither give the multiplicity of that prime and further it is totally false that there would be atmost $t$ such primes. So the intended method was something totally different. Some time later I realized that there are atmost $t$ digits in the binary representation of $x$ and what if in one move I am able to determine one of these  bits? So using gcd$(2^r,s)=$ min $(r,v_2(s))$, the solution naturally follows.



So this is it for this blog. In case you do not understand something, feel free to write it in the comments. See ya next time!

-Mihir .M. Kaskhedikar

Comments

Popular posts from this blog

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong