Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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) ?

share|improve this question
1  
A motivation would be welcome. –  Benoît Kloeckner Apr 27 '10 at 17:27
3  
Maybe I am missing something, but isn't the complement of an exact subset also an exact subset? –  damiano Apr 27 '10 at 18:09
1  
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. –  damiano Apr 27 '10 at 18:23
    
@ 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". –  Ewan Delanoy Apr 28 '10 at 3:18
    
@ 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. –  Ewan Delanoy Apr 28 '10 at 3:20

2 Answers 2

up vote 8 down vote accepted

I believe 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 the set indexed by {1,2,5,7,10,12} is the unique exact subset (up to complementation).

share|improve this answer
    
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 ? –  Ewan Delanoy Apr 27 '10 at 19:47
    
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. –  Tony Huynh Apr 27 '10 at 20:21
    
Nice argument Tony ! Thanks. –  Ewan Delanoy Apr 28 '10 at 3:22
    
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'. –  Tony Huynh Apr 28 '10 at 4:20

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.

share|improve this answer
    
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. –  Tony Huynh Apr 28 '10 at 14:47
    
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"... –  damiano Apr 28 '10 at 15:50
    
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. –  Tony Huynh Apr 28 '10 at 17:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.