Author |
Topic: Infinite B&W plane (Read 1103 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
Infinite B&W plane
« on: Apr 29th, 2004, 12:42pm » |
 Quote  Modify
|
A plane is painted in two colors, such that each point is painted either black or white.
Prove it always possible to find:
(1) Three points of the same colors, one of which is at the exact middle of the segment connecting the other two;
(2) Three points of the same color, forming an equilateral triangle .
|
|
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Infinite B&W plane
« Reply #1 on: Apr 29th, 2004, 1:24pm » |
Quote Modify
|
I've managed to solve both of them - the line by considering 5 points, and the triangle 7. I'll hold off on actually posting the constructions for a while so others can have a go...
|
|
IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: Infinite B&W plane
« Reply #2 on: Apr 29th, 2004, 7:32pm » |
Quote Modify
|
Only a fledgling at infinities, so excuse me.
I think I thought the same thought as rmsgrey. But now I don't know.
I assume the plane isn't definately uniformly distributed bwbwbw like a chess board?
|
|
IP Logged |
a shade of wit and the art of farce.
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Infinite B&W plane
« Reply #3 on: Apr 29th, 2004, 10:43pm » |
Quote Modify
|
on Apr 29th, 2004, 7:32pm, Noke Lieu wrote:Only a fledgling at infinities, so excuse me.
|
|
Don't worry about it. You don't have to work with infinities here. all the calculations are finite; infinite plane is there to indicate unbounded area.
Quote:
I assume the plane isn't definately uniformly distributed bwbwbw like a chess board?
|
|
It wounldn't be interesting then.. 
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: Infinite B&W plane
« Reply #4 on: Apr 29th, 2004, 11:00pm » |
Quote Modify
|
That means the points are uniformly distributed- other wise it would be very easy. Actually, no it doesn't- a unit-cell of
.w.b
w.b.
would do it. And that's pretty obvious to see. Okay- am with you now.
So any random distribution of points, labelled W or B will make it work. Ahh. Much more interesting, you're right.
|
| « Last Edit: Apr 29th, 2004, 11:02pm by Noke Lieu » |
IP Logged |
a shade of wit and the art of farce.
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Infinite B&W plane
« Reply #5 on: May 1st, 2004, 4:34am » |
Quote Modify
|
how does one get to the solution?
i can think of cases to consider
1>entire plane of one color ... conditions proved
2>distributed coloring
now here comes the problem i cannot think of breaking it down further??
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Infinite B&W plane
« Reply #6 on: May 1st, 2004, 7:08am » |
Quote Modify
|
The trick is to find arrangements of a finite number of points such that no matter how these points are colored, there must be a subset of them that satisfies the condition. Note that rmsgrey says he solved (1) by considering an arrangement of 5 points, and (2) by an arrangement of 7 points.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Infinite B&W plane
« Reply #7 on: May 1st, 2004, 7:42am » |
Quote Modify
|
hint: (2) can be solved using the result from (1), and considering only 6 points.::
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Infinite B&W plane
« Reply #8 on: May 1st, 2004, 9:33am » |
Quote Modify
|
on May 1st, 2004, 4:34am, TenaliRaman wrote:how does one get to the solution?
i can think of cases to consider
1>entire plane of one color ... conditions proved
2>distributed coloring
now here comes the problem i cannot think of breaking it down further??
|
|
I can think of other cases. Like,
A finite number of black points.
Or all black points on a hyperbolic curve.
The results will differ for different distributions..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Infinite B&W plane
« Reply #9 on: May 2nd, 2004, 6:52am » |
Quote Modify
|
BNC: While using the result of the first part reduces the number of points needed for the second, proving the first part as part of the proof of the second requires more than 7 points. Anyway, I think the trick in the 7 point construction is much more interesting...
As an extension, if, instead of having the entire plane (or any finite region of it) entirely painted, instead you can specify in advance a finite number of points to be painted either black or white, what's the minimum number of points (and in what arrangement) required so that you can guarantee:
1) At least one point lies precisely midway between two others of its colour.
2) Three points of the same colour form an equilateral triangle.
I have answers of ::9 and 15:: respectively. The arrangements are again left unstated.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Infinite B&W plane
« Reply #10 on: May 2nd, 2004, 7:04am » |
Quote Modify
|
Some hints/preliminary results for the original problems:
::
If there is any finite convex area all one single colour, then it's always possible to pick a finite line segment and an equilateral triangle that lie entirely within that region and so both parts of the original problem become trivial.
::
::
Rather than proving that all possible arrangements of points must satisfy each condition, it's probably easier to show that there is no possible arrangement that falsifies either condition. This can be done by trying to construct an arrangement that doesn't satisfy one or other condition, and showing that you can't.
::
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Infinite B&W plane
« Reply #11 on: May 2nd, 2004, 8:11am » |
Quote Modify
|
rmsgrey,
A clarification regarding your extension:
Are you allowed to state a specific arrangement of N points, and just the colors are random?
[e] Got 9 for (1), so I guess it's the right question[/e]
|
| « Last Edit: May 2nd, 2004, 8:19am by BNC » |
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Infinite B&W plane
« Reply #12 on: May 2nd, 2004, 11:06pm » |
Quote Modify
|
on May 1st, 2004, 7:08am, Icarus wrote:| The trick is to find arrangements of a finite number of points such that no matter how these points are colored, there must be a subset of them that satisfies the condition. Note that rmsgrey says he solved (1) by considering an arrangement of 5 points, and (2) by an arrangement of 7 points. |
|
Thanks Icarus!
on May 1st, 2004, 9:33am, towr wrote:I can think of other cases. Like,
A finite number of black points.
Or all black points on a hyperbolic curve.
The results will differ for different distributions.. |
|
That's exactly the dilemma i had. But now cleared.
----------------------------------------------------------
I have managed to solve #2 by using 5 points. But i have not yet managed to solve #1. 
I am looking deeply into rmsgrey's hints but i am not sure if i understand that. Any pointers would be helpful.
|
| « Last Edit: May 2nd, 2004, 11:10pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Infinite B&W plane
« Reply #13 on: May 3rd, 2004, 7:10am » |
Quote Modify
|
This looks harder to me as I may lack some basic knowledge about something.
Just one question. Are we looking for a gernal method that would work for any distribution? From rmsgrey's hint it definitely feels like it, but just want to confirm.
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Infinite B&W plane
« Reply #14 on: May 3rd, 2004, 10:13am » |
Quote Modify
|
on May 3rd, 2004, 7:10am, Sameer wrote:This looks harder to me as I may lack some basic knowledge about something.
|
|
No special knowledge is required, only logic, and the "a-ha" moment.
Quote:
Just one question. Are we looking for a gernal method that would work for any distribution? From rmsgrey's hint it definitely feels like it, but just want to confirm. |
|
Yes, indeed.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
yadayada
Guest
|
Here is one way to solve the midpoint problem
First assume that there is no line whose midpoint is same colour as the vertices. Now,
Consider points (-1,0), (0,0) and (1,0). We can assume that (-1,0) and (1,0) are both Black. Then (0,0) is white.
Consider (-3,0). Must be White. similarly (3,0). This implies (0,0) must be black. Contradiction.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Infinite B&W plane
« Reply #16 on: May 4th, 2004, 2:23am » |
Quote Modify
|
yadayada,
i did hit that particular contradiction earlier but i think the assumptions seem faulty.
I think its equivalent to saying,
consider a rhombus with two opposite vertices colored black and other two opposite vertices colored white.The intersection of the diagonals will be black or white.QED.
Don't you think the assumptions are unfair??
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Infinite B&W plane
« Reply #17 on: May 4th, 2004, 9:04am » |
Quote Modify
|
on May 4th, 2004, 2:23am, TenaliRaman wrote:yadayada,
i did hit that particular contradiction earlier but i think the assumptions seem faulty. |
|
Yadayada's assumptions are perfectly correct: you can always pick 2 points of the same color and build a coordinate system on them (i.e. say their coordinates will be (-1, 0) and (1, 0).
Quote:I think its equivalent to saying,
consider a rhombus with two opposite vertices colored black and other two opposite vertices colored white.The intersection of the diagonals will be black or white.QED.
Don't you think the assumptions are unfair?? |
|
That's something different: it’s not immediately obvious you can choose that many specific points to define a coordinate system on them. If you prove it's possible, than this argument is as sound as yadayada's.
|
| « Last Edit: May 4th, 2004, 9:04am by Barukh » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Infinite B&W plane
« Reply #18 on: May 4th, 2004, 9:17am » |
Quote Modify
|
yadayada's construction is easily fixed - instead of saying "... we can assume that ..." say "... we can define our co-ordinate system so that ..."
::
If you don't want to assume that there are (at least) two black points in the plane, pick two points of the same colour, call that colour "Fred" and rewrite the proof replacing "black" and "white" with "Fred" and "Barney" respectively...
::
And for the requested clarification: yes, you are allowed to specify the specific points to be painted (though not the colour of each!  ) not just the number of them. In fact, you can find an arrangement of any number of points so that no three of them even lie on the same straight line (eg the edge of a circle), or so that no three form an equilateral triangle (eg a straight line), so you need the arrangement of points to be specified for ti even to be possible.
[e]Barukh posted faster... [/e]
|
| « Last Edit: May 4th, 2004, 9:18am by rmsgrey » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Infinite B&W plane
« Reply #19 on: May 4th, 2004, 11:22am » |
Quote Modify
|
Thx for the replies!
however my point was not that yadayada's construction was wrong but the assumptions he made in between.
i have no problems in assuming two points which are of the same color but my argument is that "this" is the limit of assumptions and that any more assumptions made after this would yield nothing.
To clarify what i am trying to say , lets go along yadayada's construction,
1>take two points which are of same color (perfectly valid system)
2>midpoint not of same color (perfectly valid assumption)
3>suppose there is -3,0 and 3,0 of the white color then contradiction...(here is where i have my problem ... i can distribute the whites such that no pair of white point has 0,0 as the midpoint) obviously such a distribution doesn't help much to contradiction proof.
sorry if the above is unclear and feels absurd.any comments or criticism on the above post is warmly welcomed.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Infinite B&W plane
« Reply #20 on: May 4th, 2004, 12:22pm » |
Quote Modify
|
If those points weren't white, you'd allready have a contradiction earlier.. because
(-1,0) , (1,0) and (3,0) would be black
or (-3,0) , (-1,0) and (1,0) would be black
Thus (3,0) , (0,0) and (3,0) must be white, and you get a contradiction anyway
|
| « Last Edit: May 4th, 2004, 12:27pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Infinite B&W plane
« Reply #21 on: May 4th, 2004, 4:45pm » |
Quote Modify
|
For clarity, let me recast yadayada's argument:
Out of any three points, 2 must be of the same color, so let B and D be two such points and let C be the midpoint between them. Let A and E be the points for which B is the mid point of AD and D is the midpoint of BE. It follows that C is also the mid point of AE.
By our choice, B and D are both the same color (call it 1 and the other color 2).
If A is of color 1, then A,B,D form the desired triple.
Assume A is of color 2.
If E is of color 1, then B, D, E form the desired triple.
Assume E is of color 2.
If C is of color 1, then B, C, D form the desired triple.
If C is of color 2, then A, C, E form the desired triple.
Therefore in all cases, three of A, B, C, D, E must be equally spaced points of the same color.
Does that make the argument a little clearer?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Infinite B&W plane
« Reply #22 on: May 5th, 2004, 3:35am » |
Quote Modify
|
Thanks towr and Icarus!
(i feel so dumb right now  )
========================================
I have also solved rmsgrey's extension problems (which are quite easy once u solve the original problems nonetheless they were still pretty nice extensions),
the first one i did with 9 points
the second i finished with 12 points
(if i have my drawings correct hopefully)
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Infinite B&W plane
« Reply #23 on: May 5th, 2004, 8:17am » |
Quote Modify
|
I'm curious about your 12 point solution to the second part of my extension. I got 15 points easily enough, and assumed that was optimal. If there's a 12 point construction, I'd like to know what I missed...
[e]OK, just had a brainwave and got it down to 10...[/e]
|
| « Last Edit: May 5th, 2004, 8:22am by rmsgrey » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Infinite B&W plane
« Reply #24 on: May 5th, 2004, 9:02am » |
Quote Modify
|
yeehaw! me too! i removed 2 redundant points from my diagram.But 10 pts is the limit and i think it is the optimal.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove