Showing properties about subsets of positive integers.

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Showing properties about subsets of positive integers.

G H J

Reveal topic tags

rational number

L

G H BBookmark kLocked kLocked NReply

Source: IMO 2018 Shortlist A3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

18 posts

#1 h Jul 17, 2019, 12:20 PM • 4 Y

Y by centslordm, ImSh95, GeoMetrix, Adventure10

Given any set $S$ of positive integers, show that at least one of the following two assertions holds:

(1) There exist distinct finite subsets $F$ and $G$ of $S$ such that $\sum_{x\in F}1/x=\sum_{x\in G}1/x$ ;

(2) There exists a positive rational number $r<1$ such that $\sum_{x\in F}1/x\neq r$ for all finite subsets $F$ of $S$ .

This post has been edited 2 times. Last edited by v_Enhance, Jul 26, 2020, 7:14 PM
Reason: spelling

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1298 posts

Kayak

#2 h Jul 17, 2019, 12:35 PM • 2 Y

Y by ImSh95, Adventure10

Also Indian TST 3 P1

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1721 posts

#3 h Jul 17, 2019, 1:09 PM • 7 Y

Y by Starrysky, Smkh, centslordm, bigboo, ImSh95, Adventure10, Mango247

Fun

If $S$ is finite, it is clear that (2) holds, as there are infinitely many rational numbers less than 1.
Therefore, let us assume that $S$ is infinite. We will prove this problem indirectly. Assume that (1), (2) both fail.
Now we get that there exists a unique finite subset $S(r) \subset S$ such that $\sum_{x \in S(r)} \frac{1}{x} = r$ for each $r<1$ .
We will show that this is impossible, which shows the desired contradiction. We can also now easily assume that $1 \notin S$ , since if there is a set $S$ which satisfies the condition and also has $1 \in S$ , then $S - \{1\}$ satisfies the condition as well.
With this big condition, we can force a lot of good conditions on $S(r)$ .
For example, if we have an element $x \in S - S(r)$ , we can immediately force $S \left( r + \frac{1}{x} \right) = S(r) \cup \{x\}$ , if $r+ \frac{1}{x}<1$ .

Let us label the elements of $S$ as $2 \le u_1 < u_2 < \cdots$ .
If there exists an $n$ such that $u_{n+1} < 2u_n$ , let us denote $r = \frac{1}{u_n} - \frac{1}{u_{n+1}} < \frac{1}{u_{n+1}}$
Because $r<1$ , there should be a unique set $S(r)$ which satisfies $\sum_{x \in S(r)} \frac{1}{x} = r$ .
Clearly, for any integer $x$ in $S(r)$ , we will have $x > u_{n+1}$ . Therefore, $u_{n+1}$ is definitely not in $S(r)$ .
Now, it is clear that $T = S(r) \cup \{u_{n+1}\}$ satisfies $\sum_{x \in T} \frac{1}{x} = \frac{1}{u_n}$ .
However, $T' = \{u_n \}$ also satisfies $\sum_{x \in T'} \frac{1}{x} = \frac{1}{u_n}$ , so this shows that (1) is true. Contradiction.

Now we have $u_{n+1} \ge 2u_n$ for all $n$ . In this case, we can see that $\sum_{i=1}^\infty \frac{1}{u_i}$ can't be too big.
Indeed, the largest possible value of $\sum_{i=1}^\infty \frac{1}{u_i}$ is $\sum_{i=1}^\infty \frac{1}{2^i} = 1$ .
Therefore, if $u_i \neq 2^i$ for some $i$ , we immediately have $\sum_{i=1}^\infty \frac{1}{u_i} < 1$ .
Taking $Q = \sum_{i=1}^\infty \frac{1}{u_i} < 1$ , we can just take $r = \frac{1+Q}{2}$ and see that (2) is true. Contradiction.

Now we have $u_n = 2^n$ for all $n$ . This is quite easy to do.
For all finite subsets $T$ of $S$ , the denominator of $\sum_{x \in T} \frac{1}{x}$ will be a power of 2.
So we can just take something like $r = \frac{2018}{2019}$ and call it a day. Contradiction.

This post has been edited 2 times. Last edited by rkm0959, Jul 17, 2019, 1:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1594 posts

#4 h Jul 17, 2019, 2:02 PM • 14 Y

Y by kevinatcausa, XbenX, mijail, rashah76, qubatae, Siddharth03, rcorreaa, snap7822, ImSh95, Quidditch, sabkx, Adventure10, Mango247, Sedro

Assume that both assertions are false. Clearly $S$ is infinite. We first extract the uniqueness condition.

Claim: There does not exists $a,b\in S$ such that $a<b<2a$ .

Proof: Take subset $F$ such that $\sum\limits_{x\in F}\frac{1}{x} = \frac{1}{b}-\frac{1}{a}$ . Clearly $a\notin F$ by size reasons. So notice that
$\sum_{x\in F\cup\{a\}}\frac{1}{x} = \frac{1}{a}+\sum\limits_{x\in F}\frac{1}{x}=\frac{1}{b},$ contradiction to the first assertion.

Enumerate $S=\{a_1,a_2,a_3,...\}$ where $a_1<a_2<...$ . By the first claim $a_{i+1} > 2a_i$ . Now we extract the existence condition.

Claim: $a_{i+1} = 2a_i$ for any $i\in\mathbb{Z}^+$ .

Proof: Assume that $a_{i+1} > 2a_i$ . Take any rational $r\in\left(\frac{2}{a_{i+1}},\frac{1}{a_i}\right)$ and set $F\subset S$ such that $\sum\limits_{x\in F}\frac{1}{x} = r$ . Clearly $\{a_1,a_2,...,a_i\}\notin F$ for size reason. Thus
$r < \frac{1}{a_{i+1}} + \frac{1}{a_{i+2}} + \frac{1}{a_{i+3}} + ... \leqslant \frac{1}{a_{i+1}}\left(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...\right)=\frac{2}{a_{i+1}},$ contradiction.

Thus set $S$ must be in form $\{k, 2k, 4k, 8k,...\}$ . However, this makes $\frac{1}{3k}$ inexpressible, final contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

157 posts

#5 h Jul 17, 2019, 2:08 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

Loved this problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3042 posts

#6 h Jul 17, 2019, 2:39 PM • 2 Y

Y by ImSh95, Adventure10

Functional wrote:

Given any set $S$ of postive integers, show that at least one of the following two assertions holds:

(1) There exist distinct finite subsets $F$ and $G$ of $S$ such that $\sum_{x\in F}1/x=\sum_{x\in G}1/x$ ;

(2) There exists a positive rational number $r<1$ such that $\sum_{x\in F}1/x\neq r$ for all finite subsets $F$ of $S$ .

Solution. Assume that both the assertions do not hold. As second condition does not hold, $S$ has the infinite. Therefore for any rational $r<1$ , there is an unique subset of $S$ , $F$ such that $\sum_{x\in F} \frac{1}{x} = r$ .

Suppose there are elements $a,b$ in $S$ such that $a<b<2a$ . Then there is a subset $F$ such that $\sum_{x\in F} \frac{1}{x} = \frac{1}{a} - \frac{1}{b}$ . If $b\in F$ , then $\frac{1}{a} = \sum_{x\in F} \frac{1}{x} + \frac{1}{b} \geq \frac{2}{b}$ which is a contradiction as we have two subsets with same sum.

