3
$\begingroup$

A special case says it all ... Let $ w_1 < w_2 < \ldots < w_{12} $ be an increasing sequence of $12$ integers ("weights") such that the total weight $W=\sum_{k=1}^{12}w_k$ is even.

Say that $I \subseteq \lbrace 1,2, \ldots ,12 \rbrace$ is an exact subset iff the sum $\sum_{k \in I}w_k$ equals $\frac{W}{2}$. My question is : is there a sequence for which $ \lbrace 1,2,5,7,10,12 \rbrace $ is exact and is the only exact subset (up to complementation) ?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ A motivation would be welcome. $\endgroup$
    – Benoît Kloeckner
    Commented Apr 27, 2010 at 17:27
  • 3
    $\begingroup$ Maybe I am missing something, but isn't the complement of an exact subset also an exact subset? $\endgroup$
    – damiano
    Commented Apr 27, 2010 at 18:09
  • 1
    $\begingroup$ Having said this, it seems that you have a linear function on $R^{12}$ with integer coefficients and you are trying to find its zeros on the set of vertices of a cube and you would like the set of zeros to consist exactly of a pair of opposite vertices. This does not seem hard to achieve. $\endgroup$
    – damiano
    Commented Apr 27, 2010 at 18:23
  • $\begingroup$ @ Benoît : I encountered this problem trying to construct nontrivial examples in the context of partitions-with-weights problems that appear in recreational mathematics. The subset $\lbrace 1,2,5,7,10,12 \rbrace$ was chosen ``as random as possible". $\endgroup$
    – Ewan Delanoy
    Commented Apr 28, 2010 at 3:18
  • $\begingroup$ @ damiano : I believe your linear-function-on-$ {\mathbb R}^{12} $ analogy only provides nondecreasing sequences instead of increasing sequences. If you insist that the sequence be increasing, you get an affine function instead of a linear function. Also, note that $ \lbrace 1,2,3,4,5,6 \rbrace $ can never be an exact subset. $\endgroup$
    – Ewan Delanoy
    Commented Apr 28, 2010 at 3:20

2 Answers 2

Reset to default
10
$\begingroup$

The answer is yes. Consider the sequence

$100, 200, 201, 202, 500, 601, 700, 701, 801, 1000, 1194, 1200.$

It is easy to see that $X=\{1,2,5,7,10,12\}$ and $Y=\{3,4,6,8,9,11\}$ are exact. Moreover, we claim that they are the only exact subsets. To see this, note that for every subset $X'$ of $X$, the sum of the corresponding sequence values is divisible by $100$. However, for every proper subset $Y'$ of $Y$, the sum of the corresponding sequence values is not divisible by $100$. Thus, $X$ and $Y$ are the only exact subsets.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It's not quite clear to me that {1,2,5,7,10,12} is the only exact subset up to complementation. How did you construct your sequence ? $\endgroup$
    – Ewan Delanoy
    Commented Apr 27, 2010 at 19:47
  • $\begingroup$ Let X={1,2,5,7,10,12} and Y={3,4,6,8,9,11}. Then for any subset of $X$ we have that the sum of the corresponding sequence values are 0 (mod 100). However, for any proper subset of Y, the sum of the corresponding sequence values are non-zero (mod 100). Thus, X and Y are the only exact subsets. $\endgroup$
    – Tony Huynh
    Commented Apr 27, 2010 at 20:21
  • $\begingroup$ Thanks Ewan. Using the same technique it is easy to prove that if X is an exact subset of some sequence S, then there is another sequence S' such that X is the unique exact subset of S'. For example, for sequences S of length 12, we can first multiply S by 10. Then we can arbitrarily choose an index x in X and subtract 5 from the corresponding member of 10S. We then can add 1 to the members of 10S corresponding to X -x to obtain S'. $\endgroup$
    – Tony Huynh
    Commented Apr 28, 2010 at 4:20
1
$\begingroup$

Just an expansion on my comment. I will assume that exact sequences need to have half the number of indices of the whole sequence. Then a sequence is exact for some choice of weights if and only if it is exact for one weight. (This is already argued, both in my comment and in Tony Huynh's.)

The final question to be answered is when is a subsequence exact for some choice of weights. This is again very easy. A subset I of {1,...,2n} of size n obviously determines an increasing bijection $j_I$ between I and its complement. The subset I is an exact subsequence for some choice of weights if and only if the function $i \mapsto j_I(i)-i$ for $i \in I$ does not have constant sign.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can't we handle the general case where exact sequences don't necessarily have half the indices? That is, for some subset X of [n], let (X) be the sequence of elements of X in increasing order. Letting Y by [n]-X, we have that X and Y are both exact for some sequence of length n if and only if (X) and (Y) are incomparable under the usual ordering of finite sequences (not necessarily of the same length) of integers. $\endgroup$
    – Tony Huynh
    Commented Apr 28, 2010 at 14:47
  • $\begingroup$ I am pretty sure that there is a way of handling the general case, but I just have not thought about it. I do not know what is the "usual ordering of finite sequences"... $\endgroup$
    – damiano
    Commented Apr 28, 2010 at 15:50
  • $\begingroup$ A sequence $(x_1, \dots, x_n)$ is less than or equal to another sequence $(y_1, \dots, y_m)$ if and only if there is an increasing map $f:[n] \to [m]$ such that $x_i \leq y_{f(i)}$ for all $i \in [n]$. So, it is clear that if $(X) \leq (Y)$, then neither $X$ nor $Y$ can be exact. I believe the converse is true as well. $\endgroup$
    – Tony Huynh
    Commented Apr 28, 2010 at 17:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .