Math Question, not for HW

[pancakes3]

In how many distinct ways can eight different colored beads be arranged on a circular necklace with no clasp or noticeable break?

[Simplicio]

7!

ETA: (that's seven factorial, not me being really excited about the number seven)

[Munch]

Originally Posted by Simplicio

ETA: (that's seven factorial, not me being really excited about the number seven)

Haha - I was going to say!

7! comes out to 40,320.

[fachverwirrt]

Originally Posted by Munch

Haha - I was going to say!

7! comes out to 40,320.

I get 5040. I'm pretty sure you calculated 8! there.

[Simplicio]

Its easy to see why if you already know the number of different combinations for n objects where the order matters is n!. On a circular wire, the order still matters, but there's no "first" spot.

But you can choose an arbitrary color to mark the "start" of the series. Then the one to the right is the "first"spot, the one to the right of that the "second" and so on. So you end up with (n-1) spots for (n-1) beads. Thus (n-1)! total combinations.

[md2000]

Originally Posted by Simplicio

Its easy to see why if you already know the number of different combinations for n objects where the order matters is n!. On a circular wire, the order still matters, but there's no "first" spot.

But you can choose an arbitrary color to mark the "start" of the series. Then the one to the right is the "first"spot, the one to the right of that the "second" and so on. So you end up with (n-1) spots for (n-1) beads. Thus (n-1)! total combinations.

yes, if the following are all equivalent ( necklace with no beginning, no end)...

12345678
23456781
34567812

etc. - 8 different "identical" arrangements.
then yes, it's 8!/8 or 7!

[Munch]

Originally Posted by fachverwirrt

I get 5040. I'm pretty sure you calculated 8! there.

Yup - you're right.

[septimus]

Since the necklace seems to be symmetric, let me ... Nitpick:

Only 7!/2
2520 arrangements can be obtained from one of the other 2520 arrangements by simply turning the necklace upside-down.

[TriPolar]

Since there's no mention that the beads take up the entire necklace, there should be an infinite number of distinct arrangement of beads including the gaps between them. I doubt that's what the OP had in mind, but I've got a lot of experience reviewing customer specs for ambiguities. I wouldn't sign that contract until it was clarified. On top of that, the OP isn't clear that there are only 8 beads, just 8 different colors of beads.

[yorick73]

Wait....there is no break in the necklace so the beads cannot be randomly placed. Wouldn't that equal just 8 combinations. I think the OP is suggesting that we start with 8 beads already on a closed necklace. Am I missing something basic?

[ultrafilter]

The general solution is a little more complicated. You need to specify whether you're allowing reflections of a necklace to be distinct, and after that you can use the linked formulas.

[ZenBeam]

Originally Posted by TriPolar

Since there's no mention that the beads take up the entire necklace, there should be an infinite number of distinct arrangement of beads including the gaps between them. I doubt that's what the OP had in mind, but I've got a lot of experience reviewing customer specs for ambiguities. I wouldn't sign that contract until it was clarified. On top of that, the OP isn't clear that there are only 8 beads, just 8 different colors of beads.

The OP says "eight different colored beads". The words "eight", "different", and "colored" are all adjectives modifying "beads", so I don't see how you're getting this ambiguity in the number of beads.

I will add to the nitpick that we don't know if the beads are symmetric. If each bead isn't mirror-symmetric in the along-string direction, and could be strung in either direction, then the number would grow to 7! * 2^7.

[TriPolar]

Originally Posted by ZenBeam

The OP says "eight different colored beads". The words "eight", "different", and "colored" are all adjectives modifying "beads", so I don't see how you're getting this ambiguity in the number of beads.

I will add to the nitpick that we don't know if the beads are symmetric. If each bead isn't mirror-symmetric in the along-string direction, and could be strung in either direction, then the number would grow to 7! * 2^7.

In that case the ambiguity is that there may not be eight different colors. We don't know whether or not 'eight' is the extent of the enumeration of 'color'.

[Frylock]

Originally Posted by yorick73

Wait....there is no break in the necklace so the beads cannot be randomly placed. Wouldn't that equal just 8 combinations. I think the OP is suggesting that we start with 8 beads already on a closed necklace. Am I missing something basic?

Seconded. I do not understand how to interpret "with no clasp or noticeable break" except as implying that the beads basically can't be rearranged. If there's no clasp or noticeable break, how do you get them off the chain to rearrange them?

But if that's not what "no clasp or noticeable break" means, then what does it mean?

[md2000]

Originally Posted by septimus

Since the necklace seems to be symmetric, let me ... Nitpick:

Only 7!/2
2520 arrangements can be obtained from one of the other 2520 arrangements by simply turning the necklace upside-down.

Doh! Of course, unless they are weird one-side-up-only-can't-be-flipped beads.

(Edit - but then they could be rotated on the string after the necklace is flipped. Doh!)

[Indistinguishable]

Originally Posted by Frylock

Seconded. I do not understand how to interpret "with no clasp or noticeable break" except as implying that the beads basically can't be rearranged. If there's no clasp or noticeable break, how do you get them off the chain to rearrange them?

But if that's not what "no clasp or noticeable break" means, then what does it mean?

It means there's no distinguished starting spot; rotating the beads around the necklace without changing their adjacency relation does not produce a new arrangement.

[ultrafilter]

The necklace is really only a way to visualize the problem. If you're hung up on the details, think of how many ways there are to arrange the letters in ABCDEFGH if you don't distinguish between the circular shifts of the words.

[Indistinguishable]

In other words, "How many ways can 8 different symbols be arranged into a sequence, where two sequences are considered the same if they are cyclic shifts of each other (the way ABCDEFGH and DEFGHABC are)?".

ETA: Er, I wrote this before refreshing the page; ultrafilter's post wasn't there yet.

[ZenBeam]

Originally Posted by TriPolar

In that case the ambiguity is that there may not be eight different colors. We don't know whether or not 'eight' is the extent of the enumeration of 'color'.

It doesn't matter. There'd still be eight different beads, even if some are the same color. Maybe they have different sizes or shapes.

[Senegoid]

Originally Posted by Simplicio

7!

ETA: (that's seven factorial, not me being really excited about the number seven)

My 11th grade Algebra teacher was quite careful to make the same point, explicitly telling us that 6! (the example he always used), is not pronounced
SIX!

A friend of mine, a molecular biologist and research mathematecian, told me of a time he didn't know the factorial notation. He saw some derivation or something in his undergrad textbook, which ended up (skipping a few step) pronouncing that the final answer reduced to 6!

My friend tried and tried to figure how one got 6 for the answer (not knowing that ! meant factorial), and upon failing to do so, that only reinforced his interpretation that the ! simply meant that this was a surprising and remarkable fact. !

[pancakes3]

thanks guys (factorial)

[pancakes3]

Got another one. These are practice mathcounts question that a friend's daughter of mine is trying and when he doesn't get it, he forwards it to me, and I am now forwarding to this forum.

The digits 1-9 are each used once to form a positive 9-digit integer. There are 362880 possible integers like this. How many of them have the digits 1, 2, and 3 in order from least to greatest throughout the integer? One such example is 451,728,936

(so the 1-2-3 doesn't have to go in order.)

[Frylock]

Originally Posted by pancakes3

Got another one. These are practice mathcounts question that a friend's daughter of mine is trying and when he doesn't get it, he forwards it to me, and I am now forwarding to this forum.

The digits 1-9 are each used once to form a positive 9-digit integer. There are 362880 possible integers like this. How many of them have the digits 1, 2, and 3 in order from least to greatest throughout the integer? One such example is 451,728,936

(so the 1-2-3 doesn't have to go in order.)

You just need to figure out how many items are in the following list:

123......
12.3.....
12..3....
.
.
.
1..2...3.
1..2....3
1...23...
.
.
.
.
....1..23
.....123.
.....12.3
.....1.23
......123

No time now to count it up but I imagine conceptualizing the problem that way should make the math more obvious.

[Frylock]

nvm

[TriPolar]

Ok, I wrote all the numbers down on a piece of paper, then used 3 different colored highlighters for the digits 1, 2, and 3, with the colors red, green, and blue. Then I counted up the ones that an RGB pattern in them and got 60480. I may not have done this carefully, so I'll try it again to check.

[Frylock]

Originally Posted by TriPolar

Ok, I wrote all the numbers down on a piece of paper, then used 3 different colored highlighters for the digits 1, 2, and 3, with the colors red, green, and blue. Then I counted up the ones that an RGB pattern in them and got 60480. I may not have done this carefully, so I'll try it again to check.

[Frylock]

Never mind what I posted above: I completely misread the problem.

[TriPolar]

Yep, recounted, 60480 is it.

[Great Antibob]

Here's how to work that problem in a more formal way.

There are 9 "positions". There are C(9,3) = 84 ways to choose which positions the 1, 2, 3 go in.

This is the simple way to compute what Frylock was trying to do by hand.

*Note: equivalently, you can choose which positions the other 6 numbers go in, or C(9,6) = 84, which works out to the same.

For the other 6 numbers, there are 6! = 720 permutations. For example, if the first three numbers are 123, there are 720 ways to arrange the remaining 6 numbers:

123456789
123456798
123987654
etc

So, there are a total of C(9,3)*6! = 84*720 = 60,480 such integers, which matches what TriPolar got by hand.

[Frylock]

Originally Posted by Frylock

You just need to figure out how many items are in the following list:

123......
12.3.....
12..3....
.
.
.
1..2...3.
1..2....3
1...23...
.
.
.
.
....1..23
.....123.
.....12.3
.....1.23
......123

No time now to count it up but I imagine conceptualizing the problem that way should make the math more obvious.

To correct the above, you take the number of items on the implied list I gave, and multiply it by the number of possible combinations of six digits in six spaces.

[pancakes3]

Originally Posted by Great Antibob

Here's how to work that problem in a more formal way.

There are 9 "positions". There are C(9,3) = 84 ways to choose which positions the 1, 2, 3 go in.

This is the simple way to compute what Frylock was trying to do by hand.

*Note: equivalently, you can choose which positions the other 6 numbers go in, or C(9,6) = 84, which works out to the same.

For the other 6 numbers, there are 6! = 720 permutations. For example, if the first three numbers are 123, there are 720 ways to arrange the remaining 6 numbers:

123456789
123456798
123987654
etc

So, there are a total of C(9,3)*6! = 84*720 = 60,480 such integers, which matches what TriPolar got by hand.

doesn't 9C3 method just give the exact combinations where 1-2-3 are in a row?

[TriPolar]

Originally Posted by pancakes3

doesn't 9C3 method just give the exact combinations where 1-2-3 are in a row?

I don't know, but he got the same total I did, which included all that had the sequence 1-2-3 going left to right, including numbers like 516283794.

ETA: I assumed you weren't counting rotations like 345678912.

[jpei]

Here's another way to get the same answer:

Let us call this set of 9-digit integers with the digits 1-9 used once, the set X.

Ignoring all other digits, there's nothing special about the digits 1, 2, and 3 being in ascending order. They could just as easily be in the order 1, 3, and 2, or 2, 1, and 3.

We can imagine dividing this set X into:
{The subset with 1,2,3 being in the order 123}
{The subset with 1,2,3 being in the order 132}
{The subset with 1,2,3 being in the order 213}
{The subset with 1,2,3 being in the order 231}
{The subset with 1,2,3 being in the order 312}
{The subset with 1,2,3 being in the order 321}

One may check that each number in X belongs to exactly one of these subsets.

Given no further restrictions, one may conclude that by symmetry, these sets are of equal size. The problem statement gives the size of X as 362880, so there are 362880/3! = 60480 such numbers having the digits 1, 2, and 3 in order.

[Great Antibob]

Originally Posted by pancakes3

doesn't 9C3 method just give the exact combinations where 1-2-3 are in a row?

No, it's the number of different positions you can choose for the numbers.

Let's say you have 9 "positions"

_ _ _ _ _ _ _ _ _

How many ways can you choose 3 of these positions for 1-2-3? The answer is 9C3.

You can always verify it by counting them by hand:

1 2 3 _ _ _ _ _ _
1 _ 2 3 _ _ _ _ _
1 _ _ 2 3 _ _ _ _
etc

There are 9C3 = 84 of these.

As I noted, you can equivalently use 9C6, which is the number of ways of choosing which positions 1-2-3 are NOT in.

After you have that, 6! is the number of combinations for the rest, i.e. after the positions of 1-2-3 are decided.

For example, if you have _ _ 1 _ 2 _ _ 3 _, then there are 6! = 720 ways to arrange the other 6 digits in the blanks.

[Great Antibob]

By the way, another way to check the 9C3 is ok is by allowing permutations of 1-2-3.

So, if you allowed 3-2-1, 1-2-3, 1-3-2, etc, we'd have 9P3, instead.

Including the other 6 digits, the total number of integers would be:

9P3 * 6!, which works out to (9!/6!)*6! = 9!

So, the calculation using 9C3 is consistent with allowing permutations of all 9 digits without constraint.

This is the same thing that jpei noted but from the other direction.

[TriPolar]

Ok, so if you want to count rotations, I just looked for all combinations of RGB, BRG, and GBR. There are 181440 of those.

I just realized I didn't have write down ALL the numbers, just the integers between 123456789 and 987654321. It was really hard writing down those irrational numbers, and you don't even use them.

[Jas09]

Props to jpei (I did it the longer way) - that's very elegant and exactly the sort of thing MathCounts would applaud.

[TriPolar]

Originally Posted by TriPolar

Ok, so if you want to count rotations, I just looked for all combinations of RGB, BRG, and GBR. There are 181440 of those.

Originally Posted by Jas09

Props to jpei (I did it the longer way) - that's very elegant and exactly the sort of thing MathCounts would applaud.

Yes, look at that! 3*60480=181440. That would have been way easier.

[pancakes3]

Twofer:

1) What is the largest value of n for which 213! is divisible by (7!)^n

2) Let N be any 3-digit integer which has none of its digits equal to zero. Let M be the 3-digit integer formed by reversing the order of N's digits. What is the greatest integer that is always a factor of the positive difference of N and M. (is it 0?)

[truthSeeker2]

Originally Posted by pancakes3

Twofer:

1) What is the largest value of n for which 213! is divisible by (7!)^n

2) Let N be any 3-digit integer which has none of its digits equal to zero. Let M be the 3-digit integer formed by reversing the order of N's digits. What is the greatest integer that is always a factor of the positive difference of N and M. (is it 0?)

1.

Since 7 is the largest prime number from 1 to 7. Count all the factors of 7 from 1 to 213 for the answer:
Answer = 213/7 + 213/49 = 34

[truthSeeker2]

Originally Posted by pancakes3

Twofer:

1) What is the largest value of n for which 213! is divisible by (7!)^n

2) Let N be any 3-digit integer which has none of its digits equal to zero. Let M be the 3-digit integer formed by reversing the order of N's digits. What is the greatest integer that is always a factor of the positive difference of N and M. (is it 0?)

2. yes its 0
say:
N =111
M =111

[Indistinguishable]

Originally Posted by truthSeeker2

2. yes its 0
say:
N =111
M =111

It's 99 (which happens to divide 0; also, the question-writer was unduly skittish about digits being equal to zero).

Let the original number be A * 100 + B * 10 + C. Its reverse is then C * 100 + B * 10 + A. The difference will be (A - C) * 99. (And taking its absolute value won't change what divides it). So 99 always divides the difference, and if |A - C| = 1, nothing greater will.

[truthSeeker2]

Originally Posted by Indistinguishable

It's 99 (which happens to divide 0; also, the question-writer was unduly skittish about digits being equal to zero).

Let the original number be A * 100 + B * 10 + C. Its reverse is then C * 100 + B * 10 + A. The difference will be (A - C) * 99. (And taking its absolute value won't change what divides it). So 99 always divides the difference, and if |A - C| = 1, nothing greater will.

Oops I missed that the question mentions "positive difference" , so the difference cant be zero. Hence A cant be same as C.
You are right.

[Indistinguishable]

Originally Posted by truthSeeker2

Oops I missed that the question mentions "positive difference" , so the difference cant be zero. Hence A cant be same as C.
You are right.

A CAN be the same as C, and the answer would still be 99, in the sense that 99 divides 0. The question is distractingly, unnecessarily paranoid in its wording.

[Indistinguishable]

Originally Posted by truthSeeker2

Since 7 is the largest prime number from 1 to 7. Count all the factors of 7 from 1 to 213 for the answer:
Answer = 213/7 + 213/49 = 34

This is the correct answer, but it's not clear to me that we can get away with only counting factors of 7 (and not the other prime factors of 7!) just because it's the largest prime from 1 to 7.

For example, 7 is also the largest prime from 1 to 10. But 10!³⁴ doesn't divide 213!. The largest power of 10! which divides 213! is only 10!²⁵.

[truthSeeker2]

Originally Posted by Indistinguishable

This is the correct answer, but it's not clear to me that we can get away with only counting factors of 7 (and not the other prime factors of 7!) just because it's the largest prime from 1 to 7.

For example, 7 is also the largest prime from 1 to 10. But 10!³⁴ doesn't divide 213!. The largest power of 10! which divides 213! is only 10!²⁵.

Right, I know. Since 7 was a smaller number I took smallest way for explaining.

Otherwise one would need to count factors of every prime number. like in 10! :
2's factor comes 8 times
3's factor comes 4 times
5's factor comes 2 times
7's factor comes once.

Count factors in 213! for each of these
For 2:
213/2+213/4+213/8+213/16+213/32+213/64 + 213/128
Divide it by 8. Call it a

For 3
213/3+213/9+213/27+213/81
Divide it by 4. Call it b

For 5
213/5+213/25+213/125
Divide it by 2. Call it c.

For 7
213/7+213/49
Divide it by 1. Call it d.

The minimum of a,b,c,d is the answer. Turns out b=c=25 is the minimum here.
Could there be another shorter procedure??

[Indistinguishable]

Right, that's what I would've done (and I would've done the same thing for the multiple prime factors of 7!). But, like you, I am curious if there is a more efficient, shorter procedure.

For example, I know it is always the case that a! * b! * ... * z! divides k! whenever k >= a + b + ... + z. [Since (a + b + ... + z)!/(a! * b! * ... * z!) has a combinatoric interpretation as the number of ways to arrange in sequence a set comprised of a indistinguishable items of one color, b items of another color, etc.]. From this, we know that b!ⁿ always divides (nb)!, without having to tediously check all the prime factors; thus, we immediately know that 7!³⁰ and 10!²¹ divide 213!. And, of course, by checking just the largest prime factor, we obtain upper bounds on the exponent. But tightening to the precise cutoff, I don't yet know how to do efficiently.

[truthSeeker2]

Originally Posted by Indistinguishable

Right, that's what I would've done (and I would've done the same thing for the multiple prime factors of 7!). But, like you, I am curious if there is a more efficient, shorter procedure.

For example, I know it is always the case that a! * b! * ... * z! divides k! whenever k >= a + b + ... + z. [Since (a + b + ... + z)!/(a! * b! * ... * z!) has a combinatoric interpretation as the number of ways to arrange in sequence a set comprised of a indistinguishable items of one color, b items of another color, etc.]. From this, we know that b!ⁿ always divides (nb)!, without having to tediously check all the prime factors; thus, we immediately know that 7!³⁰ and 10!²¹ divide 213!. And, of course, by checking just the largest prime factor, we obtain upper bounds on the exponent. But tightening to the precise cutoff, I don't yet know how to do efficiently.

Good job.
Here's what I could understand till now:
1. For x! when x is prime, there is only need to check factors of x and that is the anwser. For ex. in 13! the anwser is simply 213/13+213/169

2. For x! when x is non-prime, find the largest prime smaller than x.
For ex. in 33! it is 31, one needs to check for 31 i.e. 213/31. Now go to: 32=2⁵ and 33=3*11. In this case one needs to only check for 2,3,11,31 and no other prime factors.

I might now look at this topic tomorrow only as it is 1:30 am here.

[Indistinguishable]

I'm not sure I understand your #2; are you saying that, if p is the largest prime <= x, you only need to check the prime factors of p, p + 1, ..., x? Why is that? (Indeed, even for the special case of #1, which I find very plausible, I'd like the assurance of a proof)

[truthSeeker2]

Originally Posted by Indistinguishable

I'm not sure I understand your #2; are you saying that, if p is the largest prime <= x, you only need to check the prime factors of p, p + 1, ..., x? Why is that? (Indeed, even for the special case of #1, which I find very plausible, I'd like the assurance of a proof)

Yes, you understood #2 correctly.
#1 can be concluded if one visualizes 213! as blocks of x. For ex., for 13!, as blocks 1 to 13, 14 to 26 and so on.
#2 can be arrived upon using #1 and the method we used in post#46.