Suppose $S = \{a_1,a_2,\ldots \}$ , and $a_i$ 's are in increasing order. We have $a_{n+1} > 2a_n$ for all $n$ . Therefore $a_n > 2^{n-1}a_1$ . Therefore $\sum_{i=1} \frac{1}{a_i} < \frac{1}{a_1} \left(1+\frac{1}{2} + \frac{1}{4} + \ldots \right)<\frac{2}{a_1}.$ If $a_1 \geq 2$ , $\sum \frac{1}{a_1}$ is strictly less than $1$ , and we can pick a rational between $1$ and that number which gives a contradiction as second condition was false. Therefore $a_1 = 1$ . Now for a rational $r<1$ , we have a subset $F$ such that $\sum _{x\in F}\frac{1}{x} = r<1$ . Therefore $a_1\not\in F$ and again we get $\sum_{i=2} \frac{1}{a_i} < 1$ which again gives a contradiction to the second condition and we are done. $~\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

230 posts

#7 h Jul 17, 2019, 2:45 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

plagueis wrote:

Loved this problem.

It is not a good IMO problem as it does not clearly fit into the ACGN scheme. It is not A and also not C.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

32 posts

#8 h Jul 18, 2019, 12:01 PM • 4 Y

Y by DVDthe1st, ImSh95, Adventure10, Mango247

prague123 wrote:

plagueis wrote:

Loved this problem.

It is not a good IMO problem as it does not clearly fit into the ACGN scheme. It is not A and also not C.

There are examples of such problems on the IMO in several places, just look at IMO 2014/5. A problem being between categories does not disqualify it, and this is a very nice problem.

Besides, it is much, much more A than C, merely nonstandard A in the style of IMOSL 2016 A2, A3 or 2017 A3.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#9 h Aug 1, 2019, 9:20 PM • 3 Y

Y by ImSh95, SerdarBozdag, Adventure10

Assume for sake of contradiction that neither of the statements is true. Then, for every rational number $r\in(0,1)$ , we have a unique finite set $F(r)\subset S$ such that
$r=\sum_{x\in F(r)}1/x.$ For the purposes of this assertion, having $1$ in $S$ won't affect anything since $1\not\in F(r)$ for all $r\in(0,1)$ as $r<1$ , so WLOG assume $1\not\in S$ .

Suppose $x,y\in S$ with $x>y$ . Then
$1/x+(1/y-1/x)=1/y,$ so if $x\not\in F(1/y-1/x)$ then we have two different ways of representing $1/y$ namely $\{y\}$ and $F(1/y-1/x)\cup\{x\}$ . Thus, $x\in F(1/y-1/x)$ , so
$1/x\le 1/y-1/x$ which means that $x\ge 2y$ . So if we order $S$ as
$S=\{x_1<x_2<\cdots\},$ we must have $x_{k+1}\ge 2x_k$ . This means that $x_{k+1}\ge 2^k x_1$ .

However, note that if $r$ can be made, then certainly
$r<\sum_{x\in S}1/x.$ This is true for $r$ arbitrarily close to $1$ , so
$\sum_{x\in S}1/x\ge 1.$ But since $x_{k+1}\ge 2^k x_1$ , $\sum_{x\in S}1/x\le 2/x_1$ , so $2/x_1\ge 1$ , so $x_1=2$ . Thus,
$S=\{2,4,8,16,32,\ldots\}.$ Clearly $1/3$ is not a finite sum of these, so we have our desired contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

21 posts

#10 h Aug 2, 2019, 11:35 AM • 5 Y

Y by ImSh95, Adventure10, Mango247, Mango247, Mango247

I think it is trivial,because card(2^S)>card(Q),isn’t it correct?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#11 h Aug 2, 2019, 6:23 PM • 2 Y

Y by ImSh95, Adventure10

@above
Finite subsets of S. Cardinality of those is same as Q

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

62861

#12 h Aug 2, 2019, 8:06 PM • 3 Y

Y by aopsuser305, ImSh95, Adventure10

Compare with https://artofproblemsolving.com/community/c6h37239p233042

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#13 h Aug 2, 2019, 8:43 PM • 2 Y

Y by ImSh95, Adventure10

@above
huh this is basically the exact same problem....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

62861

#14 h Aug 2, 2019, 9:11 PM • 4 Y

Y by yayups, aopsuser305, ImSh95, Adventure10

Now you know why this didn't appear on a mop test

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1576 posts

#15 h Aug 7, 2019, 4:53 PM • 2 Y

Y by ImSh95, Adventure10

Suppose the contrary, namely that all rationals $0<r<1$ can be expressed uniquely. Clearly, this means that $S$ is infinite. Also, suppose $1\not\in S$ , since this relaxes condition 1, and doesn't impact 2. Finally, define $S_r$ to be the unique subset of $S$ which generates $r$ .

Given $n\in \mathbb{Z}^+$ , suppose that there exists $x\in S\cap[n,2n)$ such that $x\not\in S_{1/n}$ . Then, the set $S_{1/n-1/x}\cup\left\{x\right\}$ also generates $1/n$ , which contradicts uniqueness. Therefore, such an $x$ doesn't exist. So, all $S\cap[n,2n)\subseteq S_{1/n}$ . However, the sum of reciprocals of 2 numbers in this range already exceeds $1/n$ , so $|S\cap[n,2n)|\le 1$ . Now, consider the intervals $[2,4)$ , $[4,8)$ , etc. As there is at most 1 number from $S$ in each set, $\sum\limits_{x\in S}1/x\le 1$ , with equality iff $S=\left\{2^x\arrowvert x\ge 1\right\}$ . Unfortunately, this choice of $S$ doesn't work, so the inequality is strict, and we can find a sufficiently small epsilon such that $1-\epsilon$ is unexpressible. This is a contradiction, as desired.

This post has been edited 2 times. Last edited by william122, Aug 7, 2019, 4:54 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

691 posts

#16 h Feb 4, 2020, 1:40 AM • 2 Y

Y by ImSh95, Adventure10

Assume that both assertion doesn't hold, that is, there exists a set $S$ of positive integers such that
For every positive rational number $r < 1$ , there exists a unique finite subset $F$ of $S$ such that
$\sum_{x \in F} \frac{1}{x} = r$
Obviously $S$ is infinite, otherwise take $r < \frac{1}{\max S}$ and this contradicts the second statement.

Claim 01. There doesn't exists any two element $a,b \in S$ such that $a < b < 2a$ .
Proof. Suppose otherwise, then we have $\frac{1}{b} < \frac{1}{a} < \frac{2}{b}$ . Therefore, we can construct $\frac{1}{a}$ in two ways: which is just the partition of $\frac{1}{a}$ , which exists by the hypothesis, or $\frac{1}{b}$ and the partition of $\left( \frac{1}{a} - \frac{1}{b} \right)$ , a contradiction.

