# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Wed, 22 May 2013 23:20:40 UTC

 All times are UTC [ DST ]

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

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 )

_________________
math puns are the first sine of madness
-JDR

Top

 Post subject: Re: red and blue points on a circlePosted: Wed, 4 Apr 2012 15:40:11 UTC
 Member of the 'S.O.S. Math' Hall of Fame

Joined: Sun, 24 Jul 2005 20:12:39 UTC
Posts: 3692
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

 Post subject: Re: red and blue points on a circlePosted: Wed, 4 Apr 2012 15:55:08 UTC
 Senior Member

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.

_________________
math puns are the first sine of madness
-JDR

Top

 Post subject: Re: red and blue points on a circlePosted: Wed, 4 Apr 2012 17:14:19 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6007
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 )

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

_________________

Top

 Post subject: Re: red and blue points on a circlePosted: Wed, 4 Apr 2012 18:46:53 UTC
 Senior Member

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

Top

 Post subject: Re: red and blue points on a circlePosted: Thu, 5 Apr 2012 01:38:28 UTC
 Senior Member

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

Top

 Post subject: Re: red and blue points on a circlePosted: Thu, 5 Apr 2012 01:43:54 UTC
 Moderator

Joined: Wed, 30 Mar 2005 04:25:14 UTC
Posts: 12102
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? 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

 Post subject: Re: red and blue points on a circlePosted: Thu, 5 Apr 2012 02:00:41 UTC
 Senior Member

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
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. 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

Top

 Post subject: Re: red and blue points on a circlePosted: Thu, 5 Apr 2012 05:24:26 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6007
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? 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?

_________________

Top

 Post subject: Re: red and blue points on a circlePosted: Thu, 5 Apr 2012 18:24:24 UTC
 Senior Member

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

Top

 Post subject: Re: red and blue points on a circlePosted: Thu, 12 Apr 2012 11:05:51 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6007
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?

_________________

Top

 Post subject: Re: red and blue points on a circlePosted: Mon, 16 Apr 2012 15:27:03 UTC
 Senior Member

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

Top

 Post subject: Re: red and blue points on a circlePosted: Sat, 19 May 2012 10:20:32 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6007
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)

Spoiler:
Let B be the function "multiply by 2 (or equivalently, -1)". Now R and B are functions satisfying , and I'll leave you to check the details.

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

_________________

Top

 Post subject: Re: red and blue points on a circlePosted: Mon, 21 May 2012 00:40:30 UTC
 Senior Member

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

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 satisfying , 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

Top

 Post subject: Re: red and blue points on a circlePosted: Mon, 21 May 2012 00:50:21 UTC
 Moderator

Joined: Wed, 30 Mar 2005 04:25:14 UTC
Posts: 12102
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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 19 posts ] Go to page 1, 2  Next

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

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

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous