Is it true that if $H$ and $A$ are bounded subsets of $\mathbb{R}$, then there exists at most one set $B$ such that $a+b(a\in A,b\in B)$ are pairwise distinct and $H=A+B$.
Problem
Source: Kürschák competition 2019 P3
Tags: combinatorics, algebra
11.02.2020 19:26
Denote by $A,B,H$ the generating functions of sets $A,B,H$ respectively. Treat these as polynomials. We're looking for all $B$ such that $H=AB$. The result then follows from the fact that $\mathbb Z[X]$ is a unique factorization domain.
11.02.2020 20:06
@stroller: Your argument is true if $A,H$ are finite sets. But, the only thing pointed is they are bounded. So, ... it's not true. For example $(0,1)+(0,1)=(0,2); (0,1)+[0,1]=(0,2)$.
11.02.2020 20:07
But I understand that the condition is that $a+b=a'+b'$ implies that $a=a', b=b'$ which is not true in your example?
11.02.2020 20:48
Oh, very sorry, I didn't read properly and underestimated the problem. After all, it's not from a district Olympiad. But, nevertheless, the statement is not true. It involves an interesting construction.
12.02.2020 04:55
dgrozev wrote: Oh, very sorry, I didn't read properly and underestimated the problem. After all, it's not from a district Olympiad. But, nevertheless, the statement is not true. It involves an interesting construction. Could you please post the construction, I spent a lot of time on it but made no progress.
12.02.2020 11:13
I may post a detailed solution later, but here is the main idea. View it as a game between two players $A,B$. Each player constructs its own set - $A$ or $B$ and there is another "common" set $P$. At the begining $P=A=B=\emptyset$. First palyer - $A$ adds one real to $A$ and $P$. After each turn, the corresponding player, say B, construct the set $A+P$, adds one real to his set $B$ and some reals $\Delta P$ to $P$ such that $A+P\subset B+(P\cup \Delta P)$. Thus, at each step the sets $A, B, P$ increase. After infinitely many steps, we arrive at some sets, denote them again by $A,B,P$. Then $A+P=B+P$. There are two technical obstacles. 1) The sets $A,B,P$ must remain bounded; 2) At each step the sums $A+P$, resp. $B+P$ must remain distinct. Omitting either 1) or 2) makes the problem easier. I resolved it by considering $\mathbb{R}$ as an infinitely dimensional vector space and each time adding new basis vectors to $A,B$ to ensure sums remain distinct. The boundedness is not an issue.
12.02.2020 19:24
dgrozev wrote: There are two technical obstacles. 1) The sets $A,B,P$ must remain bounded; 2) At each step the sums $A+P$, resp. $B+P$ must remain distinct. Omitting either 1) or 2) makes the problem easier. I resolved it by considering $\mathbb{R}$ as an infinitely dimensional vector space and each time adding new basis vectors to $A,B$ to ensure sums remain distinct. The boundedness is not an issue. Can we just use the fact that there exists a real in any interval instead of using $\mathbb{R}$ is an infinitely dimensional vector space
12.02.2020 20:35
Yeah, of course.
12.02.2020 21:12
dgrozev wrote: Yeah, of course. I still face some difficulties in cleaning up the mess of preserving the boundedness. That is, how to add a proper element into $B$ (Of course, If we don't add elements into $B$, then $P$ will be unbounded. However I don't see clearly why adding an element (chosen from a bounded set) Into $B$ fix this problem.) Seems like there’s something more to be done.
14.02.2020 00:00
Ok, here are the details.
21.02.2020 10:22
Let $H=\left (a_1,a_2,a_3,\hdots,a_{\mathbb X}\right). $ $\mathbb X $ consists different real numbers , $a_1<a_2 <\hdots <a_{\mathbb X}.$ We need to construct $2$ $ B $ sets, and each of them will have only $1$ element. $B=a_1; A=H\setminus B=\left (a_1,a_3,\hdots,a_{\mathbb X}\right)\implies (B)a_1+a_2 (A)\leftrightarrow (B)a_1+a_3 (A)\leftrightarrow\hdots\leftrightarrow (B)a_1+a_{\mathbb X}(A).$ $B=a_2;A=H\setminus B=\left (a_1,a_2,\hdots,a_{\mathbb X}\right)\implies (B)a_2+a_1 (A)\leftrightarrow (B)a_2+a_3 (A)\leftrightarrow\hdots\leftrightarrow (B)a_2+a_{\mathbb X}(A).$ We have $2$ $B $ sets satisfy the condition. Is bounded interval not $\equiv $ bounded sets?
21.02.2020 19:15
Physicsknight wrote: Let $H=\left (a_1,a_2,a_3,\hdots,a_{\mathbb X}\right). $ $\mathbb X $ consists different real numbers , $a_1<a_2 <\hdots <a_{\mathbb X}.$ We need to construct $2$ $ B $ sets, and each of them will have only $1$ element. $B=a_1; A=H\setminus B=\left (a_1,a_3,\hdots,a_{\mathbb X}\right)\implies (B)a_1+a_2 (A)\leftrightarrow (B)a_1+a_3 (A)\leftrightarrow\hdots\leftrightarrow (B)a_1+a_{\mathbb X}(A).$ $B=a_2;A=H\setminus B=\left (a_1,a_2,\hdots,a_{\mathbb X}\right)\implies (B)a_2+a_1 (A)\leftrightarrow (B)a_2+a_3 (A)\leftrightarrow\hdots\leftrightarrow (B)a_2+a_{\mathbb X}(A).$ We have $2$ $B $ sets satisfy the condition. Is bounded interval not $\equiv $ bounded sets? I didn't got it and indeed tried hard!?
23.02.2020 06:28
Physicsknight wrote: Let $H=\left (a_1,a_2,a_3,\hdots,a_{\mathbb X}\right). $ $\mathbb X $ consists different real numbers , $a_1<a_2 <\hdots <a_{\mathbb X}.$ We need to construct $2$ $ B $ sets, and each of them will have only $1$ element. $B=a_1; A=H\setminus B=\left (a_1,a_3,\hdots,a_{\mathbb X}\right)\implies (B)a_1+a_2 (A)\leftrightarrow (B)a_1+a_3 (A)\leftrightarrow\hdots\leftrightarrow (B)a_1+a_{\mathbb X}(A).$ $B=a_2;A=H\setminus B=\left (a_1,a_2,\hdots,a_{\mathbb X}\right)\implies (B)a_2+a_1 (A)\leftrightarrow (B)a_2+a_3 (A)\leftrightarrow\hdots\leftrightarrow (B)a_2+a_{\mathbb X}(A).$ We have $2$ $B $ sets satisfy the condition. Is bounded interval not $\equiv $ bounded sets? Seems like you are defining $H$ through a recursive algorithm, but how to make sure that $H$ is bounded.