# math question **URL:** \ **Category:** Factual Questions\ **Created:** [August 20, 2001, 4:27pm UTC](https://boards.straightdope.com/t/math-question/77167 "2001-08-20T16:27:37Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![curwin](https://avatars.discourse-cdn.com/v4/letter/c/f05b48/32.png) [@curwin](https://boards.straightdope.com/u/curwin)\ **Post date:** [August 20, 2001, 4:27pm UTC](https://boards.straightdope.com/t/math-question/77167/1 "2001-08-20T16:27:37Z")
I was playing with a little puzzle that consisted of 20 beads in a circle, each with a number from 1 to 20. The purpose of the game is to move the beads around until all the beads are in order. This got me wondering. First of all, what is the maximum number of combinations of beads? I assume 400 (20 squared) but I could be wrong. But more intererstingly (for me) is the question, how many possible combinations of beads are there with not even one set of two consecutive numbers? (And remember this is a circle, so every bead has two numbers next to it). ---
**Author:** ![kabbes](https://avatars.discourse-cdn.com/v4/letter/k/e99b99/32.png) [@kabbes](https://boards.straightdope.com/u/kabbes)\ **Post date:** [August 20, 2001, 4:33pm UTC](https://boards.straightdope.com/t/math-question/77167/2 "2001-08-20T16:33:57Z")
Well unless I’ve misunderstood you, the permutations for beads is 20 x 19 x 18 x 17 x … x 1 = 20! = about 2.43 x 10[sup]18[/sup]. So a lot more than 400. There is a simple method of doing the second bit of the question too, but I’m off home. Enough maths for me today. Someone else will have to fill you in. 😛 pan ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [August 20, 2001, 4:59pm UTC](https://boards.straightdope.com/t/math-question/77167/3 "2001-08-20T16:59:19Z")
Actually, since the beads are arranged on a circle (as opposed to a straight line), the number of possible permutations is not 20! but 19!, which is about 1.22 x 10[sup]17[/sup]. An important note: This is the number of all possible permutations–due to the nature of your puzzle, it’s very possible that not all of these possible permutations can be achieved, it may be that only a certain fraction of the possible permutations can be made with the puzzle. ---
**Author:** ![kniz](https://avatars.discourse-cdn.com/v4/letter/k/c37758/32.png) [@kniz](https://boards.straightdope.com/u/kniz)\ **Post date:** [August 20, 2001, 5:56pm UTC](https://boards.straightdope.com/t/math-question/77167/4 "2001-08-20T17:56:02Z")
Completely off the subject, but I noticed how close the number of posts are for both **kabbes** and **cabbage**. However, **cabbage** became a member almost a year before **kabbes**. That means **kabbes** recently overtook **cabbage**. This is all mundane trivia and thus this post belongs on **MPSIMS**. ---
**Author:** ![kabbes](https://avatars.discourse-cdn.com/v4/letter/k/e99b99/32.png) [@kabbes](https://boards.straightdope.com/u/kabbes)\ **Post date:** [August 21, 2001, 8:54am UTC](https://boards.straightdope.com/t/math-question/77167/5 "2001-08-21T08:54:37Z")
Here’s another snippet for ya. **kabbes** means **Cabbage** in Luxembourgese. We also both have a degree in mathematics (I believe). This is all pure coincidence. I have no idea why **Cabbage** chose his name but I had personal reasons for choosing mine and did so before I was aware of another green-leafed mathematician on the Straight Dope. In other news: bugger. I can’t believe that I made such an elementary permutation mistake. In my defence, I was trying to leave work and was in a rush, but still! pan ---
**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\ **Post date:** [August 21, 2001, 1:04pm UTC](https://boards.straightdope.com/t/math-question/77167/6 "2001-08-21T13:04:52Z")
OK, I know I shouldn’t ask… but: how does this puzzle work? If they are in a circle, and strung on one wire, how can you move any of them relative to each other? And if they are free to move anywhere, it seems like a very simple puzzle. What are “legal” moves in this puzzle? This has nothing to do with answering the OP, I’m just curious. ---
**Author:** ![curwin](https://avatars.discourse-cdn.com/v4/letter/c/f05b48/32.png) [@curwin](https://boards.straightdope.com/u/curwin)\ **Post date:** [August 21, 2001, 1:14pm UTC](https://boards.straightdope.com/t/math-question/77167/7 "2001-08-21T13:14:20Z")
It’s not that hard (or that easy). The beads aren’t on a wire, they’re on a circular track. There is a thing that turns and can hold 4 beads, allowing you to reverse the order of 4 beads at a time. The factoral answer makes more sense – but does anyone have an answer to the second part of my question? ---
**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\ **Post date:** [August 21, 2001, 1:26pm UTC](https://boards.straightdope.com/t/math-question/77167/8 "2001-08-21T13:26:04Z")
Thank you. For the second part, let’s see… The first one can be any one of 20 beads. Let’s proceed clockwise. The next one can be 17 of the remaining 19 (I am assuming you don’t want “1” next to “20” either). The next one can be 16 of the remaining 18, and so on. And the last choice is forced since you’re in a circle. So I’m tempted to say the answer is 19 \* 16!. However, that doesn’t deal with the cases where legal choices made at bead n lead to an “unsolvable” situation at the end. So I’m going to back off until the cabbage brothers return. 🙂 ---
**Author:** ![23skidoo](https://avatars.discourse-cdn.com/v4/letter/2/f04885/32.png) [@23skidoo](https://boards.straightdope.com/u/23skidoo)\ **Post date:** [August 21, 2001, 2:47pm UTC](https://boards.straightdope.com/t/math-question/77167/9 "2001-08-21T14:47:22Z")
> [@](#): > > \*Originally posted by muttrox \* > \*\*Thank you. > > For the second part, let’s see… > > The first one can be any one of 20 beads. Let’s proceed clockwise. The next one can be 17 of the remaining 19 (I am assuming you don’t want “1” next to “20” either). The next one can be 16 of the remaining 18, and so on. And the last choice is forced since you’re in a circle. So I’m tempted to say the answer is 19 \* 16!. > > However, that doesn’t deal with the cases where legal choices made at bead n lead to an “unsolvable” situation at the end. > > So I’m going to back off until the cabbage brothers return. 🙂 \*\* Let 13 be the ‘first’ bead. Let 6 be the ‘second’ bead. Let 7 be the ‘third’ bead. Oops. I think that there are 19 \* 17! ways to arrange the bracelet so that _any one given number_ isn’t next to its “consecutive neighbors”. For example, there are 19 \* 17! ways to have the ring such that 13 is next to neither 12 or 14. The number of ways where _no_ number is next to its ‘consecutive neighbors’ has to be lower than that. ---
**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\ **Post date:** [August 21, 2001, 3:03pm UTC](https://boards.straightdope.com/t/math-question/77167/10 "2001-08-21T15:03:49Z")
Let 13 be the first bead (any of 20 beads). The second bead is 6. (any of 17 beads). The third bead is 7. Whoops! Well, how many values could the 3rd bead have been? There are 18 beads left in the bag, of which 16 ought to be valid. OK, we repick and get 9 for the 3rd bead. The 4th bead is… there are 17 beads left, of which 15 are valid. So we have a pattern, 20 \* 17! factorial, which would go to 19\*17! due to the circular pattern. However, if we continue the example, we see another pitfall. Let’s say the 4th bead is 7. 5th bead: There are 16 beads left. But this time, 15 of them are valid, not 14. We have already used the “6”, only the “8” is left to mess us up. We would multiply not by 14, as the pattern suggest, but by 15. So here we have a case where it seems like the answer should be _more_, not _less_ than what I originally said. On the other hand, maybe situations like this occur exactly enough to balance the “dead end” routes. Hmm. Well 23, I don’t think your analysis is right, but I’m thinking mine ain’t either. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 21, 2001, 3:07pm UTC](https://boards.straightdope.com/t/math-question/77167/11 "2001-08-21T15:07:36Z")
The simplest way to get the answer to the second part is to figure out how many permutations do have at least one pair of consecutive numbers, and subtract that from the total number of possible permutations. I’m kinda busy right now, otherwise I’d do it. ---
**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\ **Post date:** [August 21, 2001, 3:11pm UTC](https://boards.straightdope.com/t/math-question/77167/12 "2001-08-21T15:11:15Z")
Let 13 be the first bead (any of 20 beads). The second bead is 6. (any of 17 beads). The third bead is 7. Whoops! Well, how many values could the 3rd bead have been? There are 18 beads left in the bag, of which 16 ought to be valid. OK, we repick and get 9 for the 3rd bead. The 4th bead is… there are 17 beads left, of which 15 are valid. So we have a pattern, 20 \* 17! factorial, which would go to 19\*17! due to the circular pattern. However, if we continue the example, we see another pitfall. Let’s say the 4th bead is 7. 5th bead: There are 16 beads left. But this time, 15 of them are valid, not 14. We have already used the “6”, only the “8” is left to mess us up. We would multiply not by 14, as the pattern suggest, but by 15. So here we have a case where it seems like the answer should be _more_, not _less_ than what I originally said. On the other hand, maybe situations like this occur exactly enough to balance the “dead end” routes. Hmm. Well 23, I don’t think your analysis is right, but I’m thinking mine ain’t either. ---
**Author:** ![kabbes](https://avatars.discourse-cdn.com/v4/letter/k/e99b99/32.png) [@kabbes](https://boards.straightdope.com/u/kabbes)\ **Post date:** [August 21, 2001, 3:14pm UTC](https://boards.straightdope.com/t/math-question/77167/13 "2001-08-21T15:14:48Z")
OK, let’s see. I hope you’re ready to follow this… I’m also assuming that you don’t want 20,1 Define properties E[sub]_i_[/sub] where E[sub]_i_[/sub] is true if _i_(_i_ + 1)occurs in the new permutation. Since we have a circular arrangement, E[sub]_n_[/sub] is the property that _n_1 occurs. The first step is to compute E[sub]_i_[/sub]. Now a permutation with property E[sub]_i_[/sub] can be thought of as a permutation of 1; 2; : : : ;(_i_(_i_ + 1)); : : : ; _n_, where we treat (_i_(_i_ + 1)) as a single item. That is, we permute _n_ - 1 objects in a circle. There are (_n_ - 2)! ways of doing this. Now consider E[sub]_i_[/sub] AND E[sub]_j_[/sub]. There are two cases depending on whether _i_ + 1=_j_ or _i_ +1 \< _j_. In the first case _j_ = _i_ +1, we are permuting the following objects: 1; 2; : : : ;(_i_(_i_ +1)(_i_ +2)); : : :; _n_ where _i_(_i_ +1)(_i_ +2)is a single item. There are _n_ - 2 objects, so the number of ways of doing this in a circle is (_n_ - 3)! In the second case _j_ \>_i_+1 we are permuting the objects: 1; 2; : : : ;(_i_(_i_ +1)); : : :;(_j_(_j_ + 1)); : : : ; _n_, where _i_(_i_ +1)and _j_(_j_ +1) are single objects. But there are still _n_ - 2 objects in total and hence (_n_ - 3)! permutations. In the general case where we consider _k_ properties, no matter how the properties are ordered and what size “meta-objects” are created by combining integers, the total number of objects is reduced by the number of properties, which is _k_. So there will still be (_n_ - _k_ - 1)! permutations around a circle. In this case, we are interested in the number of situations in which none of the E[sub]_i_[/sub]’s occur. This is (_n_ - 1)! - SUM[sub]k=2[/sub][sup]k = n-1[/sup]([sup]n[/sup]C[sub]k[/sub](_n_ - _k_)!) = (_n_ - 1)! - SUM[sub]k=2[/sub][sup]k = n-1[/sup](_n_!/(_k_!(_n_ - _k_)!)(_n_ - _k_)!) = (_n_ - 1)! - SUM[sub]k=2[/sub][sup]k = n-1/sup I’m sure that there is a simple way of evaluating this sum, but I’ve devoted enough time to it for now unfortunately. I’m gonna get in trouble unless I submit this now and get on with it. So I did it on Excel instead (how inelegant!) So for now, your answer is: 20! - “the sum from k = 2 to 19 of” (20! / k!) which is negative. So I screwed up. Bollocks. ::scrutinizes sea of italics and superscripts:: Arse if I can see where the error is. I’ll try later if noone has finished it off. pan ---
**Author:** ![23skidoo](https://avatars.discourse-cdn.com/v4/letter/2/f04885/32.png) [@23skidoo](https://boards.straightdope.com/u/23skidoo)\ **Post date:** [August 21, 2001, 3:19pm UTC](https://boards.straightdope.com/t/math-question/77167/14 "2001-08-21T15:19:31Z")
> [@](#): > > \*Originally posted by muttrox \* > \*\*Thank you. > > For the second part, let’s see… > > The first one can be any one of 20 beads. Let’s proceed clockwise. The next one can be 17 of the remaining 19 (I am assuming you don’t want “1” next to “20” either). The next one can be 16 of the remaining 18, and so on. And the last choice is forced since you’re in a circle. So I’m tempted to say the answer is 19 \* 16!. > > However, that doesn’t deal with the cases where legal choices made at bead n lead to an “unsolvable” situation at the end. > > So I’m going to back off until the cabbage brothers return. 🙂 \*\* I shouldn’t be allowed to think early in the morning. Take back what I said before, it was obviously produced by sleeplessness the night before. However… Wouldn’t the above equation give you: 20 \* 17! You could divide by 20 to account for the similar permutations in a bracelet giving just 17! for the answer. BUT: wouldn’t the above formula give you the following: “…the next choice can be 2 of the remaining 4, the next choice can be 1 of the remaining 3…” Are you already ‘forced’ with 3 remaining? What about 2 remaining? Imagine the following order being selected, using the method above: ‘First’:7 ‘second’:5 ‘third’:19 ‘fourth’:6 For the fifth choice, I should be able to choose “14 of the remaining 16”, but in reality I can choose any of the remaining 16, because 5 and 7 are already used. Now is where I run away screaming before I find something wrong with _this_ post too. ---
**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\ **Post date:** [August 21, 2001, 3:21pm UTC](https://boards.straightdope.com/t/math-question/77167/15 "2001-08-21T15:21:42Z")
I assume our posts got crossed in the mail? We’re pointing out the same phenom, right 23? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 21, 2001, 3:24pm UTC](https://boards.straightdope.com/t/math-question/77167/16 "2001-08-21T15:24:20Z")
**kabbes** : You may not have screwed up. Those numbers are large enough that they probably caused an overflow. Excel’s not the best tool for scientific computing. So here’s my try. I’m also assuming that 20 shouldn’t be next to 1. Let p and p + 1 denote the two consecutive numbers. So there are 20 pairs, but let’s cut that in half, because order doesn’t matter here. We’re down to 10 bad pairs. It doesn’t matter what order the other numbers are in, but they’re no longer in a circle, so there are 18! possible permutations of them. There are 19! total permutations, and 10_18! of them are bad, so the total number of good permutations is 9_18!. It’s positive, anyway; that’s a good sign. 😉 ---
**Author:** ![23skidoo](https://avatars.discourse-cdn.com/v4/letter/2/f04885/32.png) [@23skidoo](https://boards.straightdope.com/u/23skidoo)\ **Post date:** [August 21, 2001, 3:28pm UTC](https://boards.straightdope.com/t/math-question/77167/17 "2001-08-21T15:28:44Z")
> [@](#): > > \*Originally posted by muttrox \* > \*\*I assume our posts got crossed in the mail? We’re pointing out the same phenom, right 23? \*\* Yeah, lol, yours wasn’t there when I started composing mine. 🙂 ---
**Author:** ![23skidoo](https://avatars.discourse-cdn.com/v4/letter/2/f04885/32.png) [@23skidoo](https://boards.straightdope.com/u/23skidoo)\ **Post date:** [August 21, 2001, 4:18pm UTC](https://boards.straightdope.com/t/math-question/77167/18 "2001-08-21T16:18:26Z")
> [@](#): > > _Originally posted by ultrafilter \* > \*\*So here’s my try. I’m also assuming that 20 shouldn’t be next to 1. Let p and p + 1 denote the two consecutive numbers. So there are 20 pairs, but let’s cut that in half, because order doesn’t matter here. We’re down to 10 bad pairs. It doesn’t matter what order the other numbers are in, but they’re no longer in a circle, so there are 18! possible permutations of them. There are 19! total permutations, and 10_18! of them are bad, so the total number of good permutations is 9\*18!. > > It’s positive, anyway; that’s a good sign. 😉 \*\* I get the 20 pairs part. But why do you divide by 2? Does each of the twenty pairs have a “double”? What are the 10 bad pairs? ---
**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\ **Post date:** [August 21, 2001, 4:35pm UTC](https://boards.straightdope.com/t/math-question/77167/19 "2001-08-21T16:35:44Z")
Ultra, I’m confused by your whole chain of logic. I assume you were dividing by 2 to distinguish “12-13” from “13-12”, but I’m not following your overall reasoning. What do you mean they’re no longer in a circle? BTW, interesting question about mathematical instinct… once we get the answer, what percentage of possible arrangements do y’all think will be “bad”? Ultra seems to be saying 10/19, or slightly above 50%. I’m going to guess 20% or so. ---
**Author:** ![kabbes](https://avatars.discourse-cdn.com/v4/letter/k/e99b99/32.png) [@kabbes](https://boards.straightdope.com/u/kabbes)\ **Post date:** [August 21, 2001, 4:41pm UTC](https://boards.straightdope.com/t/math-question/77167/20 "2001-08-21T16:41:54Z")
Based on my above approach, I’m guessing that about 1000% are “bad”. Dammit, I still can’t see what’s wrong. Or rather, I can see one thing that is wrong\*, but it still gives a negative answer Make no mistake though, my method _is_ the only way to truly get the answer. The other approaches you’re coming up with will leave gaps because they don’t take every possibility into account systematically. Trust me on this - you don’t want to mess around when you start dealing with combinatorics. Now if I can just work out where I’m going wrong… pan \*Should be the sum from 1 to 19 of [sup]n[/sup]C[sub]k[/sub](n - k - 1)! But when k = 1 this gives n.(n-2)! \> (n-1)! Problem! [Next page](https://boards.straightdope.com/t/math-question/77167.md?page=2)