How is a binary set defined, rather than a binary pair?

AshAuktober wrote: How is a binary set defined, rather than a binary pair? Binary Set is defined as the set of binary pairs . I think here it asks about the maximum cardinality of the binary set which Ig $n-1$

Hint: If ab+1 and ac+1 are powers of 2 Then a is smaller than b or c

Define a graph $G$ with the $n$ numbers as vertices, with 2 numbers being connected iff they form a binary pair. Claim: $G$ is a tree Proof. FTSOC let there exists a cycle. This means that there exist $a_1,a_2,\ldots,a_n,x_1,\ldots,x_n$ such that: $$\begin{cases} a_1a_2=2^{x_1}-1 \\ a_2a_3=2^{x_2}-1 \\ \cdots \\ a_na_1=2^{x_n}-1\end{cases}$$Let WLOG $x_1$ be the largest out of the x's. Then by Zsigmondy theorem if $x_1\neq 6$ there exists a prime $p$ that divides $2^{x_1}-1$ and doesn't divide $2^i-1$ for $i=0,1,\ldots, x_1-1$. Then we have that $p \mid a_1$ or $p\mid a_2$ $\Rightarrow$ $p\mid 2^{x_n}-1$ or $p\mid 2^{x_2}-1$ $\Rightarrow$ $x_1=x_n$ or $x_1=x_2$ $\Rightarrow$ $a_2=a_n$ or $a_1=a_3$, which is a contradiction. It is now easy to check that when $x_1=6$ the above system of equations again doesn't have a solution. This implies that $G$ can have at most $n-1$ edges, meaning there can be at most $n-1$ binary pair. To show that in fact $n-1$ is the answer, one can consider the numbers $1,2^1-1,2^2-1,\ldots,2^{n-1}-1$

The answer is n-1. We will convert the question into graphs where 2 numbers are connected iff they are a binary pair. We will show that there can never be a cycle in this graph. Suppose there is a cycle. Then, we can pick the local maximum of the product of 2 consecutive values in the cycle $a_1, a_2, ..., a_k$, (let us name them $a_i$ and $a_i+1$, where $a_ia_{i+1} > a_{i-1}a_i$ and $a_ia_{i+1} > a_{i+2}a_{i+1}$ (we can have a scenario where $a_{i+2} = a_{i-1}$ when the cycle is of length 3, but I claim that this does not affect the solution whatsoever). $$\frac {(a_{i-1}a_i)(a_{i+1}a_{i+2})}{a_ia_{i+1}} = a_{i-1}a_{i+2}$$$$\frac {(2^x - 1)(2^y - 1)}{2^z - 1} = a_{i-1}a_{i+2}$$However, note that $gcd(2^z-1, (2^x-1)(2^y-1)) \leq gcd(2^z-1, 2^x-1)gcd(2^z-1, 2^y-1) = (2^{gcd(z,x)}-1)(2^{gcd(z,y)}-1) < 2^z -1$ (Remark: $z$ has to be bigger than 1, otherwise the binary pair cant exist) Thus the LHS cannot be an integer, but the RHS is, thus there is a contradiction. Therefore the answer is at most n-1, and the construction is very simple with {1, $2^2-1$, ..., $2^n - 1$}.

This is my solution : I. Prove that all binary set $(a,b)$ are of the form $(1,2^x-1)$: Let $(a,b)$ be binary set hence we have $ab+1=2^x$. Thus $a,b<2^x.$ So we may rewrite $a=2^x-t$ and $b=2^x-r$ for $0<r< t<2^x$. Thus we get $(2^x-t)(2^x-r)+1=2^x\iff rt+1=2^x(r+t+1-2^x)$. On one hand we have $rt<2^x$ and $r+t>2^x-1$ i.e $r+t\geq 2^x$. If $r>1$: thus $2^x>rt>2t\geq r+t\geq 2^x$. Contradiction ! So $r=1$ and concequently $t=2^x-1$ meaning that $a=1$ and $b=2^x-1$ I. Finding the maximum number of binary set in a set $S$: Let $\chi$ be the number of binary pairs in a set $S$ of $n$ elements. If $1\not\in S$: then there are no binary sets meaning that $\chi=0$ If $1\in S$: as we can make at most $n-1$ non-ordered pairs with $1$ we have $\chi\leq n-1$. This value is reachable if $S=\{1;2^2-1;\ldots;2^{n}-1\}$.

By the way, when I first saw the problem, I immediately thought about Ukraine National Round 2023 Grade 9 (by the same author), but anyway I think the details of the solution are significantly different (and harder).

Cute problem! I love when a problem mixes both number theory and combinatorics elements.

Suppose that pairs $(a,b)$ and $(a,c)$ are both binary, where $b<c$. Then $$ab+1=2^k, \ ac+1=2^l \vdots 2^k$$Subtracting them yields $$a(c-b) \vdots 2^k$$But $a$ is odd, hence $c-b \vdots 2^k=ab+1>a$, and so $c>a$. Now draw a graph where edges=binary pairs, suppose there is a cycle, consider the maximum number in the cycle. Previous deductions give the contradiction. Hence there is no cycle and so we have at most $n-1$ edges. We can always make a simple chain, which has $n-1$ binary pairs.

Ahmed_mallek wrote: This is my solution : I. Prove that all binary set $(a,b)$ are of the form $(1,2^x-1)$: Let $(a,b)$ be binary set hence we have $ab+1=2^x$. Thus $a,b<2^x.$ So we may rewrite $a=2^x-t$ and $b=2^x-r$ for $0<r< t<2^x$. Thus we get $(2^x-t)(2^x-r)+1=2^x\iff rt+1=2^x(r+t+1-2^x)$. On one hand we have $rt<2^x$ and $r+t>2^x-1$ i.e $r+t\geq 2^x$. If $r>1$: thus $2^x>rt>2t\geq r+t\geq 2^x$. Contradiction ! So $r=1$ and concequently $t=2^x-1$ meaning that $a=1$ and $b=2^x-1$ I. Finding the maximum number of binary set in a set $S$: Let $\chi$ be the number of binary pairs in a set $S$ of $n$ elements. If $1\not\in S$: then there are no binary sets meaning that $\chi=0$ If $1\in S$: as we can make at most $n-1$ non-ordered pairs with $1$ we have $\chi\leq n-1$. This value is reachable if $S=\{1;2^2-1;\ldots;2^{n}-1\}$. $3,5$ is a binary pair, the error in your logic is that $rt$ is not necessarily smaller than $2^x$