I hope these have been fun problems. I've had several in my head from when I first heard them, but I'm starting to look around for more - hopefully I can keep finding interesting ones to solve that don't require lots of background knowledge. Again, if anyone else has any to share, please do.
Here's a new problem. Let's see if it gets solved before the weekend is over or not.
You have a complete graph on 6 vertices (graph where all vertices are connected to each other) like below
Each edge can be colored either red or blue.
Show that regardless of the coloring, you can always find 3 edges that form a triangle that will have its edges all the same color.
No takers on this one?
The proof is pretty (imho):
Spoiler!
Pick any vertex. We'll choose vertex 1 in the diagram.
Vertex 1 has five attached edges. Because we are coloring the edges either red or black, we are guaranteed to have at least 3 colors the same color.
Each edge is identical to every other edge, so without loss of generality, we can say that edge 1-3, 1-4, and 1-5 are red.
If 3-5 is red, we are done (triangle 1-3-5 is red)
If 3-4 is red, we are done (triangle 1-3-4 is red)
If 4-5 is red, we are done (triangle 1-4-5 is red)
If 3-5, 3-4, and 4-5 are not red, then they must all be blue. But that means triangle 3-4-5 is blue and we are done.
Ok, new puzzle. This one is a pretty cool one I remember from my high school math teacher.
You have 100 coins on a table, with 50 heads, 50 tails. You are blindfolded and must divide the coins into two groups of 50 such that each group will have the same number of heads/tails.
The coins are each encased in plastic so you can't tell whether a coin is heads or tails by touch.
Ok, new puzzle. This one is a pretty cool one I remember from my high school math teacher.
You have 100 coins on a table, with 50 heads, 50 tails. You are blindfolded and must divide the coins into two groups of 50 such that each group will have the same number of heads/tails.
The coins are each encased in plastic so you can't tell whether a coin is heads or tails by touch.
Ok, new puzzle. This one is a pretty cool one I remember from my high school math teacher.
You have 100 coins on a table, with 50 heads, 50 tails. You are blindfolded and must divide the coins into two groups of 50 such that each group will have the same number of heads/tails.
The coins are each encased in plastic so you can't tell whether a coin is heads or tails by touch.
How do you do this?
To confirm this isn’t a cheesy answer like each coin has a head and a tail therefore I split them into to piles of 50 correct?
We know that we can take only two actions - split into groups and flip groups
We know that we can do each of these actions once because doing more won’t gain us info
We know we need two groups of 50 so the first split into two groups of 50 and the flip one of the groups. These are the only actions we can take therefore it should be correct.
Testing it So if we have 50 heads and split into two groups of 50. One group say has 40 heads and 10 tails and the other group then has 10 heads and 40 tails we flip one and you get 10 tails and 40 heads in each groups. It works because you don’t care the number of heads or tails just that they are equal. So it’s just x heads and 50-x tails in one pile and x tails and 50-x heads so flip and they match no matter what split the coins are.
Ok, new puzzle. This one is a pretty cool one I remember from my high school math teacher.
You have 100 coins on a table, with 50 heads, 50 tails. You are blindfolded and must divide the coins into two groups of 50 such that each group will have the same number of heads/tails.
The coins are each encased in plastic so you can't tell whether a coin is heads or tails by touch.
How do you do this?
Not sure if GGG already gave this answer as I didn't look at his, but here goes...
Spoiler!
Click for solution:
Spoiler!
Just put 50 in one group, 50 in the other. Flip all the coins of one group. Done.
(However, if by the question you meant each group must have exactly 25 heads & 25 tails, then I don't know.)
If that is the answer, then I'd call it a trick question that relies on fooling people with ambiguous wording
I did think about that after I posted, but I still don't think it's a trick question. It is worded to say exactly what it is supposed to say and I don't know how to word the question differently without it being a hint.
And we have two winners on this one! Great work to both of you.
Spoiler!
GGG provided the proof of why the method works so I won't reproduce it here. That said, I just want to say I really enjoyed GGG's process in solving it: you can only do these two operations. Let's do them and see if it works. Ok, it works, now let's come up with the proof after the fact.
It's such a great example of how an engineer approaches a problem vs. a mathematician!
Quote:
Originally Posted by GGG
Spoiler!
We know that we can take only two actions - split into groups and flip groups
We know that we can do each of these actions once because doing more won’t gain us info
We know we need two groups of 50 so the first split into two groups of 50 and the flip one of the groups. These are the only actions we can take therefore it should be correct.
Testing it So if we have 50 heads and split into two groups of 50. One group say has 40 heads and 10 tails and the other group then has 10 heads and 40 tails we flip one and you get 10 tails and 40 heads in each groups. It works because you don’t care the number of heads or tails just that they are equal. So it’s just x heads and 50-x tails in one pile and x tails and 50-x heads so flip and they match no matter what split the coins are.
That’s neat.
Quote:
Originally Posted by Mathgod
Not sure if GGG already gave this answer as I didn't look at his, but here goes...
Spoiler!
Click for solution:
Spoiler!
Just put 50 in one group, 50 in the other. Flip all the coins of one group. Done.
(However, if by the question you meant each group must have exactly 25 heads & 25 tails, then I don't know.)
You have the same setup - 100 coins encased in plastic, you are blindfolded. Only this time, there are 10 tails. Can you divide the coins into two groups so that they each have the same number of tails?
And now, generalizing: What if there are n tails at the start. Can you always divide the coins into two groups so that they have the same number of tails?
Location: In my office, at the Ministry of Awesome!
Exp:
Quote:
Originally Posted by psyang
A quick follow up to the last one.
You have the same setup - 100 coins encased in plastic, you are blindfolded. Only this time, there are 10 tails. Can you divide the coins into two groups so that they each have the same number of tails?
And now, generalizing: What if there are n tails at the start. Can you always divide the coins into two groups so that they have the same number of tails?
Spoiler!
You only need the same number of Tails (not heads & tails that is the important bit).
If the number of Tails in the original group is T then you put the coins into 2 groups.
Group 1:
# of coins: T
# of Tails (Call this TG1)= x
# of heads (Call this HG1) = T-x
Group 2:
# of coins: 100 (or whatever # of coins you started with) - T
# of Tails (call this TG2): T-x (this matters)
# of Heads: (100-T) - (T-x) = 100-2T+X - This doesn't really matter
Now flip all the coins in Group 1 the number of heads and tails swap values.
TG1 now equals T-x
HG1 now equals x
So now we have
TG1 = T-x = TG2
__________________
THE SHANTZ WILL RISE AGAIN.
<-----Check the Badge bitches. You want some Awesome, you come to me!
Bring_Back_Shantz is the winner - congrats! For the bonus point, you should have mentioned that n (or x in your solution) needs to be even, otherwise it is impossible.
Spoiler!
So for the first question, divide the groups into 10 and 90, and flip the group of 10.
For n tails (where n is even), divide into n and 100-n and flip the n group.
Quote:
Originally Posted by Bring_Back_Shantz
Spoiler!
You only need the same number of Tails (not heads & tails that is the important bit).
If the number of Tails in the original group is T then you put the coins into 2 groups.
Group 1:
# of coins: T
# of Tails (Call this TG1)= x
# of heads (Call this HG1) = T-x
Group 2:
# of coins: 100 (or whatever # of coins you started with) - T
# of Tails (call this TG2): T-x (this matters)
# of Heads: (100-T) - (T-x) = 100-2T+X - This doesn't really matter
Now flip all the coins in Group 1 the number of heads and tails swap values.
TG1 now equals T-x
HG1 now equals x
Ok, one more coin question (for now). This one might be tricky, we'll see. The solution is very elegant.
You have 100 perfectly round and identical quarters on a rectangular table arranged such that none of them overlap (ie. all quarters are flat on the table) and it is impossible to add another quarter to the table without requiring an overlap.
Show that you can always cover the table completely with 400 coins (where, by "cover", I mean that for every point on the table, there is at least one coin directly above it). Obviously, the covering would allow for overlaps.
Location: In my office, at the Ministry of Awesome!
Exp:
Quote:
Originally Posted by psyang
Bring_Back_Shantz is the winner - congrats! For the bonus point, you should have mentioned that n (or x in your solution) needs to be even, otherwise it is impossible.
Spoiler!
So for the first question, divide the groups into 10 and 90, and flip the group of 10.
For n tails (where n is even), divide into n and 100-n and flip the n group.
I assume you mean "T" in my solution.
As in the starting number of tails in the total group.
But that's not correct, it can definitely be odd.
Look at the extreme example where n = 1 (1 starting tail)
Group 1 will be 1 coin.
Group 2 will be 99 coins.
There are 2 possibilities
1:
Group 1 = 1 tail
Group 2 = 99 heads
Flip over the coin in group 1
Group 1 = 1 head = 0 tails
Group 2 = 99 heads = 0 tails
2:
Group 1 = 1 Head
Group 2 = 1 tail, 98 heads
Flip over the coin in group 1
Group 1 - 1 tail
Group 2 = 1 tail, 98 heads
Works just fine for an odd number.
__________________
THE SHANTZ WILL RISE AGAIN.
<-----Check the Badge bitches. You want some Awesome, you come to me!
I assume you mean "T" in my solution.
As in the starting number of tails in the total group.
But that's not correct, it can definitely be odd.
Look at the extreme example where n = 1 (1 starting tail)
Group 1 will be 1 coin.
Group 2 will be 99 coins.
There are 2 possibilities
1:
Group 1 = 1 tail
Group 2 = 99 heads
Flip over the coin in group 1
Group 1 = 1 head = 0 tails
Group 2 = 99 heads = 0 tails
2:
Group 1 = 1 Head
Group 2 = 1 tail, 98 heads
Flip over the coin in group 1
Group 1 - 1 tail
Group 2 = 1 tail, 98 heads
Works just fine for an odd number.
Ha ha, you are right. I don't know what I was thinking! Well, I do know what I was thinking but it was obviously wrong. Thanks for the correction!
Ok, one more coin question (for now). This one might be tricky, we'll see. The solution is very elegant.
You have 100 perfectly round and identical quarters on a rectangular table arranged such that none of them overlap (ie. all quarters are flat on the table) and it is impossible to add another quarter to the table without requiring an overlap.
Show that you can always cover the table completely with 400 coins (where, by "cover", I mean that for every point on the table, there is at least one coin directly above it). Obviously, the covering would allow for overlaps.
Spoiler!
The table is 100 identical squares of side length D the diameter of the coins.
You have 4 coins per square. If you line them up such that each coin has a diameter on the edge of the square it covers the whole square because a semi circle is concave out (more than the isosceles triangle that would exactly cover)
The table is 100 identical squares of side length D the diameter of the coins.
You have 4 coins per square. If you line them up such that each coin has a diameter on the edge of the square it covers the whole square because a semi circle is concave out (more than the isosceles triangle that would exactly cover)
Then do the same for all the other squares.
Hmm. Not quite.
Spoiler!
You will have to prove that every table for which you can arrange a maximum of 100 coins without overlapping is smaller than or equal to your 100 square table (which I don't think is the case).
What you've proven is that there exists a table for which 400 coins will cover given the initial conditions. But the problem is about any rectangular table that satisfies the initial conditions.
For example, I think it would be possible to arrange a maximum 100 coins non-overlapped on a table composed of 100 squares of side length D+k where D is the diameter of the coin, and k is an infinitely small value.
In such a table, the initial conditions would still be satisfied, but your procedure would not work as there would be an infinitely small uncovered area in the center of each square.
Let r be the radius of the coin. The dimensions of the table can be larger than x coins wide and y coins long, so the area of the table is larger than x*2r*y*2r = 4xyr^2
However, since the coins are close enough to prevent any more coins from fitting between them, the total area must be smaller than 2x*2r*2y*2r = 16xyr^2
Furthermore, the coins must also be close enough to prevent any coin from fitting in the two-dimensional spaces between coins on the table. As a consequence, the centres of the coins must not be farther apart than 2sqrt(2)r. This means that the total area of the table must be smaller than x*2sqrt(2)r*y*2sqrt(2)r = 8xyr^2
Now place coins, starting at the top left corner, exactly 2r apart, in a grid pattern, then a 2nd layer precisely positioned to cover the gaps left by the first layer. All area is covered, and the non-overlapping area that each coin contributes is r^2/2*4 = 2r^2. Since there are 4xy total coins, the total area covered is 8xyr^2
The solution isn't quite that simple, as it doesn't quite explain what happens on the sides and on the corners, but that's the gist of it.
I think it's a great start but not a valid solution. Comments/questions below in blue:
Quote:
Originally Posted by Mathgod
Spoiler!
Click for solution:
Spoiler!
Let r be the radius of the coin. The dimensions of the table can be larger than x coins wide and y coins long, so the area of the table is larger than x*2r*y*2r = 4xyr^2
However, since the coins are close enough to prevent any more coins from fitting between them, the total area must be smaller than 2x*2r*2y*2r = 16xyr^2
Can you clarify how you get 2x*2r*2y*2r as a bounding area for the table? I'm not seeing where that is coming from.
Furthermore, the coins must also be close enough to prevent any coin from fitting in the two-dimensional spaces between coins on the table. As a consequence, the centres of the coins must not be farther apart than 2sqrt(2)r.
Here, you are assuming the coins are packed in a grid, but that's not necessarily the case. What if you created a grid but added an infinitely small space between touching coins (ie. space between two coins in x direction and two coins in y direction). You still couldn't place a coin in the space in between the 4 coins, but the centers of the diagonal coins would be more than 2sqrt(2)r apart.
This means that the total area of the table must be smaller than x*2sqrt(2)r*y*2sqrt(2)r = 8xyr^2
Now place coins, starting at the top left corner, exactly 2r apart, in a grid pattern, then a 2nd layer precisely positioned to cover the gaps left by the first layer. All area is covered, and the non-overlapping area that each coin contributes is r^2/2*4 = 2r^2. Since there are 4xy total coins, the total area covered is 8xyr^2
The solution isn't quite that simple, as it doesn't quite explain what happens on the sides and on the corners, but that's the gist of it.