1
$\begingroup$

Suppose 28 objects are placed along a circle at equal distances. In how many ways can 3 objects be chosen from among them so that no two of the three chosen objects are adjacent nor diametrically opposite? I have done this problem in the following manner: There are 28 ways to choose the first object.For the second object, there are two cases:

Case 1:

It is the next-to-next object from the first object. This can be done in two ways. For each of these two ways, we can choose the third object in 21 ways excluding the 7 as per restrictions. (1 for position of first object,1 for second object,3 for their adjacent positions and 2 for their opposite positions). Therefore, for this case, there are 28*2*21 ways to choose the object.

Case 2:

Second object occupies any other position except for the next to next positions of first object. There are 22 ways to choose the second object then. Now for each of these ways we can choose the third object in 18 ways. So the number of ways is 28*18*22.

Now the answer is 28*(18*22+2*21) ways which is way larger than the given answer:2268. The given solution uses complementary method.Though I understood the solution,I am not able to figure out the flaw in my approach but I understand that something is seriously wrong.

Kindly help me figure out the mistake.

$\endgroup$
1
$\begingroup$

Suppose $28$ objects are placed along a circle at equal distances. In how many ways can three objects be chosen from among them so that no two of the three chosen objects are adjacent nor diametrically opposite?

There are $\binom{28}{3}$ ways to select three of the $28$ objects. From these, we must exclude those cases in which two or more objects are adjacent or diametrically opposite.

There are $28$ ways to select a pair of adjacent objects since there are $28$ possible starting points as we move clockwise around the circle. For each such pair, there are $26$ ways to choose the third object.

The only way to have two pairs of adjacent objects is to select three consecutive objects, which can be done in $28$ ways since, again, there are $28$ possible starting points as we move clockwise around the circle.

By the Inclusion-Exclusion Principle, there are $$\binom{28}{3} - 28 \cdot 26 + 28$$ ways to select three objects so that no two of them are adjacent.

In considering the case of one pair of adjacent objects, we have already excluded those cases in which the third object is diametrically opposite one of the objects in the adjacent pair. We still need to remove those cases in which two objects are diametrically opposite each other but no two of the objects are adjacent.

There are $14$ pairs of diametrically opposite objects. For each such pair, there are $22$ ways of selecting a third object that is not adjacent to either of these objects. Hence, there are $14 \cdot 22$ pairs of diametrically opposite objects which we have not previously excluded.

Hence, the number of permissible selections is $$\binom{28}{3} - 28 \cdot 26 + 28 - 14 \cdot 22 = 2268$$

I am not able to find the flaw in my approach.

You are counting the same arrangements multiple times.

Suppose we number the objects from $1$ to $28$ as we proceed clockwise around the circle.

Case 1: There are two subcases, each of which you have counted multiple times.

Type 1: There is exactly one pair of next-to-next objects.

You count each such selection twice. For example, you count the selection $1, 3, 7$:

  • once when you select $1$, then select $3$ as the next-to-next object, and $7$ as the additional object
  • once when you select $3$, then select $1$ as the next-to-next object, and $7$ as the additional object

Type 2: There are two pairs of next-to-next objects. You count these selections four times.

For example, you count the selection $1, 3, 5$:

  • once when you select $1$, then select $3$ as the next-to-next object, and $5$ as the additional object
  • once when you select $3$, then select $1$ as the next-to-next object, and $5$ as the additional object
  • once when you select $3$, then select $5$ as the next-to-next object, and $1$ as the additional object
  • once when you select $5$, then select $3$ as the next-to-next object, and $1$ as the additional object

There are $28$ cases of the second type, corresponding to the $28$ possible starting points as we move clockwise around the circle.

For the first type, there are $28$ pairs, corresponding to the $28$ possible starting points as we move clockwise around the circle. There are $19$ ways to place the additional object so that it satisfies the restrictions and does not fall into the second type.

We can separate your $21$ ways of selecting the third object into $19$ ways of the first type and $2$ of the second type (choosing the third object to be one that is next-to-next of one end of the pair). Hence, there are actually $$\frac{1}{2} \cdot 28 \cdot 2 \cdot 19 + \frac{1}{4} \cdot 28 \cdot 2 \cdot 2 = 28 \cdot 19 + 28 = 28 \cdot 20 = 560$$ such cases.

Case 2: You count each such selection six times, once for each permutation of the three objects you selected.

However, you have to be careful how you count this case. Notice, for instance, that the selections $1, 4, 19$ and $1, 7, 20$ both satisfy your criteria. However, $1$ and $4$ share excluded spaces, while $1$, $7$, and $20$ do not. Whenever two of the objects are separated by two or three other objects, they share excluded spaces, which you did not take into account.

$\endgroup$
0
$\begingroup$

Taking the circle to be numbered, but the $3$ objects to be identical, we can divide the inadmissible cases out of $\binom{28}3$ total placements into three disjoint types for ease of computation:

  • all three together: $28$

  • exactly two together: $28\cdot24$

  • two diametrically opposite and the third apart: $14\cdot22$

Thus admissible placements $= \binom{28}3 - (28+28\cdot 24+ 14\cdot 22) = 2268$

$\endgroup$

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.