Now, consider the elements of $S$ ordered from the smallest number: $a_1 < a_2 < a_3 < \dots$
By Claim 01, we have $a_{i + 1} \ge 2a_i$ for every $i \in \mathbb{N}$ .
We could WLOG $a_1 \not= 1$ , as whether $1$ is in or not won't affect the problem as the hypothesis only holds for $r < 1$ .
Claim 02. $a_1 = 2$ .
Proof. Suppose otherwise, that $a_1 = 3$ . Then
$\sum_{x \in S} \frac{1}{x} \le \sum_{i = 0}^{\infty} \frac{1}{2^i \cdot 3} = \frac{2}{3}$ Taking $r > \frac{2}{3}$ , this clearly won't satisfy.
In a similar method, one can prove that $a_i = 2^i$ for every $i \in \mathbb{N}$ .
Now, we'll prove that $r = \frac{1}{3}$ is not attainable.
To prove this, we claim that the denominator of $r$ will stay $0$ modulo $3$ at the whole process of subtraction.
$r - \frac{1}{2^k} = \frac{1}{3 \cdot N} - \frac{1}{2^k} = \frac{2^k - 3 \cdot N}{3 \cdot N \cdot 2^k}$ It's clear enough that $2^k - 3 \cdot N$ is not $0$ modulo $3$ , and therefore we've finished.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

946 posts

Plops

#17 h Mar 25, 2020, 5:59 AM • 1 Y

Y by ImSh95

In my proof, I implicitly use the fact that $\sum_{n=1}^{\infty} \frac{1}{n}$ diverges.

Assume $(2)$ doesn't hold. Then, clearly $S$ is an infinite set of positive integers. Given two finite subsets $A$ and $B$ of $S$ , and WLOG $\sum_{x \in A}^{} \frac{1}{x} > \sum_{x \in B}^{} \frac{1}{x}$ . It suffices to prove
$\sum_{x \in A}^{}\frac{1}{x}=r \text{ and } \sum_{x \in B}^{}\frac{1}{x}=r-\epsilon \text{ such that }\epsilon<\text{ min }{\frac{1}{x} : x \in A \cup B}$ Consider successively deleting $\frac{1}{l}$ from $\sum_{x \in A}^{}\frac{1}{x}$ where $l$ is the maximal element of $A$ , and let $A$ now be the new sequence of integers obtained from deleting $l$ . We do this until $\sum_{x \in A \setminus{j}}^{} \frac{1}{x} < \sum_{x \in B}^{} \frac{1}{x}$ where $j$ is the maximum element set $A$ .
We consider our current sets $A$ and $B$ from now on. Like in the above notation, let $\sum_{x \in A}^{} \frac{1}{x}-\sum_{x \in B}^{} \frac{1}{x}=\epsilon$ . Furthermore, let $j$ be the maximal element of $A$ . Then, $\sum_{x \in A \setminus{j}}^{} \frac{1}{x} < \sum_{x \in B}^{} \frac{1}{x} \implies \epsilon=\sum_{x \in A}^{} \frac{1}{x}-\sum_{x \in B}^{} \frac{1}{x}< \frac{1}{j}$ .
Then, let $w$ be the maximal element of $B$ and consider the set $B'=\{u \in \mathbb{Z}: u>w\}$ . Now, consider adding the least remaining element of $B'$ , $m$ for convenience to $B$ , and call the new set $B \cup \{m\}$ as $B$ , and let $\sum_{x\in A}^{}\frac{1}{x}-\sum_{x\in B}^{}\frac{1}{x}=\epsilon$ as before. We keep applying the above operation to $G$ until $\epsilon>0$ and applying the operation $1$ more time results in $\epsilon<0$ . Let the number we add to $G$ such that $\epsilon<0$ be $l$ . Then
$\sum_{x \in A}^{} \frac{1}{x}-\sum_{x\in B}^{} \frac{1}{x}-\frac{1}{l}<0 \implies \epsilon-\frac{1}{l}<0 \implies \epsilon<\frac{1}{l}$ However, $\epsilon<\{\frac{1}{x}:x \in A \} \text{ and } \epsilon<\frac{1}{l}<\{\frac{1}{x}: x \in B \}$ .
Therefore, given $(2)$ does not hold, we can find finite subsets $A$ and $B$ of $S$ such that $\sum_{x \in A}^{}\frac{1}{x}=r \text{ and } \sum_{x \in B}^{}\frac{1}{x}=r-\epsilon \text{ such that }\epsilon<\{\text{ min }{\frac{1}{x} : x \in A \cup B}\}$ , and there must exist a finite subset $L$ of $S$ completely distinct from $F$ and $G$ such that $\sum_{x\in L}^{} \frac{1}{x}=\epsilon \implies \sum_{x \in A}^{} \frac{1}{x}=\sum_{x \in B \cup L}^{} \frac{1}{x}$
Otherwise, $(2)$ holds, and we are done.

This post has been edited 3 times. Last edited by Plops, Mar 25, 2020, 3:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#18 h Mar 29, 2020, 10:41 PM • 2 Y

Y by ImSh95, sabkx

Solved with eisirrational and Th3Numb3rThr33.

Assume for contradiction both fail. Then for each $r<1$ there is a unique finite subset $R(r)$ of $S$ such that $\textstyle\sum_{x\in F}1/x=r$ .

Claim: There are no two elements $a,b\in S$ with $a<b<2a$ .

Proof. Let $a,b\in S$ with $a<b$ , so that $R(1/a)=1/a$ and $R(1/b)=1/b$ . Note that if $\frac1b\notin R\left(\frac1a-\frac1b\right),$ then $R(1/a-1/b)\cup\{1/b\}$ is another way to represent $1/a$ , contradiction. Hence $\frac1a-\frac1b\ge\frac1b\implies b\ge2a,$ as claimed. $\blacksquare$

Now if $S$ is finite, then (ii) clearly holds, and if $1\in S$ , we may delete it since it is not $R(r)$ for all $r<1$ . Thus we have $\sum_{x\in S}\frac1x\le\frac12+\frac14+\frac18+\cdots=1,$ where equality holds if and only if $S=\{2,4,8,\ldots\}$ . If equality fails, then some $r<1$ cannot be represented, but if $S=\{2,4,8,\ldots\}$ , then it is impossible to represent $1/3$ , the end.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

20 posts

Remon

#19 h Mar 30, 2020, 2:35 AM • 1 Y

Y by ImSh95

There are many similar question.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

946 posts

Plops

#20 h Mar 30, 2020, 2:56 PM • 1 Y

Y by ImSh95

Indeed: Problem $6$ from this has a similar taste.

This post has been edited 1 time. Last edited by Plops, Mar 30, 2020, 2:56 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

300 posts

hansu

#21 h Apr 24, 2020, 11:44 AM • 1 Y

Y by ImSh95

Functional wrote:

Given any set $S$ of postive integers, show that at least one of the following two assertions holds:

(1) There exist distinct finite subsets $F$ and $G$ of $S$ such that $\sum_{x\in F}1/x=\sum_{x\in G}1/x$ ;

(2) There exists a positive rational number $r<1$ such that $\sum_{x\in F}1/x\neq r$ for all finite subsets $F$ of $S$ .

Assume to the contrary such a set exists. We begin by observing that $S$ must be infinite. Now suppose that $S=\{a_1,a_2,\ldots\}$ , where $a_{i+1}>a_i$ . Also observe that $1\not\in S$ . If we had $\frac{1}{a_i}-\frac{1}{a_{i+1}}< \frac{1}{a_{i+1}}$ , then we are violating (2). Then we must have $\frac{1}{a_i}\ge \frac{2}{a_{i+1}}\implies a_{i+1}\ge 2a_i$ . Thus we must have $a_i\ge 2^i$ . Suppose $N$ is the smallest positive integer such that $a_N>2^N$ . Then we have
$\sum_{x\in S}<1$ This again violates (2). But if $S=\{2,4,8,\ldots\}$ , we can not represent $\frac{1}{3}$ using finitely many elements of $S$ , a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

