Thread Rating:

Poll

21 votes (45.65%)
14 votes (30.43%)
6 votes (13.04%)
3 votes (6.52%)
12 votes (26.08%)
3 votes (6.52%)
6 votes (13.04%)
5 votes (10.86%)
12 votes (26.08%)
10 votes (21.73%)

46 members have voted

ThatDonGuy
ThatDonGuy
  • Threads: 118
  • Posts: 6414
Joined: Jun 22, 2011
June 10th, 2024 at 5:45:05 PM permalink
Quote: djtehch34t

Quote: ThatDonGuy

Here's a new problem - bad news: it's a "proof" problem.

Interplanetary Express serves 65 different locations throughout the solar system. Every pair of locations is served by a route that is one of four colors - red, blue, green, or yellow. It turns out that, given any three locations, the three routes that connect them to each other are not all the same color.

Somebody wants to add a 66th location, with routes to each of the other 65, and maintaining the "no single-color triangles" policy.
Prove that this is impossible.

(Hint: the fact that you can with 65 is irrelevant; in fact, I am not entirely sure that such a mapping exists.)
link to original post


Assume we have a graph that satisfies the condition (call this 4-colorable). Take the 66th vertex and look at its edges. The color C1 that has the maximum number of edges must have at least ceiling(65/4) = 17 edges. Look at the subgraph with the vertices we get from those edges. This must not have any edges with C1 (aka be 3-colorable), or else we get a cycle with color C1.

Pick an arbitrary vertex in the subgraph of size 17 and repeat the argument. Color C2 must have ceiling(16/3) = 6 edges. So, this creates a 2-colorable subgraph of size 6. Repeat the argument once more to get a 1-colorable subgraph of size ceiling(5/2) = 3. But, this is a contraction, as that's the same as a cycle of the same color.

link to original post



Exactly.


Call the three paths that connect three locations to each other a "red triangle" if they are all red; similarly for any other color.
Choose a location; call it Location A.
There are 65 paths from A to the other locations. If there were only 16 of each color, that would be only 64 paths; therefore, there must be at least one color with 17 paths from A. Let's assume it is red.
If any of the paths between any of the 17 locations are also red, then those two locations and A form a red triangle; therefore, they can only be blue, green, or yellow.
Choose one of these 17 locations; call it Location B.
There are 16 paths from B to the other locations of these 17; if there were only 5 of each color, that would be only 15 paths, so there must be at least one color with 6 paths from B to the other 16 locations. Let's assume it is blue.
If any of the paths between any of the 6 locations are also blue, then those two locations and B form a blue triangle; therefore, they can only be green or yellow.
Choose one of these 6 locations; call it Location C.
There are 5 paths from C to these five locations; if there were only 2 of each color, that would be only 4 paths, so there must be at least one color with 3 paths from C to these 5 locations. Let's assume it is green, and let CD, CE, and CF all be green.
If DE is green, then CDE is a green triangle; if DF is green, then CDF is a green triangle; if CEF is green, then CEF is a green triangle; if none of them are green, then DEF is a yellow triangle.

For those of you interested in such things, the principle that, if you have N items and each is one of K types, then there must be at least N/K rounded up items of at least one type is called the Pigeonhole Principle (because you are trying to put N pigeons into K pigeonholes).

Wizard
Administrator
Wizard
  • Threads: 1496
  • Posts: 26626
Joined: Oct 14, 2009
June 10th, 2024 at 7:58:22 PM permalink
To reply to all posts since my puzzle on the 13 cards, I can't give anyone credit for a proper answer yet.

To clarify, yes, both players may look at their cards.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Mental
Mental
  • Threads: 13
  • Posts: 1381
Joined: Dec 10, 2018
June 11th, 2024 at 4:37:04 AM permalink
Quote: Wizard

To reply to all posts since my puzzle on the 13 cards, I can't give anyone credit for a proper answer yet.

To clarify, yes, both players may look at their cards.
link to original post

Either you simply don't like the form of my answer or there is something missing from your description.

There are 13*12 ways the cards can be chosen. L1 wins 78 of these matchups and L2 wins the other 78 when no exchange is ever offered. If L1 offers to exchange any card but a deuce, L2 will always accept if L2 is holding a deuce. L2 can sit pat in any other situation. This will give L2 an advantage in what was otherwise a fair game. So, L1 can only offer to exchange when holding a deuce. There is no way for L1 to force L2 into a disadvantage and vice versa.

