3
$\begingroup$

This question is a similar restatement of this question which has been recently closed.

Let

$$A=\{\ (x,y,z)\in\mathbb{N}^3\ |\ 0\leq x,y,z\leq7\}$$

and

$$B\subset A \text{ with } |B|\geq49.$$

Show that there exists two distinct vectors $\ x,\ y \in B$ such that $x \leq y$, where the inequality is defined element-wise.

Trying to get a contradiction, construct B such that the inequality does not hold for any distinct pair. Then, $(0,0,0)$ and $(7,7,7)$ are definitely not in B. If, in the question, A were defined as:

$A=\{\ (x,y,z)\in\mathbb{N}^3\ |\ 0\leq x,y,z\leq1\}$

and if $|B|\geq 4$ then at least one of $(1,0,0), (0,1,0)$ and $(0,0,1)$ would be in B, say $(1,0,0)\in B$. This implies $(0,0,0),(1,1,0),(1,0,1),(1,1,1) \notin B$. So,

$B= \{\ (1,0,0),(0,1,0),(0,0,1),(0,1,1)\ \}$.

A contradiction!


I have tried to utilise the pigeonhole principle and use geometric intuition ( the convex cone in $\mathbb{R}^3$) but I only managed to end up with a rather complex summation formula having $49\pm1$ terms with the inclusion- exclusion principle. I am guessing that there is an easier and more general approach.

$\endgroup$
  • $\begingroup$ Thanks 6005, it looks better this way :) $\endgroup$ – Deniz Sargun Jul 27 '15 at 7:20
  • $\begingroup$ If you take the subset of $A$ defined by $A_0 = \{(x,y,z) \in A \; : \; x + y + z = 10\}$, it has size 48, suggesting some sort of pigeonhole on $A_0$. But I ran into a slight complication with that. I will come back tomorrow and see if anyone has figured it out. $\endgroup$ – 6005 Jul 27 '15 at 7:47
  • $\begingroup$ Deniz, no problem. Usually you only quote the problem statement. All proofs and previous work should not be quoted. It's to make the problem statement easily visible. $\endgroup$ – 6005 Jul 27 '15 at 7:48
  • 1
    $\begingroup$ Well it's only an idea, I'll think sometime later (don't have time now). But the idea of an greedy algorithm(en.wikipedia.org/wiki/Greedy_algorithm) is that it very scalable, because it doesn't need to check the whole solution space, but efficiently makes only 'good solution' at every intermediate step, and thereby in the end arrives at a globally optimal solution. This is scalable, and such an algorithm will most likely give insight into the problem structure and after some analysis help you solve the general case analytically. $\endgroup$ – user2520938 Jul 27 '15 at 8:11
  • 1
    $\begingroup$ @user2520938 I was on a vacation for the last few days and could not reply. You can not imagine my joy the time I saw your post. I hope you enjoy your stay and get the best out of your time there. For any questions contact me- I can provide an e- mail- or people from the village; anyone will be eager to help you. Bye :) $\endgroup$ – Deniz Sargun Aug 14 '15 at 9:47
2
$\begingroup$

Turns out it is quite easy (this is a bit informal, but if you feel the need I'm sure you can make it rigorous very easily):

We consider every z-slice of the cube separately: the slice $z=0$, $z=1$, etc. We first consider the slices in an unordered fashion, place elements on each slice separately, and then stack the slice on top of each other. We are going to place as many elements on the slices as possible, while ensuring that no $2$ are comparable.

It's not hard to see that on each of these slices there can be at most $8$ elements from $B$ (placed on the diagonal). So we place our first $8$ elements from $B$ on the main-diagonal of one of the slices.

Clearly, once we placed $8$ elements on the diagonal of one of the slices, we can now place at most $7$ elements on any other slice (by placing them on the length-7 next to the main diagonal) (because elements directly above each other are comparable, we cannot use the main diagonal again). There are $2$ such length-7 diagonals, so we can place $7$ elements on the length-7 diagonals of $2$ of the slices.

Clearly now any other slice can have at most $6$ elements on it, again on one of the length-6 diagonals.

We continue in this way, place: $5,6,7,8,7,6,5,4$ elements on the slices. Note the total of $48$. If we use this order of slice from top to bottom we obtain a valid stacking of the slices, in which no $2$ elements are comparable. It's not hard to convince yourself that it's not possible to place any more elements on the slices while still being able to stack them together s.t. no elements are comparable.

Further, it's now easy to generalise: for an $n\times n\times n$ cube: $$\begin{align} &n=0: 0\\ &n=1: 1\\ &n=2: 2+1=3\\ &n=3: 3+2+2=7\\ &n=4: 4+3+3+2=12\\ &n=5: 5+4+4+3+3=19\\ &n=6: 6+5+5+4+4+3=27\\ &n=7: 7+6+6+5+5+4+4=37\\ &n=8: 8+7+7+6+6+5+5+4=48\\ &n=9: 9+8+8+7+7+6+6+5+5=61\\ &\text{etc.} \end{align}$$ Altough the pattern it clear, a closed form is $\frac{(n+1)(n+2)}{2}+\lfloor\frac{n^2}{4}\rfloor$ . See A077043. You can take a look at some of the descriptions to see some equivalent problems to the one you asked (equivalent in the sense that they have the same answers as a function of $n$).


Edit: in case my explaination did not really make it clear, here are some picture for various $n$:

various maximal B

With the mathematica code:

MakeGrid[n_, {x_, y_}, z_] := Array[
  If[x - #1 == -(y - #2),
    Cuboid[{{#1, #2, z}, {#1 + 1, #2 + 1, z + 1}}],
    ## &[]
    ] &
  , {n, n}]
n = 8;
l = Table[Ceiling[(n + 1)/2] + i, {i, 0, n - 1}];
B = Table[MakeGrid[n, {1, l[[i]]}, n - i], {i, 1, Length[l]}];
Print[Length[Flatten[B]]];
Graphics3D[{Red, B}, Axes -> True, AxesLabel -> {x, y, z}]
$\endgroup$
0
$\begingroup$

You can try to cover $A$ with 48 chains. (Chain is a set where any two elements are comparable.) Then, the statement follows easily from the pigeonhole's principle since at least two elements of $B$ must be in the same chain, thus comparable.

Note that if the question is correct, the chain cover of size 48 'must' exist by Dilworth's theorem.

$\endgroup$
  • $\begingroup$ Is this an answer or just an observation? $\endgroup$ – user2520938 Jul 27 '15 at 9:40
  • $\begingroup$ I think it is an answer except that I haven't found the actual chain cover. But then, the cover exists as I said, and will be pretty easy to find I guess. $\endgroup$ – JWL Jul 27 '15 at 9:42
  • $\begingroup$ Oke, but if you can prove the existence of the chain cover, and the existence of the chain cover proves the claim, then we are done right? $\endgroup$ – user2520938 Jul 27 '15 at 9:43
  • $\begingroup$ No, my existence depends on the correctness of the question, which is a cyclic argument. $\endgroup$ – JWL Jul 27 '15 at 9:45
  • $\begingroup$ Still, I think finding the cover is not so hard since we have the antichain of size 48 in the comment of the question. $\endgroup$ – JWL Jul 27 '15 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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