wu :: forums « wu :: forums - Colouring Sectors of a Circle. » Welcome, Guest. Please Login or Register. Mar 13th, 2025, 4:45am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    medium (Moderators: Grimbal, towr, william wu, SMQ, Icarus, ThudnBlunder, Eigenray)    Colouring Sectors of a Circle. « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Colouring Sectors of a Circle.  (Read 615 times) Aryabhatta Uberpuzzler     Gender: Posts: 1321 Colouring Sectors of a Circle.   « on: Dec 11th, 2004, 5:40pm » Quote Modify A circle is divided into p equal sectors, p being a prime number. In how many ways can we colour the p sectors with n colours, assuming 2 colourings are identical iff one can be rotated to get the other.       Example, for p = 3, n = 2 the distinct colourings are RRR BBB RRB BBR IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Colouring Sectors of a Circle.   « Reply #1 on: Dec 14th, 2004, 1:14am » Quote Modify ::(2^p - 2)/p +2 Funnily, the result seems to be an integer only for prime numbers. Did I make a mathematical breakthrough by finding a fast primality test? :: IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Colouring Sectors of a Circle.   « Reply #2 on: Dec 14th, 2004, 3:23am » Quote Modify on Dec 14th, 2004, 1:14am, Grimbal wrote: Did I make a mathematical breakthrough by finding a fast primality test? Unfortunately not, try p = 341 (= 11 * 31) IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Colouring Sectors of a Circle.   « Reply #3 on: Dec 14th, 2004, 3:39am » Quote Modify Damn.  I won't win the Mathematics Nobel prize, then....   IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Colouring Sectors of a Circle.   « Reply #4 on: Dec 14th, 2004, 4:31am » Quote Modify on Dec 14th, 2004, 3:39am, Grimbal wrote: Damn.  I won't win the Mathematics Nobel prize, then....   It doesn't exist anyway IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Colouring Sectors of a Circle.   « Reply #5 on: Dec 14th, 2004, 4:58am » Quote Modify I still won't....   IP Logged Aryabhatta Uberpuzzler     Gender: Posts: 1321 Re: Colouring Sectors of a Circle.   « Reply #6 on: Dec 14th, 2004, 8:46am » Quote Modify Grimbal, your answer is right when 2 colours are used. What about when n colours are used (that was the original problem statement)? Also, your observation is related to Fermat's little theorem, which is/was an essential ingredient in fast randomised algorithms for primality testing. (I think) :: « Last Edit: Dec 14th, 2004, 8:47am by Aryabhatta » IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Colouring Sectors of a Circle.   « Reply #7 on: Dec 14th, 2004, 9:15am » Quote Modify Aaaaah....  I see.....   n colors? :: It works for any value of 2 doesn't it?  If 2 takes the value n, you get:       (np - n)/p +n   Funnily, the result seems to be an integer only for prime numbers. Did I make a mathematical breakthrough by finding a fast primality test?   The logic behind is that if you forget about the rotation part, there are n^p ways.  You have to divide that by p because of the rotation.  However, if there is a single color, the rotation maps to the same combination, so you should not divide by p in that case.  The formula says: take all the cases, remove the monochromatic ones, divide by p and add the monocromatic cases back.  Note that if p were not prime, you could match the colors after a partial rotation, by a divisor of p.  But since p is prime, as soon as you have 2 colors, the rotation has to go thru p different combinations. :: « Last Edit: Dec 14th, 2004, 9:21am by Grimbal » IP Logged Aryabhatta Uberpuzzler     Gender: Posts: 1321 Re: Colouring Sectors of a Circle.   « Reply #8 on: Dec 15th, 2004, 3:01pm » Quote Modify on Dec 14th, 2004, 9:15am, Grimbal wrote: Aaaaah....  I see.....   n colors? Funnily, the result seems to be an integer only for prime numbers. Did I make a mathematical breakthrough by finding a fast primality test? <snip> correct reasoning.   Right! Grimbal, well done.   Also, your observation is related to Fermat's little theorem, which is/was an essential ingredient in fast randomised algorithms for primality testing. (I think)     Also see towr's post for a counterexample when you use the correct value of 2.       IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Colouring Sectors of a Circle.   « Reply #9 on: Dec 15th, 2004, 3:11pm » Quote Modify Yeah.  From what I tried, it works quite well for n=2, but for other values of n, it is not that efficient. IP Logged ThudnBlunder wu::riddles Moderator Uberpuzzler The dewdrop slides into the shining Sea     Gender: Posts: 4489 Re: Colouring Sectors of a Circle.   « Reply #10 on: Dec 15th, 2004, 11:23pm » Quote Modify on Dec 14th, 2004, 3:39am, Grimbal wrote: Damn.  I won't win the Mathematics Nobel prize, then....   Nor will anybody. There ain't one! (But there is an annual Fields medal.) It is rumoured that this is because a mathematician once demonstrated too well to Nobel's mistress an alternative meaning of the word 'root'.       « Last Edit: Dec 15th, 2004, 11:49pm by ThudnBlunder » IP Logged THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you. Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Colouring Sectors of a Circle.   « Reply #11 on: Dec 16th, 2004, 12:21am » Quote Modify It wasn't a square root I guess. IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Colouring Sectors of a Circle.   « Reply #12 on: Dec 16th, 2004, 3:02am » Quote Modify on Dec 15th, 2004, 11:23pm, THUDandBLUNDER wrote: It is rumoured that this is because a mathematician once demonstrated too well to Nobel's mistress an alternative meaning of the word 'root'. Which like all too many rumors isn't true. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Barukh Uberpuzzler     Gender: Posts: 2276 Re: Colouring Sectors of a Circle.   « Reply #13 on: Dec 16th, 2004, 3:44am » Quote Modify I think last T&B and Grimbal's posts belong to "what am i?" section. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board