830 posts

niyu

#22 h Jul 3, 2020, 8:16 PM • 1 Y

Y by ImSh95

Really nice problem!

If $S$ is a finite set, there are only a finite number of subsets of $S$ ; hence, as there are an infinite number of rational numbers $r < 1$ , condition (2) is true. Henceforth, we assume $S$ is an infinite set.

Suppose condition (2) is false, i.e. for each rational number $r < 1$ , there exists a finite subset $F_r$ of $S$ such that $\sum_{x \in F_r} \frac{1}{x} = r$ . In what follows, we assume that $1$ is not an element of $S$ ; since $1 \not\in F_r$ , removing $1$ from $S$ if it exists will not alter the truth of condition (2). We will show that condition (1) is true.

Main Claim: There exist $u, v \in S$ for which $u > v > \frac{u}{2}$ .

Proof: Suppose not, and let the elements of $S$ be $1 < a_1 < a_2 < \cdots$ . For each $i > 1$ , we have $\frac{a_{i + 1}}{a_i} \geq 2$ , so $a_k \geq 2^{k - 1}a_1$ . Hence, we have
$\begin{align*} T &= \sum_{i = 1}^\infty \frac{1}{a_i} \\ &\leq \sum_{i = 1}^{\infty} \frac{1}{2^{i - 1}a_1} \\ &\leq \frac{1}{a_1}\sum_{i = 0}^\infty \frac{1}{2^i} \\ &\leq \frac{2}{a_1} \\ &\leq 1. \end{align*}$ Equality holds iff $a_k = 2^k$ for each $k$ . If $T < 1$ , pick a rational number $r$ for which $1 > r > T$ . We have
$\begin{align*} r = \sum_{x \in F_r} \frac{1}{x} < \sum_{x \in S} \frac{1}{x} = T < r, \end{align*}$ contradiction. Hence, we must have $T = 1$ , implying that $a_k = 2^k$ for each $k$ . However, as $S$ is the set of powers of $2$ larger than $1$ , there is no finite subset $F \in S$ such that $\sum_{x \in F} \frac{1}{x} = 0.\overline{1}_2 = \frac{1}{3}$ , contradicting the existence of $F_{\frac{1}{3}}$ . Thus, we have reached a contradiction, proving the claim. $\blacksquare$

Now, consider $u, v \in S$ for which $u > v > \frac{u}{2}$ . Note that $\frac{1}{v} - \frac{1}{u} < \frac{1}{u}$ , so $F_{\frac{1}{v} - \frac{1}{u}}$ does not contain $u$ . Let $F = F_{\frac{1}{v} - \frac{1}{u}} \cup \{u\}$ . We have $F \neq \{v\}$ , and $\sum_{x \in F} \frac{1}{x} = \sum_{x \in \{v\}} \frac{1}{x}$ . Thus, condition (1) is true, so we are done. $\Box$

This post has been edited 2 times. Last edited by niyu, Jul 23, 2020, 12:52 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1081 posts

#23 h Oct 18, 2020, 3:46 AM • 1 Y

Y by ImSh95

Solution

This post has been edited 2 times. Last edited by blacksheep2003, Oct 18, 2020, 3:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#24 h Mar 23, 2021, 11:40 PM • 1 Y

Y by ImSh95

FTSoC assume both are false. Let $s(\mathcal{F})$ for every $\mathcal{F} \subseteq S$ be the sum of $\tfrac 1x$ over all $x \in \mathcal{F}$ . Then we have $s$ is injective, and surjective on $(0, 1)$ . We claim, that we can actually uniquely define $S$ .

Let $x, y$ be elements of $S$ . WLOG $1 \not \in S$ since we are only given the surjective condition on $< 1$ , so this $1$ term would not matter. WLOG $x > y$ , then if $\tfrac 1y - \tfrac 1x \in (0, 1)$ note that $x$ must be in the set $F$ for which $s(F) = \tfrac 1y - \tfrac 1x$ , else there are two ways of representing $s(F)$ , by simply using $y$ or using both $F$ combined with $x$ . So this tells is $x \geq 2y$ by bounding.

Next, we rank $S$ 's elements in order $a_1 < a_2 < \ldots$ where by the previously derived condition, clearly $a_{i+1} \geq 2a_i$ . We will show that in fact, equality must hold. If not, then choosing $r = 1 - \epsilon$ cannot be achieved. Hence indeed, we can directly classify $S$ as the set of all powers of $2$ at least $2$ . But this set clearly is not surjective, contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pipitchaya.s4869

18 posts

pipitchaya.s4869

#25 h Mar 24, 2021, 8:45 AM • 1 Y

Y by ImSh95

Also Thailand TST 2019

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

29 posts

#26 h Apr 8, 2021, 1:09 PM • 1 Y

Y by ImSh95

assume that both statement fail
For each r there exists F such that the sum of the reciprocal of the numbers in F is r . Suppose F={a1,a2,……aj}
obviously, we have S is infinite, othwise statement 2 holds.
(1) if there exists an number m such that r/2<m≤r and m is not in F
use statement 2, we have a subset F1 such that the sum of the reciprocal of the numbers in F is r-m
notice that r-m < r/2 < m so m is not in F1
regard F1∪{m} and F, we have a contradiction.
(2) else, suppose a is in S, regard the region (a,2a)
let r be 2a by using (1), we have that there's no number in that region which is also in S
using the same method, we have: The maximum of the sum of the reciprocal of the numbers in S and ≤a is a+2/a+4/a+……
let r be 2a-ε so 2/a,4/a,…… is all the number in S and <a but since all numbers in S are intigers, we have a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

77 posts

#27 h Jun 13, 2021, 2:27 PM • 1 Y

Y by ImSh95

Let $A$ be the set $\{1/x \mid x \in S\}$ . Clearly, $A$ contains an infinite number of elements. Let the elements of $A$ be $a_1 \ge a_2 \ge a_3 \ge \dots$
For some $r \in \mathbb{Q}$ , let $A(r)$ denote the set of elements in $A$ which sum to $r$ .

FTSOC, assume that both conditions are false.

Then, from condition (1) we have that all elements of $A$ are distinct. Furthermore, from (2) we have the following:

Claim: $a_{i+1} \le a_{i}/2$
Proof. Otherwise, we can choose $r$ such that $2a_i > 2a_{i+1} > r > a_i$ . Then, $r-a_i < a_i$ and $r-a_{i+1} < a_{i+1}$ so the distinct sets $a_i \cup A(r-a_i)$ and $a_{i+1} \cup A(r-a_{i+1})$ both sum to $r$ , contradiction. $\square$

As we are considering $r<1$ , we can assume that $a_1 \le 1/2$ . Then the previous claim implies that $a_2 \le 1/4$ , $a_3 \le 1/8$ , and so on. If one of the preceding inequalities is strict, then the sum of all elements of $A$ is less than 1, contradicting (2). Otherwise, the elements of $A$ must be $1/2, 1/4, 1/8, 1/16, \dots$ , so numbers like $1/7$ cannot be written as a sum of distinct elements of $A$ , contradiction.

Remark

This post has been edited 1 time. Last edited by peatlo17, Jun 13, 2021, 2:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

434 posts

#28 h Jul 1, 2021, 8:34 PM • 1 Y

Y by ImSh95

Suppose both statements' negations are true. In other words, every rational number $r<1$ can be expressed as $\sum_{x\in F} 1/x = r$ for some finite subset $F$ and such subset is unique.

Claim: There cannot exist $a,b\in S$ with $a<b < 2a$ .

Proof. By assumption there then exists subset $F$ with
$\sum_{x\in F} 1/x = \frac1a - \frac1b < \frac 2b - \frac 1b = \frac 1b < \frac{1}{a},$ so $a,b\not\in F,$ implying that
$\sum_{x\in F\cup\{b\}} = \frac{1}{a},$ Contradiction. $\blacksquare$

Claim: For all $x>1$ with $x\in S,$ $\sum_{x\in S} 1/x \ge 1.$

Proof. Suppose not, and that $\sum_{1<x \in S} 1/x = r < 1,$ then $r+\varepsilon < 1$ for sufficiently small $\varepsilon \in \mathbb Q$ cannot be obtained, contradiction. $\blacksquare$

However, it is obvious then from our first claim that,
$\sum_{1< x \in S} 1/x \le \sum_{i=1}^\infty \frac{1}{2^i} = 1,$ So from our earlier claim, this forces $S = \{2,4,8,\cdots\}.$ Consequently, each rational $r<1$ is uniquely expressible as its binary representation. However, $2/3 = 0.\overline{10}_2$ is infinitely periodic, meaning no such finite subset of $S$ has elements' sum of $2/3,$ contradiction. Therefore, we conclude at least one of the statements must be true. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1040 posts

508669

#29 h Aug 25, 2021, 11:16 AM • 1 Y

Y by ImSh95

Functional wrote:

Given any set $S$ of positive integers, show that at least one of the following two assertions holds:

(1) There exist distinct finite subsets $F$ and $G$ of $S$ such that $\sum_{x\in F}1/x=\sum_{x\in G}1/x$ ;

(2) There exists a positive rational number $r<1$ such that $\sum_{x\in F}1/x\neq r$ for all finite subsets $F$ of $S$ .

FTSoC such a set $S$ exists which satisfied both the conditions. The second condition implies that $|S|$ is infinite. If there exists $x, y \in S$ such that $y \in [x, 2x]$ , then we see that choosing elements $s_1, s_2 \dots s_k \in S$ such that $\sum\limits_{i=1}^k s_i = \frac{1}{x} - \frac{1}{y} < \frac{1}{y}$ , then $\sum\limits_{i=1}^k s_i + \frac{1}{y} = \frac{1}{x}$ , a contradiction to condition $2$ . We now remove $1$ from $S$ as it is not useful to $S$ now. We see that $\sum\limits_{x \in S} \frac{1}{x} \leq \sum\limits_{i=1}^{\infty} \frac{1}{2^i} = 1$ , which means that if $S \neq \{ 2, 4, 8 \dots \}$ then there exists arbitrarily small positive reals $\epsilon$ for which $1 - \epsilon$ cannot be represented as $\sum\limits_{i=1,x_i\in S}^k \frac{1}{x_i} = 1-\epsilon$ and if $S = \{2, 4, 8 \dots \}$ then any fraction $\frac{p}{q}$ with $\text{rad}(q) \neq 2^k$ for some $k \in \mathbb{Z}^+$ cannot be represented as in the second condition, a contradiction. Therefore no such set $S$ which satisfies both the conditions.

This post has been edited 1 time. Last edited by 508669, Aug 25, 2021, 11:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

238 posts

#30 h Apr 28, 2022, 11:58 PM • 1 Y

Y by ImSh95

Assume that both conditions are not satisfied.

Let $s$ be the smallest element of $S$ . Suppose that there is an $r \in S$ such that $s<r<2s$ . Now, observe that there exists a subset $F$ of $S$ such that $\frac{1}{s}-\frac{1}{r}= \sum_{x \in F} \frac{1}{x}$ . Observe that if $r \not \in F \implies \frac{1}{s}= \sum_{x \in F \cup \{r\}} \frac{1}{x}$ , a contradiction since $s \in S$ . Thus, $r \in F \implies \frac{1}{2s} > \frac{1}{s}-\frac{1}{r} \geq \frac{1}{r}> \frac{1}{2s}$ , contradiction.

Now, let $r \geq 2s$ be the smallest element of $S$ greater than $s$ . Then, $\frac{1}{2s} \leq \frac{1}{s}-\frac{1}{r}= \sum_{x \in F} \frac{1}{x}$ for some subset $F$ of $S$ . If $r \not \in F$ , then $\frac{1}{s}=\sum_{x \in F \cup \{r\}} \frac{1}{x}$ , a contradiction, since $s \in S$ . Thus, $r \in F \implies \frac{1}{r} \geq \frac{1}{s}-\frac{1}{r}= \sum_{x \in F} \frac{1}{x} \geq \frac{1}{r} \implies \frac{1}{s}-\frac{1}{r}=\frac{1}{r} \implies r=2s$ .
By the same argument, we can prove that $S=\{s,2s,2^2s,2^3s,...\}$ . If $s>2$ , then $\sum_{x \in S} \frac{1}{x}$ converges to a number less than $1$ , so we can take a rational number in the interval $(\sum_{x \in S} \frac{1}{x},1)$ ( $\mathbb{Q}$ is dense in $\mathbb{R}$ ) to reach a contradiction.
Thus, $s=1$ or $s=2$ . If $s=1$ , we can simply ignore $s$ from $S$ , so assume WLOG that $s=1$ . But then $\frac{1}{3}$ cannot be represented as $\sum_{x \in F} \frac{1}{x}$ where $F$ is a finite subset of $S$ , so we are done.
$\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1692 posts

awesomeming327.

#31 h Mar 6, 2023, 1:11 AM

Y by

Let both of the statements be false. We have that for each $r\in (0,1)$ there exists a unique subset $S(r)$ such that $\sum_{x\in S(r)}\left(\frac{1}{x}\right)=r$ Clearly $S$ must not be finite, since then there is a finite number of possible $S(r)$ but an infinite number of rational numbers, and there cannot be a bijection there. Now, suppose there exist $a,b\in S$ such that $a<b<2a$ then $\frac{1}{a}-\frac{1}{b}\le \frac{1}{b}$ which means that $b\notin S(\tfrac{1}{a}-\tfrac{1}{b})$ so $\{a\}=S(\tfrac{1}{a})=S(\tfrac{1}{a}-\tfrac{1}{b})\cup \{b\}$ , impossible. Now, let any two consecutive terms of $S$ arranged in increasing order be $a>b$ . If $a>2b$ then it is easy to see that there is no way to represent $r\in(\tfrac{2}{a},\tfrac{1}{b})$ . If we have nothing smaller than $a$ then the maximum we can get is $\frac{1}{a}+\frac{1}{2a}+\frac{1}{4a}+\dots = \frac{2}{a}$ and if we have something smaller than $a$ then the minimum we can get is $\tfrac{1}{b}$ . Therefore, we must have $S=\{a,2a,4a,8a,\dots\}$ and the maximum sum will be $\tfrac{1}{a}$ so $a=1$ . Since we have found $S$ , we can very confidently say that there are so many rational numbers that don't have a corresponding subset.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7586 posts

#32 h Mar 11, 2023, 3:48 AM

Y by

Amazing!

Assume that neither assertion holds. Then suppose FTSOC that $x,y\in S$ satisfy $x<y<2x$ . By considering
$\frac{1}{x}=\frac{1}{y}+\left(\frac{1}{x}-\frac{1}{y}\right)$ we can actually generate two different subsets of $S$ , violating the first condition.

However we also know that if we sum the reciprocals of all elements $x\in S$ satisfying $x>1$ we obtain a value which is at least $1$ (else we violate the second condition). This implies that these elements are exactly the powers of $2$ . However by considering base $2$ we find that $\frac{1}{3}$ isn't achieveable so we are done. $\blacksquare$

This post has been edited 1 time. Last edited by asdf334, Mar 11, 2023, 3:49 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

136 posts

sman96

#33 h Apr 19, 2023, 5:43 AM

Y by

Let, $S = \{x_1, x_2, x_3, \dots\}$ where, $x_1 < x_2 < \dots < x_n < x_{n+1} < \dots$
Now, there are two cases,

$\textbf{Case 1:}$ There exists $k$ s.t. $x_{k+1} < 2x_k$
If the second condition doesn't hold, for all $1 > r \in \mathbb Q$ we will get a finite subset $F_r$ that gives the reciprocal sum $r$ .
Now, take $r = \dfrac{x_{k+1} - x_k}{x_kx_{k+1}}$ . Then by our condition we get $r < \dfrac1{x_{k+1}}$ . So, $F_r$ doesn't contain any $x_n$ with $n \leq k+1$ .
Now take, $F = \{x_k\}$ and $G = \{x_{k+1}\} \cup F_r$ and we get our first condition true. $\blacksquare$

$\textbf{Case 2:}$ For all $k$ we have $x_{k+1} \geq 2x_k$
We want to show that the second condition holds.
Notice that, For the second condition it doesn't matter if $1$ is in $S$ or not. So we assume that $1 \notin S$ .
Then, $x_1 \geq 2$ and if we get $x_{k+1} > 2x_k$ at some point then, let $c = \dfrac1{2x_k} - \dfrac1{x_{k+1}}$ and we will get that the total sum of reciprocals of $S$ is at most $1-c$ .
Then we can just take a $r = 1-c + \epsilon$ for small enough $\epsilon > 0$ and we will be done. And similarly if $x_1 \neq 2$ we get a bound $\frac2{x_1}$ on the total sum.
So now the remaining case is $x_i = 2^i$ for all $i$ .
But then we take $r = (0.\overline{01})_2 = (1/3)_{10}$ and if we get a set $F_r$ for this then we will get a finite representation of $r$ in binary which we can easily show that doesn't exist. So we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

966 posts

lrjr24

#34 h Jun 12, 2023, 8:05 PM

Y by

Assume not. Note that $S$ is infinite because otherwise there is only finitely many sums attainable but there is infinite rationals between $0$ and $1$ . Enumerate the elements of $S$ as $s_1 < s_2 < \dots$ . Let $p(F) = \sum_{x \in F} \frac{1}{x}$ . Then for all rational $r<1$ there is a finite set $F \in S$ such that $p(F) = r$ and for all pairs of finite sets $F,G \in S$ , $p(F) \neq p(G)$ .

Let's assume that $s_{k+1} < 2s_k$ for some $k$ . Then consider the assertion of ( $2$ ) for $\frac{1}{s_k}-\frac{1}{s_{k+1}}$ . Note that this value is less than $\frac{1}{s_{k+1}}$ , so the finite set $F$ satisfying the condition only contains terms greater than $s_{k+1}$ . Let $F$ be the satisfying set. Then $p\left(F \cup \{s_{k+1}\} \right) = \frac{1}{s_k} = p\left(\{ s_k \}\right)$ , a contradiction to $(1)$ and so we're done with this case.

Thus $s_{k+1} \ge 2s_k$ for all $k$ . Consider a construction for ( $2$ ). Note that $1$ isn't in it as that would make it too big. WLOG $s_1>1$ (if it's $1$ just chop it off). Note that $\sum_{x \in S} \frac{1}{x}$ converges since it's bounded by $\sum_{i=1}^{\infty} \frac{1}{2^i} = 1$ . If $s_{k+1} > 2s_k$ for some $k$ , $\sum_{x \in S} \frac{1}{x} = \sum_{i=1}^{k} \frac{1}{s_i} + \sum_{i=k+1}^{\infty} \frac{1}{s_i} \le \sum_{i=1}^k \frac{1}{2^i} + \sum_{i=k+1}^{\infty} \frac{1}{2^i+1} < \sum_{i=1}^{\infty} \frac{1}{2^i} = 1$ . Thus if we let $r = \sum_{x \in S} \frac{1}{x}$ , we won't be able to find a set summing to that (they would all be smaller). Thus $s_{k+1}=2s_k$ and $s_k=2^k$ . We finish by taking the assertion for $r=\frac{1}{3}$ and noting that the denominator in any sum would be a power of $2$ , which $3$ obviously isn't. This provides a contradiction and concludes the proof.

This post has been edited 1 time. Last edited by lrjr24, Jun 12, 2023, 8:05 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#35 h Sep 7, 2023, 7:30 PM • 1 Y

Y by centslordm

Let $s(T)$ denote the sum of the reciprocals of some set $T$ . Suppose that neither of these conditions hold. Clearly $S$ is infinite, and let its elements other than $1$ be $1<a_1<a_2<\cdots$ . The key claim is the following.

Claim: We need $a_{i+1} \geq 2a_i$ for all $i$ .
Proof: Suppose otherwise. Then there exists some finite $T \subset S$ such that $s(T)=1/a_i-1/a_{i+1}<1/a_{i+1}$ , so $a_{i+1} \not \in T$ . But then $s(T \cup \{a_{i+1}\})=s(\{a_i\})$ : contradiction. $\blacksquare$

This implies that $\sum_{x \in S} 1/s$ converges and is at most $\sum_{i \geq 1} 1/2^i=1$ , with equality iff $S=\{2,4,8,\ldots,\}$ . But it must be exactly $1$ as well, since we should be able to form numbers arbitrarily close to $1$ , so we need equality. But then we can only form dyadic rationals, so this contradicts condition 2. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AdventuringHobbit

164 posts

AdventuringHobbit

#36 h Sep 26, 2023, 3:35 AM

Y by

