Wednesday, November 16, 2022
HomePuzzlesgeometry - Plant 9 timber in 10 rows of three

geometry – Plant 9 timber in 10 rows of three

I’ve utterly rewritten this publish to hopefully be extra coherent.

The geometric puzzle suggests a associated combinatorial puzzle:

Given 9 objects, what number of non-isomorphic collections are there of ten units of three objects every, such that no two of the units have multiple object in widespread?

Where two collections are isomorphic if there’s a permutation of the 9 objects (timber) that transforms one assortment into the opposite.

Every answer to the geometric puzzle gives an answer to the combinatorial one. Solutions to the combinatorial puzzle thus prohibit the chances for options to the geometric one, and supply steering on discovering them.

The combinatorial puzzle admits solely 4 options:

Theorem: The following are the one options to the combinatorial puzzle:

• Objects: \${A, B, C, 1, 2, 3, 4, 5, 6}\$ Collections: \$\$ABC, A14, A25, A36, B15, B26, B34, C16, C24, C35\$\$
\$\$ABC, A14, A25, A36, B16, B24, B35, C13, C26, C45\$\$
\$\$AB1, AC2, BC3, A34, A56, B46, B25, C16, C45, 123\$\$
• Objects: \${A, B, C, D, 1, 2, 3, 4, *}\$ Collections: \$\$AB*, CD*, AC1, AD2, BC3, BD4, A34, B12, C24, D13\$\$

Proof:

Given such a set, outline an occasion is a set \$S\$ within the assortment, and a tree \$t\$ with \$tin S\$. As there are \$10\$ units of \$3\$ timber every, there are \$30\$ cases in all. Define the diploma of a tree to be the variety of cases of which it’s a half. A tree of diploma \$n\$ is known as an \$n\$-tree. Since there are \$9\$ timber, the common diploma of a tree is \$frac {30}9 = 3frac13\$. Therefore, some timber should have diploma \$4\$ or extra.

Lemma:

• The most diploma for any tree is \$4\$.
• Any 4-tree shares a typical set with each different tree.
• The minimal diploma for any tree is a minimum of half the variety of 4-trees.

Proof:

Let \$n\$ be the diploma of a tree \$T\$. Then the \$n\$ units containing \$T\$ encompass \$2n\$ cases apart from these for \$T\$. If any two of those cases are for a similar tree, they can’t be in the identical set, and so the 2 units they’re in have two factors in widespread (the shared level and \$T\$) which isn’t allowed. Thus we should have \$2n + 1\$ distinct timber (together with \$T\$). So \$2n + 1 le 9\$, and \$n le 4\$. If \$n = 4\$, then all timber are represented, so the 4-tree shares a set with each different tree. Now for any tree \$T\$, it should share a set with each 4-tree, so the depend \$d_4\$ of 4-trees satisfies \$d_4 le 2n\$, or \$n ge frac{d_4}2\$

QED

Let \$d_n\$ be the variety of timber of diploma \$n\$. By the lemma \$n le 4\$. Then the variety of cases (30) is the sum of the levels for all timber, which is \$\$ 30 = 4d_4 + 3d_3 + 2d_2 + 1d_1\$\$
however \$\$9 = d_4 + d_3 + d_2 + d_1\$\$
Eliminating \$d_4\$ offers
\$\$ 6 = d_3 + 2d_2 + 3d_1\$\$
So the overall variety of timber of diploma \$< 4\$ is at most \$6\$, leaving a minimum of \$3\$ 4-trees. By the lemma, the smallest diploma attainable is subsequently \$2\$, so \$d_1 = 0\$ and \$\$6 = d_3 + 2d_2\$\$
In explicit \$0 le d_2 le 3\$.

• \$d_2 = 0\$ offers \$d_3 = 6, d_4 = 3\$
• \$d_2 = 1\$ offers \$d_3 = 4, d_4 = 4\$
• \$d_2 = 2\$ offers \$d_3 = 2, d_4 = 5\$, which contradicts the lemma,
• \$d_2 = 3\$ offers \$d_3 = 0, d_4 = 6\$, which contradicts the lemma.

Consider the case \$d_2 = 1, d_3 = 4, d_4 =4\$. Label the 4-trees \$A, B, C, D\$, the 3-trees \$1, 2, 3, 4\$, and the 2-tree “\$*\$”. Since the 2-tree shares units with all \$4\$ 4-trees, these units should be \$AB* := {A, B, *}\$ and \$CD*\$.
There can’t be set of simply 4-trees, as any such set would share two timber with \$AB*\$ or \$CD*\$. Therefore the units shared by pairs of 4-trees should have a 3-tree because the third member. By relabeling we are able to take \$AC1\$ and \$AD2\$ as two of the units. The 4th set for \$A\$ should be \$A34\$, as all different timber have been paired with \$A\$. Suppose \$BC2\$ have been additionally a set. Then \$C34\$ would additionally need to be as \$C\$ has been paired with all different timber. This conflicts with \$A34\$, so it can’t be that \$BC2\$ is a set. Therefore, relabeling if wanted, we are able to take \$BC3\$ as set, and for related causes \$BD4\$. The remaining units should be \$B12, C24, D13\$, once more as these are the one remaining timber the 4-trees haven’t been paired with. This completes the record given within the theorem for this case.

For the case \$d_3 =6, d_4 = 3\$, label the 4-trees \$A, B, C\$, and the 3-trees \$1,2,3,4,5,6\$.

1. Suppose that the 4-trees don’t share a typical set. In this case we are able to label the timber in order that \$AB1, AC2, BC3\$ are units. Each of \$A, B, C\$ have two extra units every, which they share with \$2\$ 3-trees. By relabeling, three of those are \$A34, A56, B46\$. This additionally requires \$B25\$. \$C\$ stays to be paired with \$1, 4, 5, 6\$, however \$46\$ and \$56\$ have already occurred, so the 2 units should be \$C16\$ and \$C45\$. Finally \$123\$ makes up the final set.
2. When \$ABC\$ is a set, the remaining \$9\$ units should consist of three units every for \$A, B, C\$ matching them with a pair of 3-trees. This offers us 9 decisions of pairs of 3-trees, of which there are \${6choose2} = 15\$ complete, chosen so that every tree seems in 3 of the pairs. To learn the way many non-isomorphic decisions there are, it’s simpler to look at the \$6\$ pairs that weren’t picked. Since every tree seems in 5 pairs general, it should seem in precisely two pairs of the leftovers. This permits us to type paths. For instance, beginning at 1, select one of many two timber paired with it (say 3), then take the opposite tree paired with 3 (say 6), then the opposite tree paired with 6, and so forth. As there may be all the time precisely one different paired tree, this can not finish till you come again to 1, forming a loop. Each tree lies in such a loop, every loop has size a minimum of \$3\$, and the sum of all loop lengths is \$6\$. So there are solely two decisions: a loop of size \$6\$, or \$2\$ loops of size \$3\$. Any two loops of size \$6\$ are isomorphic to one another, as are any pairs of loops of size \$3\$. The remainders for
\$\$ABC, A14, A25, A36, B15, B26, B34, C16, C24, C35\$\$
type \$2\$ loops of size \$3\$, whereas the remainders for
\$\$ABC, A14, A25, A36, B16, B24, B35, C13, C26, C45\$\$
type a loop of size \$6\$. This exhausts all circumstances, so the theory is proved.

QED

There is just not a 1-1 correspondence between combinatorial options and geometric options. Indeed, the 2 geometric options discovered up to now each correspond to \$\$ABC, A14, A25, A36, B15, B26, B34, C16, C24, C35\$\$.

In reality,

Theorem: There is not any geometric answer that corresponds to \$\$AB*, CD*, AC1, AD2, BC3, BD4, A34, B12, C24, D13\$\$.

Proof: Suppose there may be. Then the rows equivalent to \$AB*\$ and \$CD*\$ type both a V, T, or X form, with the intersection at \$*\$. Assuming no strains are parallel, the 3-trees should lie someplace on the strains proven. Rows shaped by the 3-tree on a line and a 4-tree not on it should additionally go by means of a 3-tree on one other line. So the placement of the primary 3-tree decide the placement of the second 3-tree. Placing the 3-tree from the \$AD\$ line in various areas of that line determines areas for the 3-trees on the \$AC\$ and \$BD\$ strains, which in flip every require areas for the 3-tree on the \$BC\$ line. But in all circumstances, the required areas on the \$BC\$ line don’t overlap, making it unattainable to position this tree. The case when a few of the strains are parallel will be thought of within the restrict, and thus fail as nicely. It is unattainable to assemble a geometrical answer for this combitorial case.

\$\$textual content{ V – Shape}\$\$
\$\$start{array}cc AD & AC & DB & BC(AC) & BC(BD)hline
AD1 & AC2 & BD4 & BC2 & BC3
AD2 & AC2 & BD1 & BC2 & BC3
AD3 & AC3 & BD2 & BC3 & BC4
AD4 & AC4 & BD3 & BC1/4 & BC2
AD5 & AC1 & BD3 & BC1 & BC2
AD6 & AC2 & BD4 & BC2 & BC3end{array}\$\$

\$\$textual content{ T – Shape}\$\$
\$\$start{array}cc AD & AC & DB & BC(AC) & BC(BD)hline
AD1 & AC4 & BD4 & BC1/4 & BC3
AD2 & AC4 & BD1 & BC1/4 & BC3
AD3 & AC1 & BD1 & BC1 & BC3
AD4 & AC2 & BD2 & BC2 & BC1/4
AD5 & AC3 & BD3 & BC3 & BC2
AD6 & AC4 & BD4 & BC1/4 & BC3end{array}\$\$

\$\$textual content{ X – Shape}\$\$
\$\$start{array}cc AD & AC & DB & BC(AC) & BC(BD)hline
AD1 & AC2 & BD4 & BC1/4 & BC2
AD2 & AC2 & BD1 & BC1/4 & BC2
AD3 & AC3 & BD2 & BC3 & BC1/4
AD4 & AC4 & BD3 & BC2 & BC3
AD5 & AC1 & BD3 & BC2 & BC3
AD6 & AC2 & BD4 & BC1/4 & BC2end{array}\$\$

QED

RELATED ARTICLES