S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Sun, 19 May 2013 08:50:49 UTC

View unanswered posts | View active topics


Board index » High School and College Mathematics » Proposed Problems

All times are UTC [ DST ]



Post new topic Reply to topic  Page 1 of 2
  [ 19 posts ]  Go to page 1, 2  Next
  Print view Previous topic | Next topic 
Author Message
rdj5933mile5math64
 Post subject: red and blue points on a circle
PostPosted: Wed, 4 Apr 2012 15:27:24 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
I tried using a search function and I wasn't able to find anything.~

Question:
We have red and blue points on a circle. We can do any one of 2 things.

1. We can add a red point between any two existing points that are next to each other and change the color of the original points.

2. We can remove a red point and change the color of the 2 points next to it (there need to be two points next to the red point we are removing).


Prove that if there are initially 2 red points and no blue points on the circle, then we cannot get 2 blue points and no red points on the circle.

Mathematical Background:
Invariants, monovariants, injections bijections, generating functions.... (other olympiad level combinatorics stuff that I might have forgot :P )

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
Denis
 Post subject: Re: red and blue points on a circle
PostPosted: Wed, 4 Apr 2012 15:40:11 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Sun, 24 Jul 2005 20:12:39 UTC
Posts: 3688
Location: Ottawa Ontario
rdj5933mile5math64 wrote:
We have red and blue points on a circle.
.......
Prove that if there are initially 2 red points and no blue points on the circle...


You say there are blue points, then you say no blue points ?

_________________
I'm not prejudiced...I hate everybody equally!
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: red and blue points on a circle
PostPosted: Wed, 4 Apr 2012 15:55:08 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
Denis wrote:
You say there are blue points, then you say no blue points ?


