Author |
Topic: Equilateral triangle from pennies (Read 807 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
Following problem swiped from problem of the week by professor Delgado.
Take 15 pennies and put them in a triangle as shown in the figure. Must there always be three pennies, all three heads or all three tails, whose centers form an equilateral triangle?
(Note that the diagram just shows an example of which penny goes where, the Heads/Tails is arbitrary for the problem)
|
| « Last Edit: Nov 20th, 2004, 1:17am by Aryabhatta » |
 IP Logged |
|
|
|
Miles Teg
Newbie
Gender:
Posts: 11
|
 |
Re: Equilateral triangle from pennies
« Reply #1 on: Nov 20th, 2004, 2:08pm » |
 Quote  Modify
|
The answer is Yes.
proove :
lets denote the lines by letters (a,b,c,d,e)from top down
and the coins will be numbered on each row from left to right.
head -0 , tail -1
lets place at the top 0 and in the other 2 coners 1
so (a1,0) (e1,1)(e5,1)
lets also choose (b1,1) because or b1 or b2 must be 1
------------------------------------------------------
till now all the choises where simetric so it is ok to assume we start at this position.
(b1,1)&(e1,1)=>((e4,0)
now if we choose (e3,1)=>c1 and c3 are 0 and this makes triangle with a1 so
(e3,0)
(e3,0)&(e4,0)=>(d3,1)
------------------------
now if (e2,0)
(e2,0)&(e4,0)=>c(2,1)
and
(e2,0)&(e3,0)=>(d2,1)
so we have triangle (c3,d2,d3)
so it must be (e2,1)
(e2,1)&(e1,1)=>(d1,0)
(a1,0)&(d1,0)=>(d4,1)
(d3,1)&(d4,1)=>(c3,0)
(c3,0)&(a1,0)=>(c1,1)
(c1,1)&(b1,1)=>(c2,0)
(c2,0)&(c3,0)=>(b2,1)
and here we have a triangle of 1 (e2,e5,b2)
there was no way to avoid it .
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Equilateral triangle from pennies
« Reply #2 on: Nov 21st, 2004, 12:53pm » |
Quote Modify
|
Right Miles! Well done.
In fact you have proved the stronger statement, that no matter what, there will be an equilateral triangle, with sides parallel to the big triangle.
If we don't restrict the sides to be parallel to the big triangle, we can in fact prove that the first four rows itself (i.e 10 pennies) will contain an equilateral triangle.
Here is the proof I had in mind for the 15 pennies case. Of course, the proof for 10 pennies will work too for 15 pennies too...
We use X to represent the coins whose H/T nature we don't care about. H for heads, T for tail.
Notice that in the central triangle of side 1, we must have two of same kind, say Heads. i.e
X
X X
X X X
X H H X
X X X X X
This forces the following:
X
X X
X T X
X H H X
X X T X X
The two new tails force the following (this is where we use the assumption that triangle sides need not be parallel to the big one)
X
X X
X T X
H H H H
X X T X X
This forces:
X
X X
X T X
H H H H
X T T T X
which gives us an equilateral triangle of tails.
I guess the original intent for this problem was to prove that such a triangle exists with sides parallel to the outer triangle, because without that, 4 rows are enough.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Equilateral triangle from pennies
« Reply #3 on: Nov 22nd, 2004, 7:03am » |
Quote Modify
|
The non-parallel case (side-4):
::
.........X
......O M
...M X O
X O M X
The two triangles O and M each have to be either HHT or HTT. If you assume M is HHT:
.........X
......O T
...H X O
X O H X
Then if O is HTT you get either:
.........X
......T T
...H Q T
X H H X
or :
.........X
......H T
...H Q T
X T H X
Or with O as HHT:
.........X
......H T
...H Q T
X H H X
In each case, Q can be neither H nor T without forming a triangle. So O must also be HHT thus:
.........X
......H T
...H X H
X T H Z
In which case Z cannot be chosen.
::
[e]neatening diagrams[/e]
|
| « Last Edit: Nov 22nd, 2004, 7:07am by rmsgrey » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Equilateral triangle from pennies
« Reply #4 on: Nov 22nd, 2004, 10:25am » |
Quote Modify
|
Right rmsgrey!
Interestingly, any proof of this problem will prove the following (an old international math olympiad problem):
Colour each point of the 2D plane with one of two colours. Show that, no matter what the colouring, there will be 3 monchormatic points in the plane which form the vertices of an equilateral triangle.
This has been discussed before right here in this forum.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Equilateral triangle from pennies
« Reply #5 on: Nov 23rd, 2004, 5:56am » |
Quote Modify
|
Which is why I was able to answer so quickly - as I recall, 10 points is the (unproved) minimum needed to guarantee a monochrome equilateral triangle, though you only need consider 7 if you get to pick them as you go. My previous solution wasn't quite an equilateral triangle - one corner was missing and there was an additional point opposite where it should be, but I've since come up wth a solution for the side-4 equilateral triangle that only requires 7 questions...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Equilateral triangle from pennies
« Reply #6 on: Nov 23rd, 2004, 11:06am » |
Quote Modify
|
on Nov 23rd, 2004, 5:56am, rmsgrey wrote:| though you only need consider 7 if you get to pick them as you go. |
|
If you get to pick them up as you go, I would say the minimum is 3! Just pick the equilateral triangle, which you know will exist.
Maybe you are thinking in terms of a 2 player game?
I pick a point, then you pick a colour for that point and so on...
If that is the case, I know a solution for 8 (In fact my proof for 15 pennies uses that). Have to read the other thread completely to see your solution of 7.
I guess 10 is the 'unproven' minimum for the (harder for player 1) version in which Player1 picks all his points first and Player 2 next picks the colour for them.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Equilateral triangle from pennies
« Reply #7 on: Nov 24th, 2004, 6:28am » |
Quote Modify
|
on Nov 23rd, 2004, 11:06am, Aryabhatta wrote:
If you get to pick them up as you go, I would say the minimum is 3! Just pick the equilateral triangle, which you know will exist.
Maybe you are thinking in terms of a 2 player game?
I pick a point, then you pick a colour for that point and so on...
If that is the case, I know a solution for 8 (In fact my proof for 15 pennies uses that). Have to read the other thread completely to see your solution of 7.
I guess 10 is the 'unproven' minimum for the (harder for player 1) version in which Player1 picks all his points first and Player 2 next picks the colour for them.
|
|
The "pick them as you go" was meaning that you look at a point/coin, and then, based on its colour/orientation, pick your next point/coin to look at. You could do that either against a live adversary who colourspoints as you pick them, or against a concealed grid, whose points are revealed as you query them.
I haven't actually written up my solution for picking 7 points out of an equilateral triangle of side 4 - the other thread should have a solution for 7 points out of the plane though - I don't think anyone actually showed their solution for 10 points in the "pick all your points first, and then I colour them" version intheother thread, but this thread's triangle works...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Equilateral triangle from pennies
« Reply #8 on: Nov 24th, 2004, 11:11am » |
Quote Modify
|
on Nov 24th, 2004, 6:28am, rmsgrey wrote:
the other thread should have a solution for 7 points out of the plane though - |
|
I think we can do 6 for the plane if we play the pick as you go version...
Pick point A (0,0) and then point B (1,0).
Case 1)
If A and B are of the same colour (say Red):
pick C(2,0).
if C is also Red, by the midpoints construction we can get 6 points
Case 1.1) C is say Blue. Pick D (1/2, [sqrt]3/2) and E (-1/2, [sqrt]3/2). One of ABD, ABE and CDE is equilateral of same colour.
Case 2)
If A and B are of different colour.
Rescale co-ordinate system so that A is (0,0) and B is (2,0).
Now pick C(1,0). We are back to Case 1.1.
Quote:
as I recall, 10 points is the (unproved) minimum needed to guarantee a monochrome equilateral triangle,
|
|
I think it will remain unproven, as I think we can do 9!
Consider a regular hexagon ABCDEF, center G and points H and I as follows:
A B
F G C
E D I
H
Now if ABCDEF alternate between red and blue, ACE is a monochormatic equilateral triangle.
By Symmetry it is enough if we consider cases when AB are of same colour or when DE are of same colour and when BC are of same colour.
Case 1) Say we assume A and B are both Red. So G is blue.
Now if C is Red, E is blue (ACE), so F is Red (FGE) and so D is blue (FBD). GED is a blue triangle.
So C must be Blue. If C is blue, D is red (CGD). implying F is Blue (FBD). Implying E is Red (GEF). This implies H is red (HED). FCH is a blue triangle.
Case 2) Similar argument works if we assume D and E are of the same colour
Case 3) Similar arguments work I think.. (haven't worked out the details)
I think why it works is:
without considering H and I, the only arrangement which seems to not give a triangle for a hexagon is:
R R
B B B
R R
The way H and I are placed will make one of the H and I making either a blue or a red triangle.
|
| « Last Edit: Nov 24th, 2004, 11:27am by Aryabhatta » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Equilateral triangle from pennies
« Reply #9 on: Nov 26th, 2004, 6:16am » |
Quote Modify
|
Yep, that all seems to work, though it is possible (assuming I haven't missed anything) to get a worst-case 6-point solution in the 9-point universe you suggest:
...A...B
C...D...E
...F...G...H
......I
Start by saying E(1) is red, and looking at D(2).
1) D is also red: look at C(3).
1.1) C is also red: looking at F(4), G(5) and I(6) must produce a triangle (CDF,DEG,CEI,FGI)
1.2) C is blue: looking at B(4) and G(5) must produce a triangle (BCG,BDE,DEG)
2)D is blue: look at I(3).
2.1)I is red: look at F(4).
2.1.1)F is red: looking at A(5) and C(6) must produce a triangle (ACD,AEF,CEI)
2.1.2)F is blue: looking at C(5) must produce a triangle (CDF,CEI)
2.2)I is blue: look at F(4).
2.2.1)F is red: look at B(5).
2.2.1.1)B is red: looking at H(6) must produce a triangle (BFH,DHI)
2.2.1.2)B is blue: looking at A(6) must produce a triangle (ABD,AEF)
2.2.2)F is blue: looking at G(5) and H(6) must produce a triangle (DHI,EGH,DFG,FGI)
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Equilateral triangle from pennies
« Reply #10 on: Nov 26th, 2004, 1:07pm » |
Quote Modify
|
on Nov 26th, 2004, 6:16am, rmsgrey wrote:Yep, that all seems to work, though it is possible (assuming I haven't missed anything) to get a worst-case 6-point solution in the 9-point universe you suggest:
|
|
Yep, this seems to work too.
Also, I just read the other thread, looks like Grimbal had posted (waay back, in May 2004) a 9 point solution (identical to what I got) for the harder "I pick all, then you paint" version.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Equilateral triangle from pennies
« Reply #11 on: Nov 27th, 2004, 5:43am » |
Quote Modify
|
[note to self]Remember to check threads for second pages[/note] 
Still, at least we've now got an explicit solution rather than just a diagram (though trial and error is pretty convincing once you have a diagram...)
And it's even provable that you can't find a solution that only requires looking at 5 points - a 5 question solution would need two reds, two blues, and one final one. The first two points chosen (out of the entire plane) are entirely arbitrary, so they can be any combination of colours. If they're both red, then you need to pick the remaining three points so that if any of them are red, you get a triangle (otherwise you can have three red points not forming a triangle and two blue points also not forming a triangle). But there are only two points in the enire plane that form a triangle with the first two points chosen, so there aren't three points to choose...
Anyone want to try proving that 9 is/isn't the minimum size for a universe? We know 6 is a lower bound...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Equilateral triangle from pennies
« Reply #12 on: Nov 27th, 2004, 12:09pm » |
Quote Modify
|
on Nov 27th, 2004, 5:43am, rmsgrey wrote:
Anyone want to try proving that 9 is/isn't the minimum size for a universe? We know 6 is a lower bound... |
|
How about starting from 6 and trying to go up?
For 6 the following seems like an idea which might work.
With 6 points, looks like we can find no more than 5 equilateral triangles. So this looks similar to 5 equations, and 6 variables giving rise to a non-trivial solution i.e. we probably have enough room to make sure no monochromatic triangle exists.
|
| « Last Edit: Nov 27th, 2004, 12:10pm by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print