Since L2 should be able to deduce all of this, L1 knows it is futile to offer to exchange any other card but a deuce to a logical opponent. The logical opponent will always refuse any exchange unless they are holding a deuce.

Am I missing something?
This forum is more enjoyable after I learned how to use the 'Block this user' button.
Wizard
Administrator
Wizard
  • Threads: 1496
  • Posts: 26626
Joined: Oct 14, 2009
Thanked by
Mental
June 11th, 2024 at 6:08:17 AM permalink
Quote: Mental

Either you simply don't like the form of my answer or there is something missing from your description.
link to original post



Sorry, I missed your answer. Credit given for being correct.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1496
  • Posts: 26626
Joined: Oct 14, 2009
June 14th, 2024 at 1:47:39 PM permalink


The red figure is a square. If you extend its sides, they cross the x-axis at points 5, 7, 12, and 17.

What is the area of the square?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
chevy
chevy
  • Threads: 3
  • Posts: 148
Joined: Apr 15, 2011
June 14th, 2024 at 1:58:43 PM permalink

the triangle hitting 7 & 12 is 3-4-5

So right side (from square to 12) is 4
The triangle hitting 5&12 is similar,
so side from (leftmost) square corner to 12 is. 7*(4/5) = 5.6

So side of square is 5.6-4 = 1.6

Area = 2.56


Hmmm

Same method for triangle hitting 7&17
Side is 10*(3/5)=6
side of square is 6-3 = 3

area = 9


I am going something wrong



Never mind…. Doesn’t have to be 3-4-5 triangle

Will look at it further

chevy
chevy
  • Threads: 3
  • Posts: 148
Joined: Apr 15, 2011
June 14th, 2024 at 2:41:28 PM permalink


Similar triangles…y is side of square

7&12 to 7&17

X/5= (x+y)/10…..x=y

5&12to 5&17

Z/7 = (z+y)//12….z=7y/5


Small triangle x^2 + z^2 = 5^2

Y^2 + (49/25* y^2) =25

Wrong again

Trying to do on phone is not helping


……..

Need

Z^2 + (y+(sqrt (25-x^2))^2 = 7^2

Sub in z and x from above…. Solve with paper and pen….. later

Areas of square =Y^2= __________

ThatDonGuy
ThatDonGuy
  • Threads: 118
  • Posts: 6414
Joined: Jun 22, 2011
June 14th, 2024 at 3:27:40 PM permalink

Note that the lines touching x = 5 and x = 7 are parallel, and the lines touching x = 12 and x = 17 are parallel, so the four triangles that are visible are all similar.

Let x be the length of the side of the square, a the distance from the square to (5,0), and b the distance from the square to (17,0)

(12 - 5) / a = (17 - 5) / (a + x) => 7 a + 7 x = 12 a => a = 7/5 x
(17 - 7) / b = (17 - 5) / (b + x) => 10 b + 10 x = 12 b => b = 5 x
Pythagorean Theorem: (a + x)^2 + (b + x)^2 = (17 - 5)^2
(12/5 x)^2 + (6 x)^2 = 144
1044/25 x^2 = 144
x^2 = 144 * 25 / 1044 = 100 / 29
Since x is a side of the square, the area is x^2, or 100 / 29

Wizard
Administrator
Wizard
  • Threads: 1496
  • Posts: 26626
Joined: Oct 14, 2009
June 14th, 2024 at 7:15:52 PM permalink
Quote: ThatDonGuy


Note that the lines touching x = 5 and x = 7 are parallel, and the lines touching x = 12 and x = 17 are parallel, so the four triangles that are visible are all similar.

Let x be the length of the side of the square, a the distance from the square to (5,0), and b the distance from the square to (17,0)

(12 - 5) / a = (17 - 5) / (a + x) => 7 a + 7 x = 12 a => a = 7/5 x
(17 - 7) / b = (17 - 5) / (b + x) => 10 b + 10 x = 12 b => b = 5 x
Pythagorean Theorem: (a + x)^2 + (b + x)^2 = (17 - 5)^2
(12/5 x)^2 + (6 x)^2 = 144
1044/25 x^2 = 144
x^2 = 144 * 25 / 1044 = 100 / 29
Since x is a side of the square, the area is x^2, or 100 / 29


link to original post



I agree!
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
  • Jump to: