Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $a,b,c\in \mathbb{F}_{3^n}$. The summation of two vectors is done with modulo $3$. The elements of vectors are $0,1$ or $2$. We will say that $a,b,c$ form a bad triplet if $a\neq b,a\neq c,b\neq c$ and $a+b+c=0$.

Let $B_k$ be maximal number of bad triplets of set that has $k$ vectors. So we should add vectors to set so that number of total bad triplets in set is maximized.

I have calculated some values of $B_k$.

$B_1 = B_2 = 0,\ B_3 = B_4=1,\ B_5=2,\ B_6=3,\ B_7=5,\ B_8=8,\ B_9=12\ ...$

I need formula for $B_k$ or some evaluation of it. Tried here but no result.

For example (for $n = 2$) the set that produces $B_6=3$ may be $\{(0,0),(1,0),(2,0),(0,1),(1,1),(0,2)\}$

$(0,0)+(1,0)+(2,0) = (0,0)$

$(0,0)+(0,1)+(0,2) = (0,0)$

$(0,2)+(1,1)+(2,0) = (0,0)$

So we have $3$ bad triplets.

I believe that value of $B_k$ doesn't depend on $n$ (size of vectors). I have already showed that $B_k \le$ $\frac{{k} \choose {2}}{3}$ but need more correct formula.

share|improve this question
    
I would work out another term or two then check The On-Line Encyclopedia of Integer Sequences again. Your link has 12 entered twice, and you should probably throw out the first few terms since they are not combinatorially interesting and might not be published with the sequence you're looking for. There are 7 pages matching "1,2,3,5,8,12". –  Slade Oct 16 '13 at 7:46

1 Answer 1

Considering only the $j^{\operatorname{th}}$ coordinate, there are only two possibilities: either $a_j=b_j=c_j$, or all three are distinct. In other words, you are counting the maximum number of Sets that may be made with $k$ cards and $n$ properties!

I know of a decent amount of research about the opposite problem, that of finding the largest possible subsets of $\mathbb{F}_3^n$ that contain no such triples. Here is a post by Terence Tao on the subject, for example. But I don't know offhand about research specifically on your problem.

Note that ${a,b,c}$ is a "bad" triplet if and only if it forms a line in $\mathbb{F}_3^n$. This is an important geometric interpretation that might help in finding similar work. Who knows, maybe somebody has applied algebraic geometry to this...

share|improve this answer

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.