gg

After $A\cup B = (A-a)\cup (B+b)$, we can also write the generating function $A(x) + B(x) = x^{-a}A(x) + x^bB(x)$. We can finish by differentiating at $1$, or equivalently, plugging in $1$ to $\frac{x^a-1}{x^a(x-1)}A(x) = \frac{x^b-1}{x-1}B(x)$. This is really equivalent to the directed cycles solution though.

$A\cup B=(A-a)\cup (B-b)$ $ \Rightarrow $ general means idea. Let $S(X)$ - sum elements of set $X$. Math154, can we easy way for proof to $ S(A)+S(B)=S(A-a)+S(B+b)$ ?

mathuz wrote: Math154, can we easy way for proof to $ S(A)+S(B)=S(A-a)+S(B+b)$ ? That's equivalent to taking the derivative of $A(x) + B(x) = x^{-a}A(x) + x^b B(x)$ at $1$.

thank you, math154! I understand you. It's very nice solution.

I think the main idea is considering all possible cycle in $A$ and $B$, by considering every cycle take any element $i$ and then the next term is either $i+a$ or $i-b$. The minimal index where one element is considered as both sets are finite, w.l.o.g. let the repeated element to be the first term and so within this $a|A_{1}|=b|B_{1}|$, where $|A_{1}|$ is the number of elements in $A$ that appear in the cycle. And since it can be proven that every cycles are disjoint the problem is solved. Unfortunately I thought that only one cycle can exist during the competition, and did not manage to solve it. Anyway the "diffentiating" solution is nice too!

This problem can be tracked back into Math Magazine vol 59 no 4 (Oct 1986), problem proposals #1247

How can it be an APMO problem if it appeared somewhere else? (E.g. APMO 2012 P1 also appeared in somewhere else) For this reasons every year 5 or 6 problems in ISL are rejected immediately in jury's meeting (as said in UK leader report)

Consider these bijections of $A$ and $B$. $A_a=\{i-a:i \in A\},B_b=\{i+b:i \in B\}$. Note that $|A|=|A_a|,|B|=|B_b|$ Now choose any $i \in A \cup B$. Then $i+a \in A$ or $i-b \in B$. If $i+a \in A$, then $i \in A_a$; else if $i-b \in A$, then $i \in B_b$. So every $i \in A \cup B$ maps to either $A_a$ or $B_b$. Hence $A \cup B \subseteq A_a \cup B_b$. So $|A \cup B| \le |A_a \cup B_b| \le |A_a|+|B_b|[\text{PIE}]$ $=|A|+|B|$[Since $A_a,B_b$ are bijections of $A,B$ respectively]. $=|A \cup B|$[Since $A,B$ are disjoint.] Thus $|A \cup B| \le |A_a \cup B_b| \le |A \cup B|$. Hence $A \cup B=A_a \cup B_b$ So we have $|A \cup B|=|A_a \cup B_b| \Rightarrow |A|+|B|=|A_a|+|B_b|-|A_a \cap B_b| \Rightarrow |A_a \cap B_b|=0$. Hence $A_a,B_b$ are disjoint. now let us denote the sum of elements of a set $S$ as $\sum S$. Now $\sum A+\sum B=\sum (A \cup B)=\sum (A_a \cup B_b)=\sum A_a+\sum B_b$ $=\sum A-a|A|+\sum B+b|B| \Rightarrow a|A|=b|B|$, done!

v_Enhance wrote: Let $a$ and $b$ be positive integers, and let $A$ and $B$ be finite sets of integers satisfying (i) $A$ and $B$ are disjoint; (ii) if an integer $i$ belongs to either to $A$ or to $B$, then either $i+a$ belongs to $A$ or $i-b$ belongs to $B$. Prove that $a\left\lvert A \right\rvert = b \left\lvert B \right\rvert$. (Here $\left\lvert X \right\rvert$ denotes the number of elements in the set $X$.) I didnt understand so well, that means that if a belongs to A the i+a also, and if b belongs to B the i-b also?

$a,b$ are given positive integers. If $i$ belongs to either $A$ or $B$, then either $i+a$ belongs to $A$ or $i-b$ belongs to $B$ (or both). For example, if $a = 2, b = 3$ and $i = 10$ is in $A$ (or $B$), then either $10+2 = 12$ is in $A$ or $10-3 = 7$ is in $B$ or both.

