math question

Factual Questions
1

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).

2

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.

:stuck_out_tongue:

pan

3

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.

4

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.

5

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

6

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.

7

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?

8

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. :slight_smile:

9

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.

10

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.

11

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.

12

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.

13

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 n1 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

14

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.

15

I assume our posts got crossed in the mail? We’re pointing out the same phenom, right 23?

16

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 1018! of them are bad, so the total number of good permutations is 918!.

It’s positive, anyway; that’s a good sign. :wink:

17

Yeah, lol, yours wasn’t there when I started composing mine. :slight_smile:

18

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?

19

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.

20

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!