wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Infinite B&W plane
        
(Message started by: BNC on Apr 29^th, 2004, 12:42pm)

Title: Infinite B&W plane
Post by BNC on Apr 29^th, 2004, 12:42pm

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 .

Title: Re: Infinite B&W plane
Post by rmsgrey on Apr 29^th, 2004, 1:24pm

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

Title: Re: Infinite B&W plane
Post by Noke Lieu on Apr 29^th, 2004, 7:32pm

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?

Title: Re: Infinite B&W plane
Post by BNC on Apr 29^th, 2004, 10:43pm

on 04/29/04 at 19:32:45, 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. [hide]all the calculations are finite; infinite plane is there to indicate unbounded area.[/hide]

Quote:

I assume the plane isn't definately uniformly distributed bwbwbw like a chess board?

It wounldn't be interesting then.. ;)

Title: Re: Infinite B&W plane
Post by Noke Lieu on Apr 29^th, 2004, 11:00pm

That means the points are uniformly distributed- other wise it would be very easy. Actually, no it doesn't- a unit-cell of [hide]
.w.b
w.b.[/hide]
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.

Title: Re: Infinite B&W plane
Post by TenaliRaman on May 1^st, 2004, 4:34am

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

Title: Re: Infinite B&W plane
Post by Icarus on May 1^st, 2004, 7:08am

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.

Title: Re: Infinite B&W plane
Post by BNC on May 1^st, 2004, 7:42am

hint: [hide](2) can be solved using the result from (1), and considering only 6 points.[/hide]::

Title: Re: Infinite B&W plane
Post by towr on May 1^st, 2004, 9:33am

on 05/01/04 at 04:34:07, TenaliRaman 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..

Title: Re: Infinite B&W plane
Post by rmsgrey on May 2^nd, 2004, 6:52am

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 ::[hide]9 and 15[/hide]:: respectively. The arrangements are again left unstated.

Title: Re: Infinite B&W plane
Post by rmsgrey on May 2^nd, 2004, 7:04am

Some hints/preliminary results for the original problems:

::[hide]
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.
[/hide]::
::[hide]
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.
[/hide]::

Title: Re: Infinite B&W plane
Post by BNC on May 2^nd, 2004, 8:11am

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 [hide]9[/hide] for (1), so I guess it's the right question[/e]

Title: Re: Infinite B&W plane
Post by TenaliRaman on May 2^nd, 2004, 11:06pm

on 05/01/04 at 07:08:13, Icarus wrote:

Thanks Icarus!

on 05/01/04 at 09:33:13, 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.

Title: Re: Infinite B&W plane
Post by Sameer on May 3^rd, 2004, 7:10am

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.

Title: Re: Infinite B&W plane
Post by BNC on May 3^rd, 2004, 10:13am

on 05/03/04 at 07:10:55, 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.

Title: Re: Infinite B&W plane
Post by yadayada on May 3^rd, 2004, 1:43pm

Here is one way to solve the midpoint problem

[hide]
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.

[/hide]

Title: Re: Infinite B&W plane
Post by TenaliRaman on May 4^th, 2004, 2:23am

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

Title: Re: Infinite B&W plane
Post by Barukh on May 4^th, 2004, 9:04am

on 05/04/04 at 02:23:46, TenaliRaman wrote:

yadayada,
i did hit that particular contradiction earlier but i think the assumptions seem faulty.

Yadayada's assumptions are perfectly correct: [hide]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)[/hide].

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 [hide]define a coordinate system on them[/hide]. If you prove it's possible, than this argument is as sound as yadayada's.

Title: Re: Infinite B&W plane
Post by rmsgrey on May 4^th, 2004, 9:17am

yadayada's construction is easily fixed - instead of saying "... we can assume that ..." say "... we can define our co-ordinate system so that ..."

::[hide]
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...
[/hide]::

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]

Title: Re: Infinite B&W plane
Post by TenaliRaman on May 4^th, 2004, 11:22am

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.

Title: Re: Infinite B&W plane
Post by towr on May 4^th, 2004, 12:22pm

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

Title: Re: Infinite B&W plane
Post by Icarus on May 4^th, 2004, 4:45pm

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?

Title: Re: Infinite B&W plane
Post by TenaliRaman on May 5^th, 2004, 3:35am

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)

Title: Re: Infinite B&W plane
Post by rmsgrey on May 5^th, 2004, 8:17am

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]

Title: Re: Infinite B&W plane
Post by TenaliRaman on May 5^th, 2004, 9:02am

yeehaw! me too! i removed 2 redundant points from my diagram.But 10 pts is the limit and i think it is the optimal.

Title: Re: Infinite B&W plane
Post by grimbal on May 22^nd, 2004, 5:43pm

for the triangle, 7 points:[hide]a b c d e f g
Suppose you can not find a triangle.
Choose b and c black. A and e must be white. Aed is a triangle, d must be black. from cdf, f must be white.
Now, from bdg, g must be white, but from efg, g must be black.
[/hide]

Title: Re: Infinite B&W plane
Post by rmsgrey on May 24^th, 2004, 5:20am

Yep, that's the exact construction I used for the triangle (down to rotation - interestingly, we had the same handedness)

So does anyone want to post explicit solutions to my extension problems?

Title: Re: Infinite B&W plane
Post by TenaliRaman on May 24^th, 2004, 10:28am

on 05/24/04 at 05:20:41, rmsgrey wrote:

So does anyone want to post explicit solutions to my extension problems?

for triangle,
[hide]
a b c
d e f g
h i j
[/hide]

for the midpoint one,
it should fairly obvious as it directly follows the original 5 point solution. hint:[hide]try to eliminate the assumption made in the 5 point solution(specifically the solution given by icarus)[/hide]

Title: Re: Infinite B&W plane
Post by grimbal on May 24^th, 2004, 12:03pm

I understand now what the extension is about.

Here is my set of points for extension 1. 9 points also
[hide] a-b-cdefg-h-i
Within c,e,g there are 2 points of the same color. If for example it is c and e, you have b-cde-g. c,e black => b,g white => d is impossible.
[/hide]
Here is my set of points for extension 2. 9 points.[hide]a b c d e f g h i[/hide]