Suppose not. Redefine $S$ as a set of reciprocals of whole numbers. Then we can define a function $f(x)$ from rational numbers less than $1$ to finite subsets of $S$ such that $f(x)$ is the unique finite subset whose elements add to $x$ . For the rest of the argument I will give, assume WLOG that $1$ is not in $S$ (this does not change the conclusion). Let $s_i$ denote the $i$ th largest element in $S$ . Observe that $f(s_i)=\{s_i\}$ . This means that for $s_i > s_j$ , we have $s_j \in f(s_i-s_j)$ . Otherwise we could write $s_i=\sum f_(s_i-s_j) \cup \{s_j\}$ . A similar argument shows $s_j \notin f(s_i-2s_j)$ . We can repeat this. In general, $s_j \in f(s_i-(2n+1)s_j)$ for an integer $n$ . Thus, for integers $n$ , if $s_i-(2n+1)s_j>0$ , then $s_i-(2n+1)s_j \ge s_j$ . This means that $\lfloor \frac{s_i}{s_j} \rfloor$ is even for all $i, j$ . This implies that if $a \in S$ , the next smallest element that could possible be in $S$ is $\frac{a}{2}$ . Thus the set $S$ which achieves maximal total sum is the set consisting of fractions which are negative powers of $2$ , which has sum exactly $1$ . If the set $S$ is not this set, then its elements sum to less than $1$ , so we can find a contradiction by finding a rational number $p$ such that $p$ is bigger than the sum of $S$ , whence $f(p)$ is undefined. If our set $S$ is the set of negative powers of $2$ , then $f(\frac{1}{3})$ is not defined, because of the requirement that the subsets be finite, and $\frac{1}{3}$ in binary is $0.0111\ldots$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3363 posts

#37 h Nov 24, 2023, 2:54 AM • 1 Y

Y by OronSH

Assume FTSOC there exists an $S$ that doesn't satisfy either assertion. Clearly $S$ must have infinite cardinality. Label the elements of $S$ as $a_1 < a_2 < a_3 \dots$ . Notice that for any $x,y \in S$ and $x>y$ , there must exist a subset $F$ that has the reciprocals of its elements sum to $\frac{1}{y} - \frac{1}{x}$ . Now if $x \notin F$ , then when we simply add $x$ to $F$ , this new set will have its sum be equal to $\frac{1}{y}$ which is it not possible due to the 1st assumption as we can simply take the set $\{ y \}$ . Therefore $x$ must be in $F$ , which implies that $\frac{2}{x} \le \frac{1}{y}$ , and $x \ge 2y$ . Therefore if we have two elements $x > y$ , then we must have $x \ge 2y$ . From this we easily get $a_{i+1} \ge 2 \cdot a_i$ . Now notice that $\sum_{x \in S} \frac{1}{x} \le \sum_{i=0}^{\infty} \frac{1}{2^i \cdot a_{1}} = \frac{2}{a_{1}}$ Now we have $\sum_{x \in S} \frac{1}{x} \ge 1$ because if not, for all $F \subset S$ we will have $\sum_{x \in F} \frac{1}{x} < 1$ , which contradicts second assumption. Now this simply implies that $a_{1} = 1, 2$ and that $a_{i+1} = 2 \cdot a_{i}$ . Now simply take a rational with denominator not a power of $2$ . This set cannot achieve such a rational, so we have achieved a contradiction.

This post has been edited 2 times. Last edited by pi271828, Nov 24, 2023, 2:55 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

176 posts

#38 h Jan 11, 2024, 12:20 PM

Y by

Nice problem. It looks like a difficult problem, but it isn't.
I have solved this in the same way as (4)

Therefore not uploading

This post has been edited 1 time. Last edited by lelouchvigeo, Jan 11, 2024, 12:20 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

180 posts

dkedu

#39 h Jan 27, 2024, 7:23 PM

Y by

AFTSOC that both statements are true.

Claim: $\frac{1}{s_1} = \sum_{i\ge2}\frac{1}{s_i}$ .

If $\frac{1}{s_1} > \sum_{i\ge2}\frac{1}{s_i}$ , then there exists a rational number $r$ between $1$ and $\sum_{i\ge1}\frac{1}{s_i}$ since $\sum_{i\ge1}\frac{1}{s_i} < \frac{2}{s_1} \le 1$ and the rationals are dense in the reals.

If $\frac{1}{s_1} < \sum_{i\ge2}\frac{1}{s_i}$ , then there must exist a $k$ such that $\frac{1}{s_1} < \sum_{i=2}^k \frac{1}{s_i}$ and $\frac{1}{s_1} > \sum_{i=2}^{k-1} \frac{1}{s_i}$ . Now by assumption, there exists a set $A$ such that $\sum_{a\in A} \frac{1}{s_i} = \left(\sum_{i=2}^k \frac{1}{s_i}\right) - \frac{1}{s_1} < \frac{1}{s_k}$ . So all elements of $A$ must be less than $k$ , so we can just take $\{1\} \cup A$ and $\{2, \dots, k\}$ to get a contradiction, so we have proven the claim.

Now note that $s_1= 2$ otherwise $r = 1 - \epsilon$ gives a contradiction. Now this argument clearly works for $s_2$ as well, by only considering numbers under $\frac{1}{2}$ so we get that $s_i = \frac{1}{2^i}$ . Now taking $r = \frac{1}{3}$ gives a contradiction so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1475 posts

#40 h Nov 7, 2024, 11:42 PM

Y by

The problem is trivial if $S$ is finite, so suppose it's infinite, FTSOC assume that neither of the claims was true, then trivially all elements of $S$ are distinct from each other so we let $S= \{a_1, a_2, \cdots \}$ where we have them ordered in increasing order, meaning that $a_i<a_{i+1}$ and also note that $a_1 \ge 2$ since if a set had $1$ and satisfied the condition then so will $S-{1}$ , so it doesn't really matter.
First we take two elements $a_k>a_j$ (so of course $k>j$ ), then consider $\sum_{x \in S_{k,j}} \frac{1}{x}=\frac{1}{a_j}-\frac{1}{a_k}$ , suppose FTSOC that $2a_j>a_k$ , then it's clear that in $S_{k,j}$ a subset of $S$ we can't have $a_k$ on it for size reasons, so now note that we have $\sum_{x \in S_{k,j} \cup (a_k)} \frac{1}{x}=\frac{1}{a_j}$ which contradicts the opposite of (1), therefore we have $a_k \ge 2a_j$ , this in general implies that $a_{i+1} \ge 2a_i$ for any $i \in \mathbb Z_{>0}$ .
Now suppose FTSOC that we have some $i$ for which $a_{i+1}>2a_i$ , then consider a rational number $r$ strictly between $\frac{2}{a_{i+1}}$ and $\frac{1}{a_i}$ , then let $S_1$ be the finite subset such that $\sum_{x \in S_1} \frac{1}{x}=r$ , notice that for size reasons we can't have any $a_1, \cdots a_i$ on $S_1$ therefore $\sum_{x \in S_1} < \frac{1}{a_{i+1}} \left(1+\frac{1}{2}+\cdots \right)=\frac{2}{a_{i+1}}$ which contradicts the existence of $r$ , therefore $a_{i+1}=2a_i$ must be true for all $i \in \mathbb Z_{>0}$ .
Therefore we have that $S$ is of the form $(\ell, 2\ell, 4\ell, \cdots )$ but now it's impossible to create $\frac{2}{\ell}$ for all $\ell \ge 3$ meaning that either $\ell=1$ or $2$ , but since we can get rid of $1$ we can just consider $\ell=2$ in which case we have $S$ of the form $(2, 4, 8 \cdots)$ in which from $v_2$ and base $2$ we can check that it happens to be impossible to make $\frac{1}{3}$ , thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

53 posts

#41 h Dec 30, 2024, 1:41 PM

Y by

Suppose ftsoc that a set $S$ doesn't satisfy any of the two conditions. Clearly, $S$ must be infinite. For a rational number $r\ge 0$ , call its decomposition $F\subset S$ if $\sum_{x\in F}\frac{1}{x}=r$ . Any rational number $r<1$ has a unique decomposition, and no rational number has more than one decomposition. We start with a fairly simple observation :

