Note_to_self_for_bugfix: it should be pairs of different integers.

it's a very nice problem have you a solution for it ?

I agree that it is a beautiful problem, but I have no solution myself. I also think it is more combinatorics than number theory.

i'll try to find a solution. my first idea is to use induction in $ k=MaxA\cup B$any way it was just a first idea,

Either collection means multiset, or the problem is incorrectly stated as for $ A = \{3,6,7,8,9\}$ and $ B = \{4,5,6,7,8,9\}$ we have as sets $ A^* = B^* = \{9,10,11,12,13,14,15,16,17\}$. Assuming collection means multiset, the problem is true. $ A^*$ and $ B^*$ clearly have $ \binom n2$ and $ \binom m2$, respectively, elements, from where $ m = n$ follows immediately. I've been trying to recall the solution for this restated problem for a while and here it is: Let $ A = \{a_1,\ldots,a_n\}$, $ B = \{b_1,\ldots,b_n\}$. Let $ f(x) = x^{a_1} + x^{a_2} + \ldots + x^{a_n}$ and $ g(x) = x^{b_1} + x^{b_2} + \ldots + x^{b_n}$. Then $ A^* = B^*$ means $ f(x)^2 - f(x^2) = g(x)^2 - g(x^2)$. Note that $ f(1) = g(1) = n$. Denote $ h(x) = f(x) - g(x)$ and $ q(x) = f(x) + g(x)$. Then $ h(1) = 0$ and $ q(1) = 2n$. Then we have $ \boxed{h(x)q(x) = h(x^2)}$. We have $ h(1) = 0$. Let $ h^{(l)}(x)$ the $ l$th derivative of $ h$. Since $ h\neq0$, there exists a $ k$ such that $ h^{(k)}(1)\neq0$. Take the smallest such $ k$. Differentiate the 'boxed' relation $ k$ times and take $ x = 1$. Because $ h^{(i)}(1) = 0$ for $ 0\le i\le k - 1$, ignoring the terms involving these derivatives (see the note below) we get $ h^{(k)}(1)q(1) = 2^kh^{(k)}(1)$. Because $ h^{(k)}(1)\neq0$, we have $ f(1) + g(1) = 2n = 2^k$, from where $ n$ is a power of $ 2$. Note: By an easy induction we have $ (hq)^{(k)} = \displaystyle\sum_{i = 0}^k\binom{k}{i}h^{(i)}q^{(k - i)}$, where $ h,q$ are $ k$ times differentiable functions (in our case, polynomials). The above solution 'hides' the following idea: $ n = 2^r$, where $ r$ is the greatest positive integer such that for any $ 0\le i\le r$ holds: $ \displaystyle\sum_{j = 1}^na_j^i = \sum_{j = 1}^nb_j^i$. I'm thinking about this approach. Edit: Under these sad circumstances, I dedicate this solution to Mr. Vornicu's Mother, my Mother and all the Mothers in the world. Edit 2: Edited thanks to othman's observation below.

Brilliant solution!

this is a very good solution thanks but $ q(x)=f(x)+g(x)$

this is a slightly different version of freemind's solution: after it has been established that $ f(x)^2 - f(x^2) = g(x)^2 - g(x^2)$ and $ f(1) - g(1) = n - n = 0$ we could have concluded that: \[ f(x) - g(x) = (x - 1)^{k}h(x) \] for some $ k\geq 1$ and $ h(x)$, so that $ h(1)\neq 0$. So $ f(x) + g(x) = \frac {f(x)^2 - g(x)^2}{f(x) - g(x)} = \frac {f(x^2) - g(x^2)}{f(x) - g(x)} = \frac {(x^2 - 1)^kh(x^2)}{(x - 1)^kh(x)}$,or \[ \boxed{f(x) + g(x) = (x + 1)^k\frac {h(x^2)}{h(x)}} \] Setting $ n = 1$ into the boxed equation, we get $ n = 2^{k - 1}$ P.S: To Peter: I am more inclined to think that this one belongs to algebra.

Can't there be multiplicity such that $a_j+a_k=a_i+a_l$ for some numbers??