Sorry my wording was a little ambiguous. My first statement that you quoted was just to give a background of the problem. Like to establish that all points we put on a circle are either red or blue (for example we can't have green points) and that all of the points are on a circle.

To give a more direct answer to your question: we start with no blue points on the circle.

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
outermeasure
 Post subject: Re: red and blue points on a circle
PostPosted: Wed, 4 Apr 2012 17:14:19 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6004
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
rdj5933mile5math64 wrote:
I tried using a search function and I wasn't able to find anything.~

Question:
We have red and blue points on a circle. We can do any one of 2 things.

1. We can add a red point between any two existing points that are next to each other and change the color of the original points.

2. We can remove a red point and change the color of the 2 points next to it (there need to be two points next to the red point we are removing).


Prove that if there are initially 2 red points and no blue points on the circle, then we cannot get 2 blue points and no red points on the circle.

Mathematical Background:
Invariants, monovariants, injections bijections, generating functions.... (other olympiad level combinatorics stuff that I might have forgot :P )


Am I understanding the first move correctly? You probably mean only those two selected points have their colour changed, not (as written) every point on the circle prior to insertion of your red point? So adding a red point and removing it shouldn't change anything, rather than flipping the colour of all points except 2 consecutive ones.

Not really a hint, but a pre-hint:
Spoiler:
There is a (reasonably natural) way to choose a (pseudo-)representative of what you can get from any starting position.


Another hint, this time for real:
Spoiler:
the equivalence between RRR and BB suggests you play with mod 3, where R stands for +1 and B stands for ...

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: red and blue points on a circle
PostPosted: Wed, 4 Apr 2012 18:46:53 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
outermeasure wrote:
I don't think so. (Am I understanding the first move correctly? You probably mean only those two selected points have their colour changed, not every point on the circle prior to insertion of your red point?)

That's correct :) . For example, we could have something like:
Spoiler:
rr
bbr
rrrr
rrbrb


outermeasure wrote:
Spoiler:
There is a (reasonably natural) way to choose a (pseudo-)representative of what you can get from any starting position.



Hmmm I'm sort of new to this website so to be safe I'll hide stuff.
Spoiler:
Looked up pseudo. hmmmmm ignoring what I said earlier about mathematical background sorry :( . We can make an equivalence relation of the set of all configurations, C. So if we let x,y be elements in C then x~y iff we can make "moves" on x to get to configuration y. So, at this point, I was thinking ok now what can I do. By taking a few examples, I thought C should be partitioned into different subsets then we can think about using the canonical form of each subset, which is just the configuration with the smallest points. But, that wasn't working as well as I'd hoped it might. Seeing as this was an old olympiad problem, the approach that I'm trying to use can't be right.


outermeasure wrote:
Spoiler:
Create "devices" that act on your representative.



Spoiler:
I'm assuming "devices"=invariants/monovariants.

So my thoughts
I was like hmmm what "matters"?
well
rrbb =/= rbrb - the relative position of the numbers matter.
bbr=brb=rbb - rotations shouldn't matter ( <--- led me to think: complex numbers)
but I couldn't get anywhere here :/
I'd really like to see a nice invariant/monovariant proof :mrgreen:
hmmm I've been trying a lot of somewhat contrived invariants but nothing has worked so far...

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: red and blue points on a circle
PostPosted: Thu, 5 Apr 2012 01:38:28 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
Sorry for double posting :( I don't know why I can't edit :?

outermeasure wrote:
Another hint, this time for real:
Spoiler:
the equivalence between RRR and BB suggests you play with mod 3, where R stands for +1 and B stands for ...


Spoiler:
... you're hinting B=-1. Why? :confused: Neither addition nor multiplication work since under both circumstances they don't account for RRBB being distinct from RBRB. These two configurations are very different seeing as RR ->RBB -> RRBB and BB ->RRR -> RBRB.


EDIT: Grammar Error

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
Shadow
 Post subject: Re: red and blue points on a circle
PostPosted: Thu, 5 Apr 2012 01:43:54 UTC 
Online
Moderator
User avatar

Joined: Wed, 30 Mar 2005 04:25:14 UTC
Posts: 12075
Location: Austin, TX
rdj5933mile5math64 wrote:
Sorry for double posting :( I don't know why I can't edit :?

outermeasure wrote:
Another hint, this time for real:
Spoiler:
the equivalence between RRR and BB suggests you play with mod 3, where R stands for +1 and B stands for ...


Spoiler:
... you're hinting B=-1. Why? :confused: Neither addition nor multiplication work since under both circumstances they don't account for RRBB being distinct from RBRB. These two configurations are very different seeing as RR ->RBB -> RRBB and BB ->RRR -> RBRB.


EDIT: Grammar Error


You don't have to hide everything. outermeasure used the spoiler tags because the hints make the problem markedly easier, and it's the only way to make it so you can get a little bit of help at a time rather than all of it all at once.

Also, you cannot edit after the first minute or so of posting, so if you have a grammar error which is nonessential, just let it be.

_________________
(\ /)
(O.o)
(> <)
This is Bunny. Copy Bunny into your signature to help him on his way to world domination
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: red and blue points on a circle
PostPosted: Thu, 5 Apr 2012 02:00:41 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
Shadow wrote:
You don't have to hide everything. outermeasure used the spoiler tags because the hints make the problem markedly easier, and it's the only way to make it so you can get a little bit of help at a time rather than all of it all at once.

Also, you cannot edit after the first minute or so of posting, so if you have a grammar error which is nonessential, just let it be.


Oh lol the point of the post you quoted wasn't for a quick grammar fix. :P I was addressing a point that outermeasure had made (looking at the R's and B's using mod's) which I must have missed earlier. I then edited the post because there was a small typo.

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
outermeasure
 Post subject: Re: red and blue points on a circle
PostPosted: Thu, 5 Apr 2012 05:24:26 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6004
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
rdj5933mile5math64 wrote:
Sorry for double posting :( I don't know why I can't edit :?

outermeasure wrote:
Another hint, this time for real:
Spoiler:
the equivalence between RRR and BB suggests you play with mod 3, where R stands for +1 and B stands for ...


Spoiler:
... you're hinting B=-1. Why? :confused: Neither addition nor multiplication work since under both circumstances they don't account for RRBB being distinct from RBRB. These two configurations are very different seeing as RR ->RBB -> RRBB and BB ->RRR -> RBRB.


EDIT: Grammar Error


No, that's not what I am hinting at. Indeed you need something that distinguishes RBRB from RRBB, and that is easy to get hold of if you look at it the right way.

By the way, you can (mostly) forget about the representative part. I just put it there to motivate why my real hint of using mod 3 and assigning R to +1 is a good idea (and the "device" thing to simplify your representative, which you can actually ignore for this exercise but a good idea to keep in mind). By the way, that is a hint:
Spoiler:
Why did I use +1 instead of 1?

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: red and blue points on a circle
PostPosted: Thu, 5 Apr 2012 18:24:24 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
outermeasure wrote:
I just put it there to motivate why my real hint of using mod 3 and assigning R to +1 is a good idea. By the way, that is a hint:
Spoiler:
Why did I use +1 instead of 1?


My (Wrong) Reasoning:
I thought that the +1 was used instead of the 1 to emphasize using B=-1 mod 3. My reasoning was that if B=R=1 mod 3, then BB is equivalent to AA so that wouldn't work. Since 1 is the multiplicative identity I thought that you were multiplying things together. As a result, B=0 mod 3 wouldn't work. Process of elimination left me with B=-1 mod 3.

I still don't know how to figure out exactly what to do with the mod 3.

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
outermeasure
 Post subject: Re: red and blue points on a circle
PostPosted: Thu, 12 Apr 2012 11:05:51 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6004
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
It has been a week (ok, minus 8 hours or so), and evidently my subtle hint didn't work terribly well..

It is very hard to give any more hint(s) without giving the entire solution away, so here is a big spoiler:
Spoiler:
Let R be the function "add 1". What is a good candidate for the function B?

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: red and blue points on a circle
PostPosted: Mon, 16 Apr 2012 15:27:03 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
outermeasure wrote:
It has been a week (ok, minus 8 hours or so), and evidently my subtle hint didn't work terribly well..

It is very hard to give any more hint(s) without giving the entire solution away, so here is a big spoiler:
Spoiler:
Let R be the function "add 1". What is a good candidate for the function B?


Darn the hint still isn't helping. I know it's really tough to give a hint to a problem like this since it's either you get it or you don't, but nothing has "clicked" yet.

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
outermeasure
 Post subject: Re: red and blue points on a circle
PostPosted: Sat, 19 May 2012 10:20:32 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6004
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
Hmm... forgot about this thread, hence the late reply.

Spoiler:
Let B be the function "multiply by 2 (or equivalently, -1)". Now R and B are functions \mathbb{Z}/3\mathbb{Z}\to\mathbb{Z}/3\mathbb{Z} satisfying R^3=B^2=\mathop{\mathrm{id}}, and I'll leave you to check the details.


Spoiler:
You don't need the full invariance. You just need ...

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: red and blue points on a circle
PostPosted: Mon, 21 May 2012 00:40:30 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
This solution is awesome! Thanks, outermeasure! :D

I've been really busy studying for finals, ACT classes, and ARML (I'm too fond of the the first 2~), so I'm sorry for the late reply.

outermeasure wrote:
Spoiler:
Let B be the function "multiply by 2 (or equivalently, -1)". Now R and B are functions \mathbb{Z}/3\mathbb{Z}\to\mathbb{Z}/3\mathbb{Z} satisfying R^3=B^2=\mathop{\mathrm{id}}, and I'll leave you to check the details.



Could you tell me what your motivation was to add 1 for R and multiply by -1 for B?

outermeasure wrote:
Spoiler:
You don't need the full invariance. You just need ...


This comment threw me off a little. I'm probably misinterpreting your hint, but how would a monovariant work here?

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
Shadow
 Post subject: Re: red and blue points on a circle
PostPosted: Mon, 21 May 2012 00:50:21 UTC 
Online
Moderator
User avatar

Joined: Wed, 30 Mar 2005 04:25:14 UTC
Posts: 12075
Location: Austin, TX
As an internet culture FYI, you don't need to give excuses as to why you're not responding immediately, it's not expected of you to do so, or even at all, especially on a problem you posed on a site dedicated mostly to homework things, hence there is no real major importance attached to the problem, it's just there for recreation, and so you're not shackled to it to such a degree. :)

_________________
(\ /)
(O.o)
(> <)
This is Bunny. Copy Bunny into your signature to help him on his way to world domination
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 2
  [ 19 posts ]  Go to page 1, 2  Next

Board index » High School and College Mathematics » Proposed Problems

All times are UTC [ DST ]

Who is online

Users browsing this forum: No registered users

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA