0
$\begingroup$

I asked a question,

AOPS Math Jam

If you look at #9: **Please CTRL:F -> ** this: *"Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. *"

As you see, two of the cases are just cyclic shifts of each other.

I do not understand, why they are considered different cases?

$\endgroup$
8
  • 1
    $\begingroup$ The table is round, but the chairs are distinguishable. Once you fix chair 1 to be at the top, you no longer have to worry about cyclic shifts. $\endgroup$
    – 6005
    Aug 9, 2015 at 20:15
  • 1
    $\begingroup$ As DPatrick says: "The circularness of the table makes it a bit tricky. How do we account for the circularness? One way is to focus on a particular chair -- say the chair at the top of the table in the picture below:" $\endgroup$
    – 6005
    Aug 9, 2015 at 20:15
  • $\begingroup$ @6005, Okay that is helpful so far. So he has fixed a chair, so there are no more cyclic shifts basically? $\endgroup$
    – Amad27
    Aug 9, 2015 at 20:19
  • $\begingroup$ Yes, since the chairs are labeled, if you cyclically shift them, the fixed chair (chair 1) will now be in a different place. So that is a different subset. The cyclic shift is really a red herring, since the chairs are distinguishable. See Rolf Hoyer's answer. $\endgroup$
    – 6005
    Aug 9, 2015 at 20:21
  • $\begingroup$ @6005, Wait a second. So If we had, take from the one left to the top, the top, and one right to the top as. $\{1, 2, 3\}$ then we take the second case and cyclic shift, is the subset $\{1, 2, 3 \}$ which we will have count as the same "subset" as the first one? (just the same arrangement cycled one to the left)? $\endgroup$
    – Amad27
    Aug 9, 2015 at 20:50

2 Answers 2

1
$\begingroup$

Since the chairs are distinguishable, cyclic shifts very well may yield different subsets. For instance, you want to treat $\{1,2,3\}$ and $\{2,3,4\}$ as distinct subsets of $\{1,2,3,4,5,6,7,8,9,10\}$.

$\endgroup$
0
0
$\begingroup$

Let's make it simple. Suppose you number the chairs serially as 1,2,3,...10, and do not disturb this order. Then any rotation will not change the subsets you can form.

The only difference from chairs arranged in a row is that 10-1 are also connected.

Further, there is no point in, say , interchanging 1 and 4, making the arrangement 4,2,3,1,5,..... It will only confuse the issue.

$\endgroup$
2
  • $\begingroup$ I do not understand this actually at all. Take 4 chairs for even more simplicity. $ABCD$ I know the cyclic shifts in the same order will not change anything, but there is a different in: $ABCD$ and $ABDC$ $\endgroup$
    – Amad27
    Aug 10, 2015 at 9:54
  • $\begingroup$ Ok, "cyclic shift" is the same as what I call "rotation", so ABCD, BCDA, etc are identical and (as you have written) ABCD and ABDC are not. Your heading says "Distinguishable objects..." but actually, the chairs are identical, and we are numbering (or labelling) them for our convenience. We shall only consider, e.g. the arrangement ABCD for determining how many subsets contain at least 3 chairs: these are ABC, BCD, CDA, DAB, and ABCD. $\endgroup$ Aug 10, 2015 at 10:20

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.