0
$\begingroup$

$\DeclareMathOperator\setsum{setsum}$Let there be two sets of numbers of size $n$ each given by $S_1, S_2$.

Let there be a one-to-one onto mapping $f: S_1 \rightarrow S_2$.

Let us denote the sum of elements of set $S$ by $\setsum(S)$.

We say that a multiset $M$ is a derived multiset of a set $S$ if

  1. $|M| = |S|$
  2. All elements of $M$ belong to $S$
  3. At least one element in $M$ is repeated.

Let $S_3$ be a derived multiset of $S_2$, then when we say $f^{-1}(S_3)$, we mean the set obtained by replacing elements of $S_3$ by their mapped elements in $S_1$.

For example, $S_1 = \{1, 2, 3\}$, $S_2=\{5, 7, 9\}$, $f=\{1\rightarrow5, 2\rightarrow7,3\rightarrow9\}$, $S_3=\{5, 5, 9\}$ then, $f^{-1}(S_3)=\{1, 1, 3\}$.

Let $D(S)$ denote the set of all derived multisets of a set $S$.

For example, $D(S_1) = \{\{1, 1, 1\}, \{2, 2, 2\}, \{3, 3, 3\}, \{1, 1, 2\}, \{1, 1, 3\}, \{1, 2, 2\}, \{2, 2, 3\}, \{1, 3, 3\}, \{2, 3, 3\}\}$.

For any given $n$, we want to find two sets $S_1$ & $S_2$ & $f$ such that $\{s\ |\ s \in D(S_1)\ \&\ \setsum(s) = \setsum(S_1)\}\ \cap\ \{f^{-1}(t) \mid t \in D(S_2)\ \&\ \setsum(t) = \setsum(S_2)\} = \emptyset.$

For example, given $n=4$, $S_1=\{1, 2, 3, 4\}$, $S_2=\{1, 2, 4, 7\}$, $f=\{1\rightarrow1, 2\rightarrow2, 3\rightarrow4, 4\rightarrow7\}$ satisfies the above condition because

$$X = \{s \in D(S_1) \mid \setsum(s) = \setsum(S_1) = 10\} = \{\{1, 1, 4, 4\}, \{1, 3, 3, 3\}, \{2, 2, 2, 4\}, \{2, 2, 3, 3\}\}$$ $$Y = \{t \in D(S_2) \mid \setsum(t) = \setsum(S_2) = 14\} = \{\{2, 4, 4, 4\}\}$$

i.e. $Y' = \{f^{-1}(t) \mid t \in D(S_2)\ \&\ \setsum(t) = \setsum(S_2) = 14\} = \{\{2, 3, 3, 3\}\}$

$$\&\ X \cap Y' = \emptyset.$$

Some other sets & mappings which satisfy the above condition for different $n$ are,

$n = 6$: $S_1=\{1, 2, 3, 4, 5, 6\}$, $S_2=\{1, 2, 4, 7, 3, 8\}$, $f:\{1\rightarrow1, 2\rightarrow2, 3\rightarrow4, 4\rightarrow7, 5\rightarrow3, 6\rightarrow8\}$

$n = 10$: $S_1 = \{1, 5, 7, 13, 16, 19, 20, 23, 24, 26\}$, $S_2 = \{2, 4, 8, 11, 17, 18, 21, 30, 43, 81\}$, $f:\{1\rightarrow2, 5\rightarrow4, 7\rightarrow8, 13\rightarrow11, 16\rightarrow17, 19\rightarrow18, 20\rightarrow21, 23\rightarrow30, 24\rightarrow43, 26\rightarrow81\}$.

Some sets & mappings which do not satisfy the above condition for different $n$ are,

$n=10$: $S_1 = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ (arithmetic), $S_2 = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}$ (primes), $f:\{1\rightarrow2, 2\rightarrow3, 3\rightarrow5, 4\rightarrow7, 5\rightarrow11, 6\rightarrow13, 7\rightarrow17, 8\rightarrow19, 9\rightarrow23, 10\rightarrow29\}$

because one of many cases which contradicts the above condition is $f^{-1}(\{2, 2, 2, 5, 19, 19, 19, 19, 19, 23\}) = \{1, 1, 1, 3, 8, 8, 8, 8, 8, 9\}$.

Question: Give a method to generate $S_1$, $S_2$ & $f$ for a given $n$ such that they satisfy the above condition and $\setsum(S_1) + \setsum(S_2)$ is minimum among all possible choices of $S_1$ and $S_2$ given that the element space for choosing elements of $S_1$ and $S_2$ is $\mathbb{Z}$.

$\endgroup$
6
  • $\begingroup$ You referred twice to an intersection equalling $\phi$ (the Greek letter phi), which I think was supposed to be $\emptyset$ (the empty set). I edited accordingly. You also switched from $\operatorname{setsum}$ to $\operatorname{sumset}$, and I edited for consistency. (Also, MathJax note: please use stars *stars* for italics, and double stars **double stars** for bold, rather than faking it in TeX.) $\endgroup$
    – LSpice
    Commented Oct 8 at 23:35
  • 1
    $\begingroup$ All your examples use positive integers, but at the end you mention $\mathbb{Z}$. Must the elements be positive? $\endgroup$
    – RobPratt
    Commented Oct 8 at 23:37
  • $\begingroup$ Please use a more descriptive title. $\endgroup$ Commented Oct 9 at 0:50
  • $\begingroup$ Thankyou @LSpice $\endgroup$ Commented Oct 9 at 4:02
  • $\begingroup$ They can be negative as well @RobPratt $\endgroup$ Commented Oct 9 at 4:02

0

You must log in to answer this question.

Browse other questions tagged .