Claim : For any element $s\in S$ and any rational number $r\in \left[\frac{1}{s}; \frac{2}{s}\right[$ , $r$ has a unique decomposition, which contains $s$ . Moreover, if any rational number $r\in \left[\frac{2}{s}; \frac{3}{s}\right[$ has a decomposition, it does not contain $s$ .
Proof : For the first part : note that $r-\frac{1}{s}\in \left[0;\frac{1}{s}\right[$ . Therefore $r-\frac{1}{s}$ has a unique decomposition, and it cannot contain $s$ . It follows that $r$ has a decomposition which contains $s$ .
Now, suppose some $r\in \left[\frac{2}{s}; \frac{3}{s}\right[$ has a decomposition which contains $s$ . Then, $r-\frac{1}{s}\in \left[\frac{1}{s}; \frac{2}{s}\right[$ has a decomposition which doesn't contain $s$ , which is a contradiction. $\square$

This leads to the following claim :

Claim : Suppose $S=\{a_1,a_2,\ldots\}$ where $a_1<a_2<\ldots$ . Then, for each positive integers $k$ and $n$ , we have $a_{k+1}\ge 2a_k$ and $\frac{1}{a_k}>\sum_{i=1}^{n}\frac{1}{a_{k+i}}$ .
Proof : Note that $r=\frac{1}{a_{k}}+\frac{1}{a_{k+1}}>\frac{2}{a_{k+1}}$ is a rational number which contains $a_{k+1}$ in its decomposition. Therefore, it must be the case that $r\ge \frac{3}{a_{k+1}}$ by our claim, which gives $a_{k+1}\ge 2a_k$ . Now, suppose that some $k$ and $n$ are such that $\frac{1}{a_k}\le \sum_{i=1}^{n}\frac{1}{a_{k+i}}$ , and take the minimal such $n$ . We then have $\sum_{i=1}^{n}\frac{1}{a_{k+i}}\in \left[\frac{1}{a_k}; \frac{2}{a_k}\right[$ , which contradicts our claim since its decomposition must contain $a_k$ . $\square$

Let us fix some $k\in \mathbb N$ . The sequence $x_n=\sum_{i=1}^{n}\frac{1}{a_{k+i}}$ is increasing and bounded above, so it must have a limit $l=l(k)$ , which must not be larger than $a_k$ by our claim. If $l<\frac{1}{a_k}$ , then any rational number $q\in \left]l;\frac{1}{a_k}\right[$ does not have a decomposition. This is a contradiction, since every number in this interval is smaller than $1$ .

Therefore, we must have $l(k)=\frac{1}{a_k}$ . Since $a_{k+i}\ge 2^ia_k$ , it must be the case that $a_{k+i}=2^ia_k$ for every $i$ and $k$ . If not, then clearly $l(k)<\frac{1}{a_k}$ by an easy geometric series argument. In particular, we have $a_k=2^{k-1}a_1$ for every $k$ . This cannot hold, since $\frac{1}{3a_1}$ would not have a decomposition. $\blacksquare$

This post has been edited 1 time. Last edited by Pitchu-25, Dec 30, 2024, 1:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

148 posts

#42 h Apr 1, 2025, 1:56 AM

Y by

Assume the negative of (1) and the negative of (2) for the sake of contradiction, and name these hypotheses (n1) and (n2) respectively. We get that for every rational $r<1$ , there is unique $F$ such that $\sum\limits_{x\in F} \frac{1}{x} = r$ . In particular, (n2) tells us there is at least one set $F$ satisfying the condition and (n1) tells us there is at most one set $F$ satisfying the condition. This means we can define $f(r) = F$ as described here. The domain of $f$ is all positive rational numbers less than 1.

Let $a_0, a_1, a_2, \ldots$ be the elements of $S$ that are not equal to 1 in increasing order
Claim (3): $a_{i+1} \ge 2a_i$ for all nonnegative integers $i$
Proof: By contradiction; assume $a_{i+1} < 2a_i$ . Then, $\frac{1}{a_i} - \frac{1}{a_{i+1}} < \frac{1}{a_i} - \frac{1}{2a_i} = \frac{1}{2a_i} < \frac{1}{a_{i+1}}$ . Thus, $a_{i+1}$ cannot be in the set $f(\frac{1}{a_i} - \frac{1}{a_{i+1}})$ , because if so, it would cause $\sum\limits_{x \in f(\frac{1}{a_i} - \frac{1}{a_{i+1}})} \frac{1}{x} > \frac{1}{a_i} - \frac{1}{a_{i+1}}$ . We may let $G = f(\frac{1}{a_i} - \frac{1}{a_{i+1}}) \cup \{ a_{i+1} \}$ , and $G$ satisfies $\sum\limits_{x \in G} \frac{1}{x} = \frac{1}{a_i} = \sum\limits_{x \in \{ a_i \}} \frac{1}{x}$ , contradicting (n1).

Claim (4): $a_{i+1} \le 2a_i$ for all nonnegative integers $i$
Proof: By contradiction; assume $a_{i+1} > 2a_i$ . This implies $a_{i+1} \ge 2a_i + 1$ . Repeated applications of (3) replacing $i$ with $j+1, j+2, \ldots j+k$ shows that $a_{j+k+1} \ge 2^ka_{j+1}$ for all nonnegative integers $j, k$ . Thus, $\sum\limits_{k=0}^{|S|} \frac{1}{a_{i+k+1}} \le \sum\limits_{k=0}^{|S|} \frac{1}{2^ka_{i+1}} \le \frac{2}{a_{i+1}} \le \frac{2}{2a_i + 1} < \frac{1}{a_i}$ . Let $r_i$ be a rational number such that $\frac{2}{2a_i + 1} < r_i < \frac{1}{a_i}$ . The set $f(r_i)$ cannot include $a_i$ or any term before it, because if so, they would cause $\sum\limits_{x \in f(r_i)} \frac{1}{x} > r_i$ . However, we have shown that, if $f(r_i)$ includes only terms after $a_i$ , then $\sum\limits_{x \in f(r_i)} \frac{1}{x} \le \frac{2}{2a_i+1} < r_i$ . Thus, the set $f(r_i)$ does not exist, contradicting (n2).

Combining (3) and (4) will give us Claim (5): $a_{i+1} = 2a_i$ for all nonnegative integers $i$
Let $p \neq 2$ be a prime that does not divide $a_0$ .

Repeated application of (5) with $i=0, 1, \ldots k-1$ gives $a_k = 2^k a_0$ for all nonnegative integers $k$ . Because $p$ is not 2 and does not divide $a_0$ , it does not divide $2^k a_0$ either. Therefore, $p$ does not divide $a_k$ for all nonnegative integers $k$ . We must have $\sum\limits_{x \in f(\frac{1}{p})} \frac{1}{x} = \frac{1}{p}$ . After cross-multiplying this sum, we see that $p$ divides $\prod\limits_{x \in f(\frac{1}{p})} x$ . This implies that there exists an $x$ such that $p$ divides $x$ . This contradicts our result that $p$ does not divide $a_k$ for all nonnegative integers $k$ , finishing our proof.

This post has been edited 1 time. Last edited by maromex, Apr 1, 2025, 1:57 AM
Reason: Forgot the not equal to 1 condition

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a