2
$\begingroup$

Let $X$ be a finite set of positive integers. Define $X$ mod $k$ as multiset of positive integers obtained by mod operation on every element of $X$. For example, $\{3, 5, 8\} \bmod 3 = \{0, 2, 2\}$. Two multisets are equal iff they have the same elements with identical frequency.

Let $A$ and B be two subsets of $\{1, 2, 3, ..., n - 1, n\}$ such that $|A| = |B| = m$, $A \cap B = \emptyset$. What is the minimum $k$ (as a function of $n$ and $m$) such that the multisets $A \bmod k \neq B \bmod k$. Consider for example $A = \{2, 4, 11, 15\}$ and $B = \{6, 8, 13, 17\}$ for which $A \bmod i = B \bmod i$, for $i = 2, 3$ but $A \bmod 4 \neq B \bmod 4$.

  • 2
    I think $k$ is a function of $A$ $B$, but does not only depend on $m$ and $n$. For example (with $n = 4$ and $m = 2$) if $A = \{1,3\}$ and $B = \{2,4\}$ then $k = 2$. But if $A = \{1,2\}$ and $B = \{3,4\}$, then $k = 3$.2012-05-27
  • 0
    @JoelCohen: I guess that just proves that $k \geq 3$; I believe what the OP wants is a bound that would work for *every* pair of sets. OP, could you confirm that?2012-05-27
  • 0
    @N.I For $n\gt m=2$, the value then is $k=n$: if $1\lt k\lt n-1$, then $A=\{1,2\}$, $B=\{1,k+2\}$ are equal modulo $k$. And $A=\{1,2\}$ $B=\{2,n\}$ have $A\bmod n-1 = B\bmod n-1$.2012-05-27
  • 0
    @N.I.: Yes, I am looking for a bound that works for every disjoint pair with the same number of elements.2012-05-28
  • 0
    @ArturoMagidin: Please note that the sets should be disjoint. Your examples do not satisfy the criterion.2012-05-28
  • 0
    @KMathCS: Sorry about that.2012-05-28
  • 0
    A specific case could be to consider to find $k$ for $p$, $q$ where $1 \leq p < q \leq n$ such that $p \not\equiv q ~mod~ k$. In other words, the size of sets $A$ and $B$ with just one element.2012-05-28

1 Answers 1