Let $A=\{x_{1},..., x_{k}\}, B=\{y_{1},...,y_{m}\}.$ After proving that $ A\cup B = (A-a)\cup (B+b) $ we consider two polynomials $f(x)=(x-x_{1})...(x-x_{k})$ and $g(x)=(x-y_{1})...(x-y_{m})$. They satisfy $f(x)g(x)=f(x+a)g(x-b)$. Let $f(x) = x^{k}+\alpha x^{k-1} + p(x), g(x) = x^{m}+ \beta x^{m-1} +q(x)$. We get $(x^{k}+\alpha x^{k-1} + p(x)) (x^{m}+ \beta x^{m-1} +q(x)) = ((x+a)^{k}+ \beta (x+a)^{k-1} +p(x+a)((x-b)^{m}+ \beta (x-b)^{m-1} +q(x-b))$. Therefore $x^{k+m-1}(\alpha + \beta) = x^{k+m-1}(\alpha + \beta + ak - bm).$ So $ak=bm$.

is it possible that $ A $ or $ B $ had 2 ( or more ) equal elements?

v_Enhance wrote: Let $a$ and $b$ be positive integers, and let $A$ and $B$ be finite sets of integers satisfying (i) $A$ and $B$ are disjoint; (ii) if an integer $i$ belongs to either to $A$ or to $B$, then either $i+a$ belongs to $A$ or $i-b$ belongs to $B$. Prove that $a\left\lvert A \right\rvert = b \left\lvert B \right\rvert$. (Here $\left\lvert X \right\rvert$ denotes the number of elements in the set $X$.) Define $A' = \{ x-a:x \in A \}, B' = \{ x-b:x \in B \}$. Note that $A\cup B\subseteq A' \cup B'$. But $|A'| = |A|, |B'| = |B|$, and $|A \cup B| = |A|+|B|$, since $A,B$ are disjoint. It follows that $A', B'$ are also disjoint. Denote $S(X) = \sum_{x \in X} X$. Hence \begin{align*} S(A) + S(B) = S(A \cup B) = S(A' \cup B') = S(A') + S(B') = S(A) - a|A| + S(B) - b|B| \implies a|A| = b|B|. \end{align*}

The crucial claim is that $$A \cup B= (A-a) \cup (B+b).$$Indeed, note that for all $x \in A \cup B,$ either $x+a \in A$ or $x-b \in B$ which implies that $x \in (A-a) \cup (B+b)$. Note that $$|A \cup B| \le |(A-a) \cup (B+b)|=|A-a|+|B+b|-|(A-a) \cap (B+b)| \le |A-a|+|B+b|=|A|+|B|=|A \cup B|,$$from where the claim follows. Translate the elements in $A,B$ so as to make them positive integers. Let $A(x)= \sum_{a \in A} x^a$ and $B(x)=\sum_{b \in B} x^b$ be the generating functions (formal series) of these two sets and we see that $$A(x)+B(x)=x^{-a}A(x)+x^bB(x) \Longrightarrow A(x)\cdot \left(\frac{x^a-1}{x^a}\right)=B(x)\cdot (x^b-1) \Longrightarrow A(x)\cdot (x^{a-1}+\dots+1)=x^aB(x)\cdot (x^{b-1}+\dots+1).$$As these formal series are "functional" for $0<x \le 1$, we plug in $x=1$ to get $aA(1)=a|A|=bB(1)=b|B|$ and the result follows.

Since this proof isn't directly stated in this thread: We take $T={(e,S)|S \in {A,B}, e \in S}$, and define $f: T \rightarrow T$ so that $f(i,S)$ is either $(i+a,A)$ or $(i-b,B)$ (if both are present, choose anyone). Note that $(i,A)$ can be the image of only $(i-a,A)$ or $(i-a,B)$, and similarly for $(i,B)$ the preimages have the same value of the element. Thus, if $f$ isn't invective, then we'll contradict $A,B$ disjoint. So we can say that $f$ is a bijection. It must be comprised of some disjoint cycles. In each cycle, every element of the form $(i,A)$ is $a$ more than the previous, while every element of the form $(i,B)$ is $b$ less. Traversing along the entire cycle we return to the same element, so if the cycles has $A_1$ elements from $A$ and $B_1$ from $B$, we can say that $aA_1 = bB_1$. Adding over all cycles, the results follows. This is identical to MellowMelon's proof here: http://artofproblemsolving.com/community/c6h486662p2727017. I simply used function terminology to make it a bit spazzier. It actually highlights some useful properties of functions over finite sets, and reveals why bijections are such a powerful tool. It's also useful to think of functions as graphs like we did above.

$A=\{a_1,a_2....,a_m \}, B=\{b_1,b_2....,b_n \}$. Consider polynomials, $$P(x)=(x-a_1)...(x-a_m), Q(x)=(x-b_1)...(x-b_n)$$Let $R(x)=P(x+a)Q(x-b)$. Then, by the given condition, $R(x)$ has roots $a_1,...a_m,b_1,...b_n$ which are distinct. Also, degree of $R(x)$ is $m+n$ so these are the only roots. Using Vieta's formula coefficient of $x^{m+n-1}$ in $R(x)$ is $-(a_1+...+a_m+b_1+...+b_n)$ while the coefficient of $x^{m+n-1}$ in $P(x+a)Q(x-b)$ is $-(a_1+...+a_m+b_1+...+b_n) +am-bn$. Therefore, $am=bn$.

Let $X - x$ denote the set $X$ with each element reduced by $x$, and analogously for $+$. Let $\sum X$ denote the sum of the elements in $X$. Claim: $A\cup B \in (B+b) \cup (A-a)$. Proof. Suppose $i \in A\cup B$. Then $i\in A$ or $i\in B$, which means $i+a \in A$ or $i-b\in B$. Hence $i\in A-a$ or $i\in B+b$, so $i\in (A-a) \cup (B+b)$. $\square$ Claim: $|(B+b) \cup (A-a)| \le |A\cup B|$. Proof. We have \begin{align*} |(B+b) \cup (A-a)| &= |B+b| + |A-a| - |(B+b) \cap (A-a)| \\ &= |B|+|A| - |(B+b) \cap (A-a)| \\ &\le |B|+|A| \\ &= |A\cup B| \end{align*}since $A,B$ are disjoint. $\square$ The above two claims combined give \[ A\cup B = (A-a) \cup (B+b). \]We claim $A-a,B+b$ are disjoint. Indeed, \begin{align*} |A|+|B| &= |A\cup B| \\ &= |(A-a) \cup (B+b)| \\ &=|A-a| + |B-b| -|(A-a)\cap (B-b)| \\ &= |A| +|B| - |(A-a)\cap (B-b)|. \end{align*}So $|(A-a)\cap (B-b)|=0$, as claimed. Now, \begin{align*} \sum (A\cup B) &= \sum (A) + \sum(B), \\ \sum((A-a) \cup (B+b)) &= \sum(A-a) + \sum(B+b) =\left[\sum(A)\right] - a|A| + \left[\sum(B)\right] + b|B|. \end{align*}Since the LHS's are equal, this implies $a|A| = b|B|$, as desired.

Intelligence provided by eisirrational. Create a graph $G$ with each element of $A\cup B$ corresponding to a vertex, and for each $i\in A\cup B$, draw a directed edge to $i+a$ if it is in $A$ and an edge to $i-b$ if it is in $B$. We now delete edges as follows; if a vertex $i$ has both edges $i\to i-b$ and $i\to i+a$, delete the edge $i\to i-b$. Claim: Every element of $A\cup B$ is contained in a cycle. Solution: Consider a particular $i\in A\cup B$. Let $i_0=i$. Inductively construct a sequence of vertices starting with $i$ as follows; for each $i_k$, let $i_{k+1}$ be a vertex for which $i_k\to i_{k+1}$ is an edge. As $A\cup B$ is finite and the process cannot terminate, there must be some first vertex $j=i_n$ for which $j$ has occurred before. Suppose that $j\ne i$. If $j\in B$, then $j+b$ must have occurred immediately before each instance of $j$, contradiction. Similarly, if $j\in A$, then $j-a$ occurred twice. Hence, $j=i$ and $i$ is in a cycle. $\fbox{}$ Claim: Every element of $A\cup B$ is contained in exactly one cycle. Solution: By the previous claim, it suffices to suppose there is a vertex $i\in A\cup B$ such that $i$ is contained in two cycles, $\mathcal{A},\mathcal{B}$. As these cycles are distinct, there is some common vertex $v$ such that in $\mathcal{A}$ the vertex after $v$ is $w_1$ and in $\mathcal{B}$ the next vertex is $w_2$. Then, $v$ has outdegree $2$, which is a contradiction. $\fbox{}$ Now, note that in any cycle with $x$ elements of $A$ and $y$ elements of $B$, we must have $ax=by$ because for a vertex in the cycle $i$, we get $i-ax+by=i$ by definition. Now, sum this result over all cycles. By the previous claim, this sum must count every element of $A\cup B$ exactly once, hence we are done.

For every $i\in A\cup B,$ define \[f(i)= \begin{cases} i+a & i+a\in A\\ i-b & i-b\in B \end{cases}. \]$\textbf{Claim: }$ $f$ is bijective $\emph{Proof: }$ Since $f$ is a function from $A\cup B$ to itself, it suffices to show that $f$ is injective. Suppose $f(x)=f(y)$ for some $x,y.$ If $f(x),f(y)\in A,$ then we have $x+a=f(x)$ and $y+a=f(y),$ so $x=y.$ Similarly, we can show that $f(x),f(y)\in B$ implies $x=y,$ so we are done. $\blacksquare$ Now consider the directed graph induced by $f$ on $A\cup B.$ Since $f$ is bijective and $A\cup B$ is finite, we can decompose the graph into disjoint cycles. Fix an element $e$ of a cycle containing $m$ vertices in $A$ and $n$ vertices in $B,$ and suppose we travel from $e$ to itself along the edges of the cycle. Notice that for any edge $ij$ along this path, $j-i=a$ if $j\in A$ and $j-i=-b$ if $j\in B.$ Therefore, we have $e+am-bn=e,$ so $am=bn.$ Since we can repeat this argument for any cycle, we have $a|A|=b|B|,$ as desired.

Put the elements of $A\cup B$ on a graph, and colour the elements of $A$ red and the elements of $B$ blue. For each red element $x$, if $x+a$ is also red, then draw a red edge between $x$ and $x+a$, otherwise it implies $x-b$ is blue, so draw a blue edge between $x$ and $x-b$. Similarly, for each blue element $x$, if $x-b$ also blue, draw a blue edge between $x$ and $x-b$, otherwise it implies $x+a$ is red, so draw a red edge between $x$ and $x+a$. Now, this implies that the red elements form a graph of chains, and so do the blue elements. Furthermore, when we follow the arrow of a blue element, it subtracts $b$, and following the arrow of a red element adds $a$. Since the two sets are disjoint, the number of red arrows going into a red element is at most $1$, same thing for the blues. Now, consider the starting position of a red chain. We can keep following the arrows until we get to the head of the chain, then follow the blue arrow to get to the starting position of a blue chain (it can't be in the middle of the blue chain because that violates disjoint sets). Then, keep following the blue chain until we get a red chain again, and so on until we're back at our starting position. We have to end up at our starting position, because the path can not end somewhere (there's always another arrow to follow), and if it ends up in the middle of path on a different chain, that would imply two arrows of the same colour are going into that vertex, a contradiction. Then, if $x, y$ were the number of red and blue vertices on this path, $x$ and $y$ would also be the number of red and blue edges. For each red edge, we add $a$, and for each blue edge, we subtract $b$, and since our net change is $0$ (we end up back where we were), we have $xa = yb$. Doing this over all starting positions gives \[\sum_{\text{path p}} p_{x}a = \sum_{\text{path p}} p_{y}b \Rightarrow |A|a = |B|b\]

amuthup wrote: For every $i\in A\cup B,$ define \[f(i)= \begin{cases} i+a & i+a\in A\\ i-b & i-b\in B \end{cases}. \]$\textbf{Claim: }$ $f$ is bijective $\emph{Proof: }$ Since $f$ is a function from $A\cup B$ to itself, it suffices to show that $f$ is injective. Suppose $f(x)=f(y)$ for some $x,y.$ If $f(x),f(y)\in A,$ then we have $x+a=f(x)$ and $y+a=f(y),$ so $x=y.$ Similarly, we can show that $f(x),f(y)\in B$ implies $x=y,$ so we are done. $\blacksquare$ Now consider the directed graph induced by $f$ on $A\cup B.$ Since $f$ is bijective and $A\cup B$ is finite, we can decompose the graph into disjoint cycles. Fix an element $e$ of a cycle containing $m$ vertices in $A$ and $n$ vertices in $B,$ and suppose we travel from $e$ to itself along the edges of the cycle. Notice that for any edge $ij$ along this path, $j-i=a$ if $j\in A$ and $j-i=-b$ if $j\in B.$ Therefore, we have $e+am-bn=e,$ so $am=bn.$ Since we can repeat this argument for any cycle, we have $a|A|=b|B|,$ as desired. But I think, that $f$ is not actually a function, where did you prove that it can't hold both $i+a \in A$ and $i-b \in B$?

@above, I don't think it really matters-- just arbitrarily assign $f(i)$ if both $i+a\in A$ and $i-b\in B,$ the same proof should hold.

Consider the directed graph $G$ with vertices in $\{A \cup B\}$, where we connect $i \in \{A \cup B\}$ with $i+a$ iff $(i+a) \in A$, and/or $i-b$ iff $(i-b) \in B$. By construction, since we are considering $i \mapsto i+a$ or $i \mapsto i-b$, the graph is a disjoint union of cycles (it has cycles because $G$ is finite and we can "query" $i \mapsto i+a$ or $i \mapsto i-b$ infinitely). $\implies$ let $C_1,C_2,...,C_N$ all the cycles contained in $G$. Now, observe that for each $1 \leq i \leq N$, there exist $x_i,y_i$ such that $i=i+ax_i-by_i$, due to the $G$'s construction. $\implies ax_i=by_i$, and $x_i$ represents the number of elements in the cycle which belong to $A$, and $y_i$ represents the number of elements in the cycle which belong to $B$. $\implies a (\sum_{i=1}^N x_i)= b (\sum_{i=1}^N y_i) \implies$ since the cycles are disjoint, $\sum_{i=1}^N x_i=|A|$ and $\sum_{i=1}^N y_i= |B|$, and hence $a|A|=b|B|$, as desired. $\blacksquare$

A fabulous instructive arrow problem. WLOG $\gcd(a,b) = 1$, and let $i$ be a really large positive integer. Furthermore denote $(x,y)$ as $i + xa + yb$. Here, we assume that $(m,n) \equiv (m + b, n - a) \equiv (m - b, n + a)$. Now, let $G$ be the directed graph interpretation of the problem, where every vertices is given the weight $(x,y)$, and draw $(x,y) \to (z,w)$ with a red arrow if $(z,w) = (x + 1, y)$ and $(x,y) \to (z,w)$ with a yellow arrow if $(z,w) = (x, y - 1)$. Now, we notice that this graph is finite by our assumption. Therefore, this graph has $v$ vertices and at least $v$ edges (each vertices has at least one outer edges), and therefore this graph must have a cycle. Claim 01. For any such cycle, the length of the cycle must be divisible by $a + b$. Proof. Take any vertices $v$ which has weight $(x,y)$. Now, we consider the function $\sigma(v) \equiv y - x \ (\text{mod} \ a + b)$. Notice that this preserves the condition where $(m,n) \equiv (m + b, n - a) \equiv (m - b, n + a)$. Furthermore, every arrow changes $\sigma(v)$ by exactly $-1$. Therefore if there exists a cycle, the length of the cycle must be divisible by $a + b$. Claim 02. There couldn't be two inner edge for every vertices $v$. Proof. Suppose otherwise, that there exists a vertex $v$ such that it has inner edge coming from $w$ and $x$. Obviously, since $w \not= x$, then both of these edges must be different in color, but this means $v \in A \cap B$, which is a contradiction as $A$ and $B$ are disjoint. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.8] \draw[fill=green] (-2,-2) circle (3 pt); \draw[fill=green] (-2,2) circle (3 pt); \draw[fill=green] (0,0) circle (3 pt); \draw[very thick, yellow, ->] (-2,2) -- (0,0); \draw[very thick, red, ->] (-2,-2) -- (0,0); \node[black, font = \small] at (0.4,0) {$v$}; \node[black, font = \small] at (-1.6,2) {$w$}; \node[black, font = \small] at (-1.6,-2) {$x$}; \end{tikzpicture}");[/asy][/asy] Now, to finish this problem. Divide $G$ into $k$ connected components: $C_1, C_2, \dots, C_k$. First of all, each of these connected component must contain a cycle, as we have $\text{outdegree} \ge \text{vertices}$ in each of these $C_i$. Now, Suppose there exists a vertex not in part of the cycle. We know that \[ |\text{vertices}| \le | \text{outdegree} | = | \text{indegree} | \le |\text{vertices}|\]from our previous lemma. This forces that each vertex has indegree exactly $1$, and outdegree exactly $1$, forcing all of them to be part of a cycle. Furthermore, it is easy to see that no two cycle can intersect (by the indegree argument). Therefore, it suffices to prove that $a|A| = b|B|$ for every such cycle. Suppose that in such cycle, we use $k$ application of red arrows and $\ell$ application of yellow arrows, we then have $(m + k, n - \ell) \equiv (m,n)$. However, this means that \[ a(m + k) + b(n - \ell) = am + bn \Rightarrow ak = b \ell \]which is a horray for us, since for every connected component of $G$, we have $a |A| = b|B|$. Sum it through all connected component, we get \[ a |A| = b|B| \]on the original graph, done. Remark. Here's a really helpful diagram that helps me figure out the cycle argument, and what happened if two cycle coincides. (I got the fact that the cycle must be divisible by $a + b$ first, and then drew the graph first, and then try to see whether it is possible to insert numbers which in the following diagram $(a,b) = (1,3)$), which fails because of the indegree argument. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.8] \draw[fill=black] (0,0) circle (3 pt); \draw[very thick, color=red, ->] (0,0) -- (2,0); \draw[fill = black] (2,0) circle (3 pt); \node[black, font = \small] at (0,-0.5) {$i$}; \node[black, font = \small] at (2,-0.5) {$i +1$}; \draw[fill=black] (3,1) circle (3 pt); \draw[very thick, color=red,->] (2,0) -- (3,1); \node[black, font = \small] at (3.8,0.7) {$i + 2$}; \draw[fill=black] (2,2) circle (3 pt); \draw[very thick, color = red, ->] (3,1) -- (2,2); \draw[very thick, color= yellow, ->] (2,2) -- (0,0); \node[black, font = \small] at (2.5,2.3) {$i + 3$}; \draw[fill=black] (3,-2) circle (3 pt); \draw[very thick, color= yellow, ->] (2,0) -- (3,-2); \node[black, font = \small] at (3.7,-2) {$i - 2$}; \draw[fill=black] (1,-3) circle (3 pt); \draw[very thick, color= red, ->] (3,-2) -- (1,-3); \draw[very thick, color=red, ->] (1,-3) -- (0,0); \node[black, font = \small] at (1,-3.2) {$i - 1$}; \end{tikzpicture}");[/asy][/asy]

Here this is done by applying the Fourier transform. More details, as well as some other applications of Fourier on Olympiad problems, you could see in my blog. The given condition just means that $$ \displaystyle A\cup B\subset \left(A-a\right)\cup \left( B+b\right)$$where, as usual, $ A-a=\{x-a : x\in A\}.$ We have $ |A\cup B|=|A|+|B|,$ because $ A$ and $ B$ are disjoint. Therefore, $\left|\left(A-a\right)\cup \left( B+b\right)\right|\ge |A|+|B|.$ Since $ |A-a|=|A|, |B+b|=|B|,$ it follows $ A-a$ and $ B+b$ are disjoint and $$ \displaystyle A\sqcup B= \left(A-a\right)\sqcup \left( B+b\right)\qquad (1)$$Let us denote $$ \displaystyle A_1:=\bigcup_{x\in A} \left[x,x+1\right)\,;\, B_1:=\bigcup_{x\in B}\left[x,x+1\right).$$Clearly, a similar condition as $ (1)$ holds for $ A_1,B_1$ $$ \displaystyle A_1\sqcup B_1= \left(A_1-a\right)\sqcup \left( B_1+b\right)\qquad (2)$$Let $ f(x)$ and $ g(x)$ be the indicator functions of the sets $ A_1,$ correspondingly $ B_1.$ By $ (2)$ we get $$ \displaystyle f(x)+g(x)=f(x+a)+g(x-b)$$Taking the Fourier transforms of the left and right sides,it yields $$\hat{f}(\xi)+\hat{g}(\xi)=\hat{f}(\xi)e^{2\pi i a\xi} + \hat{g}(\xi) e^{-2\pi i b\xi}.$$Further, we differentiate with respect to $ \xi$ the both sides of the above equality. $$\displaystyle \hat{f}'(\xi)+\hat{g}'(\xi)=\hat{f}'(\xi)e^{2\pi i a\xi}+2\pi i a\hat{f}(\xi)e^{2\pi i a\xi} + \hat{g}'(\xi) e^{-2\pi i b\xi}-2\pi i b \hat{g}(\xi) e^{-2\pi b \xi}$$Putting $ \xi=0$ it yields $$\displaystyle a\hat{f}(0)=b\hat{g}(0)$$By the mere definition of $ \hat{f}, \hat{g}$ it follows $ \displaystyle \hat{f}(0)=\int_{-\infty}^{\infty} f(x)\, dx=m(A_1)=|A|,$ where $ m(A_1)$ denotes the measure (total length) of $ A_1.$ In the same way, $ \hat{g}(0)=|B|.$ Finally, $ a|A|=b|B|.$

Consider a graph $G$ with elements of $A \cup B$ as vertices. Then, the problem can be rephrased as drawing arrows $i \to i + a$ or $i \to i-b.$ Hence, the graph consists of many disjoint cycles of edges (since there must be a repeated vertex else there are an infinite number of elements in $A$). Suppose the cycle is completed once we reach vertex $i + xa - yb.$ This means that it has already been seen before, say at another $i + x'a - y'b$ where $x' \le x$ and $y' \le y.$ This gives $a(x-x') = b(y-y').$ However, this means that $i + a(x-x') +b(y-y') = 0$ as well, and since $x - x'$ and $y-y'$ are strictly less than $x$ and $x'$ respectively, it follows that the process terminates when $i + ma - nb = i$ for some $(m,n).$ This adds $m$ elements to $A$ and $n$ elements to $B.$ For each cycle $C_k$ in $G,$ suppose that we add $m_k$ elements to $A$ and $n_k$ to $B.$ These must be distinct, since the cycles are disjoint. We can count the number of elements in $A$ as \[ |A| = \sum_{k} m_k = \sum_{k} \frac{b}{a} n_k = \frac{b}{a} \sum_{k} m_k = \frac{b}{a} |B| \iff a |A| = b|B| \]as desired.

Construct a directed weighted graph with one node per element o $A \cup B$ and drawing a directed edge from $i \to j$ with weight $+a$ if $j = i+a \in A$ and with weight $-b$ if $j = i-b \in B$. Note that if none of $j = i+a$ or $j = i-b$ holds, then we don't draw any edge. Now the crucial observation is that any node of this graph has each outdegree at least $1$ and indegree at most $1$. This will result in all nodes having degree exactly $1$ and so this graph is the union of disjoint cycles. Next, each cycle has weight zero by our tricky weight assignment. This yields that if in some cycle $C$ there are $x$ nodes in $A$ and $y$ in $B$ (so the cycle has size $x+y$) we have $xa-yb = 0$. Summing over all cycles yields the desired result.

Represent all elements of $A \cup B$ as vertices in a directed graph, in which we connect $i$ to $i+a$ if it is in $A$ and connect $i$ to $i-b$ if it is in $B$. Note that the indegree for any vertex is at most $1$ and the outdegree at least $1$. But the sum of the outdegrees and Indegrees must be equal, and therefore, the total degree of any vertex is exactly $2$ which implies that the finite graph is a union of cycles. Consider any cycle, and assign edges $+a$ if $i$ is connected to $i+a$ and assign them $-b$ if it is connected to $i-b$. Let their be $x$ elements of $A$ here and $y$ elements of $B$. Note that $ax=by$ because every element of $A$ Has it’s “in”-edge assigned $+a$ and vice versa. Summing this over all cycles, we are done.

Let $S=A \cup B$ and consider a function $f : S \to S$ where $f(i)$ either equals $i+a$ or $i-b$. Clearly $f$ is injective, thus bijective as $|S|=|S|$, so it can be decomposed into a number of cycles when considering a graph. Each directed edge on a cycle either goes $+a$ or $-b$; letting $x$ denote the number of $+a$ edges and $y$ the number of $-b$ edges, we must have $ax=by$, as the cycle ends where it starts. But counting by the "destinations" of each directed edge, there are actually $x$ elements of the cycle in $A$ and $y$ elements of the cycle in $B$. Then summing over every cycle we have $a|A|=b|B|$ as desired. $\blacksquare$

\[\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\] Let $f\colon A\cup B \to A \cup B$ satisfy \[ \begin{cases} f(i) = i + a & \text{if } i+a \in A \\ f(i) = i - b & \text{if } i + a \in B \text{ and } i + a\not\in A \\ \end{cases} \] Claim: $f$ is bijective. Proof: Since $f$ is from a finite set to itself, it suffices to show $f$ is injective. Suppose $f(x) = f(y)$, where $x\ne y\in A\cup B$. If $x+a$ and $y+a$ were both in $A$, then we have $x+a = y+a$, contradiction. Thus we may WLOG $y+a \not\in A$, so $f(y) = y-b$. If $f(x) = x - b$, then $x-b = y-b$, contradiction, so $f(x) = x + a$. However, then $f(x)\in A$, $f(y)\in B$, contradiction since $f(x) = f(y)$ and $A$ and $B$ are disjoint. Thus, $f$ is injective, so bijective. $\square$ Since $f$ is bijective and from a set to itself, it consists of a bunch of cycles. Fix a certain cycle with $k$ elements in $A$ and $l$ elements in $B$. Notice how when we cycle from a fixed element $t$ to itself, we add by $a$ $k$ times and subtract by $b$ $l$ times. Since we go back to $t$ itself, we have $ak = bl$. Summing over all such cycles gives the desired result.

Consider a graph $G$ with vertices on the elements of $A \sqcup B$, and color each vertex red if it is in $A$ and blue otherwise. Furthermore, draw a red directed arrow $x \to y$ if $y=x+a$ and $y$ is red, and a blue directed arrow $x \to y$ if $y = x-b$ and $y$ is blue. Observe that every vertex has outdegree at least one. Claim. [Key Claim] There exists a subgraph $G'$ on $G$ with the same set of vertices composed of vertex-disjoint cycles. Proof. Starting from any vertex in $G$, move along the arrows until we return to a previous vertex. Then delete the vertices in the cycle and repeat. $\blacksquare$ It suffices to show that for any cycle $C$ with $r$ red vertices and $k$ blue vertices we have $ar = bk$. Notice that among the cycle, every blue arrow points to a blue vertex, and vice versa. On the other hand, as every blue arrow has length $b$ and every red arrow has length $a$, the number of blue and red arrows are in the desired proportion, thus the number of vertices are too.

For an integer $i$ that is part of $A$ or $B$, define a parent of $i$ as either $i+a$ in $A$ or $i-b$ in $B$. The problem asserts that each number in either $A$ or $B$ has a parent. However, note that each number can be the parent of at most one other number (if $p$ is in $A$, it can only be a parent of $p-a$, and if it is in $B$ it can only be a parent of $p+b$). Thus, by global argument, this means that each number has only one parent (since each number has one parent on average and all numbers have at least one parent). Thus, consider the directed graph where we draw an edge between a number and its parent. It consists of a union of cycles, since it is injective and therefore bijective since the domain and codomain are equivalent. However, in each cycle, the number of times we add $a$ is $\frac{b}{a}$ the number of times we subtract $b$, since we return to the same number. Whenever we add $a$, we get a number in $A$, and when we subtract $b$, we get a number in $B$. Thus, there are $\frac{b}{a}$ times as many elements of $A$ as there are elements of $B$, since this applies to all cycles, hence done.

Define sets $X,Y$ as follows \[X=\{i:i\in A\cup B,i+a\in A\}\]\[Y=\{i:i\in A\cup B,i-b\in B\}\]Note that $X\cup Y=A\cup B$. Also, the set $X+a=\{i:i=x+a,x\in X\}$ is a subset of $A$. Similarly the set $Y-b$ is a subset of $B$. Hence, $|X|\leq|A|$ and $|Y|\leq|B|$, so $|X|+|Y|\leq|A|+|B|$. \[|A|+|B|\geq|X|+|Y|=|X\cup Y|+|X\cap Y|=|A\cup B|+|X\cap Y|\]\[=|A|+|B|-|A\cap B|+|X\cap Y|=|A|+|B|+|X\cap Y|\geq |A|+|B|,\]so equality must hold. Hence, $|X|=|A|,|Y|=|B|$ and $X\cap Y=\phi$. It follows that for each $i$, either $i+a\in A$, or $i-b\in B$, both cannot hold simultaneously. Consider the function $f:A\cup B\rightarrow A\cup B$ such that if $x+a\in A$ then $f(x)=x+a$ and if $x-b\in B$ then $f(x)=x-b$. Claim: This function is injective. Proof. Note that if $f(x_1)=f(x_2)$ and $x_1,x_2\in A$ then $x_1=x_2$ is forced. Similarly, if $x_1,x_2,\in B$ then $x_1=x_2$ is forced as well. However, if $x_1\in A$ and $x_2\in B$, then $x_1+a\in A$ and $x_2-b\in B$, but since $x_1+a=x_2-b$, this element lies in both $A$ and $B$, which contradicts the fact that $A\cap B=\phi$. So, the function is injective. Since there are exactly $|A|+|B|$ inputs and at most $|A|+|B|$ outputs with each input corresponding to a unique output, it follows that the function is surjective. It is hence bijective. Consider a directed graph $G$ on $|A|+|B|$ vertices where each vertex represents an element of set $A$ or set $B$. A directed edge $x\rightarrow y$ exists if and only if $y=f(x)$. Since $a\ne0$ and $b\ne0$, there are no loops, and the function is bijective, the graph is composed entirely of pairwise disjoint directed cycles, with each vertex being a part of a cycle. Consider a cycle $\mathcal{C}$ of length $l$ consisting of $x_1$ elements from set $X$ and $y_1$ elements from set $Y$. Then, there are exactly $x_1$ elements from set $A$ and $y_1$ elements from set $B$ in this cycle. Moreover, we return to the original element after $x_1+y_1$ length walk around the cycle. So, if $e$ is our original element, then $e+x_1a-y_1b=e$. So, $x_1a=y_1b$. Summing up this equation over all the cycles in graph $G$, we get $a|A|=b|B|$, as required. $\blacksquare$

Consider the following function $f$ from $A \cup B$ to $A \cup B$: Given any $x \in A \cup B$, pick either $i+a$ or $i - b$, whichever one is in $A \cup B$, if both then select freely. I claim this function is well-defined. This is clear. I claim this function is injective. If $f(x) = f(y)$ and $x, y \in A$ or $x, y \in B$ clearly $x = y$. If $x \in A, y \in B$ then if $f(x) = f(y)$ is in $A, B$ then either both $x, y = f(x) - a$ or both $x, y = f(x) + b$ respectively, giving contradiction by disjointness. Thus together this function is bijective. Hence it must consist of cycles. In each cycle, denote the cyclic sequence of $A, B$ that successive elements belong to (e.g. $AAAABABBAABA$). Since the overall action of the cycle is mapping $x \to x + a (\textrm{\# of As}) - b (\textrm{\# of Bs})$, it follows that in each cycle we have $a (\textrm{\# of As}) = b (\textrm{\# of Bs})$, so summing all cycles we have $a |A| = b |B|$ as desired.

Note that for the sets to be finite every value must be in a cycle, now suppose a value $k$ is in two cycles, if $k$ is in onlky one set that implies the value before it in the cycle is also in the second cycle, repeating this gives that it must be the same cycle, thus all cycles are disjoint. Thus as each cycle has $kb$ elements in $A$ and $ka$ elements in $B$ this proves the result.

I love archery

Note that each number in $A\cup B$ can ``support'' at most one other number; thus each supports exactly one. Thus consider the cycles, each one can only go one direction by $b$ or the other direction by $a$ and the result is clear.

Cool arrows application! We draw an arrow $x \to x+a, x-b$ (respectively called $+$arrows and $-$ arrows), for all $x$. Claim: no vertex has indegree 2. Proof: Assume otherwise, then one arrow into a vertex $v$ is a $+$arrow and the other a $-$arrow, meaning $v \in A \cap B$, contradiction. $\square$. Now because of this claim, the resulting graph on $A \cup B$ must in fact consist of disjoint cycles. In each cycle, $a \times \#\{v \in A\} = b \times \#\{v \in B\}$ by the sum condition, and summing over all the cycles finishes. $\blacksquare$

Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025. Far easier than problem 1 (19ESLA2)

storage