3 ms·

Just because you can't come up with a counterexample easily doesn't make it obvious or even true. Of course in this case it is indeed true, but I'm asking what

Just because you can't come up with a counterexample easily doesn't make it obvious or even true. Of course in this case it is indeed true, but I'm asking what makes it obvious

deleted 2y ago
[deleted]
deleted 2y ago
[deleted]
bongodongobob 2y ago
Because it's saying "you have 6 blocks, they can be either green or blue. No matter what colors they are, you'll always have either 3 blue or 3 green."
- yongjik 2y ago
  You misunderstood the problem. That's not what it's saying at all.
  - bongodongobob 2y ago
    How isn't it? There's no way to have 3 connected friends and 4 unconnected friends.
    - Dylan16807 2y ago
      You can have all 6 connected and still be in either category. For example, 6 friends in a loop can be divided into even and odd trios, where each trio has no direct friend connections within it. But six people in two separate triangles fall into the other category, with two trios of mutual friends. Notice how both of these cases give each person 2 friends. It's not nearly as simple as assigning everyone a color at the start. Another thing to think about: If you have a triangle of 3, and a line of 3, then you can find 3 mutual friends and three mutual non-friends. How would you use colors to differentiate this situation from the two-triangles situation?
      - bongodongobob 2y ago
        No, that's what I'm saying. You're either a member of the 3-group or you're not. It clearly requires 3 members, so...
        Dylan16807 2y ago
        It's proving the 3 nodes with no direct connections to each other that is the complicated part. It's not "you have a group of 3 or you don't". You can have all six people tangled up in lots of different combinations, so how do you prove there's a way to pick three that only connect indirectly?
    - drekipus 2y ago
      You could have one green and five blue
      - bongodongobob 2y ago
        Uh, exactly. You've got 3 blue in that 5.
        drekipus 2y ago
        Sorry I was thinking too fast
- michael_nielsen 2y ago
  Just so you know: you've completely misunderstood the statement.
- lcnPylGDnU4H9OF 2y ago
  I think it’s more accurate as: at least 3 which are blue or at least 3 which aren’t blue. Which is obvious even if perhaps the statement at the top of the thread is not.
  - michael_nielsen 2y ago
    You have not understood the statement.
    - lcnPylGDnU4H9OF 2y ago
      In that case, would you mind writing a more enlightening comment?
      - rcxdude 2y ago
        It's probably most clearly stated in the original post, but the point is you would either be able to find three people who are all friends with the other two, or you would be able to find three friends who are not friends with any of the others. The non-obviousness is due to the fact that someone may have only one friend, or someone may have two friends but those two would not be friends with each other, so I wouldn't call it blindingly obvious that there would always be a subset with one of these properties (I think the main intuition that is useful is that if you have a sparsely connected graph of friends, it's easy to find a group that aren't friends at all, and if you have a densely connected graph then you can find a group that are mutual friends. The theorem is then proving that there's no middle ground: it's either dense enough a mutual group must exist or sparse enough a non-friend group must exist.)
      - monktastic1 2y ago
        In your version, the color of a vertex is independent of other vertices. The real problem is about entirely about connections to other vertices. The latter cannot be reduced to the former.
      - shard 2y ago
        Does this formulation work? You have 6 wooden blocks, each can be 1 of 6 colors. There will always be either (A) 3 blocks of the same color, or (B) 3 blocks of different colors. Iterating through all possibilities: 6 of 1 color - case A 5 of 1 color, 1 of another - case A 4 of 1 color, 2 of another - case A 4 of 1 color, 1 of another, 1 of yet another - case A and B 3 of 1 color, 3 of another - case A 3 of 1 color, 2 of another, 1 of yet another - case A and B 3 of 1 color, 1 of another, 1 of yet another, 1 of another another - case A and B 2 of 1 color, 2 of another, 2 of yet another - case B 2 of 1 color, 2 of another, 1 of yet another, 1 of another another - case B 2 of 1 color, 1 of another, 1 of yet another, 1 of another another, 1 of another another another - case B all colors different - case B
- gweinberg 2y ago
  Let me see if I can clear up your misunderstanding: it is totally possible to have 5 people without having a group of 3 which are all friends nor a group of 3 none of which are friends. Draw a fully connected pentagon with all the outer edges one color and the inner edges another color. There is no triangle that is all the same color. But with 6 nodes you must have a triangle that is all the same color. It is the edges that are colored, not the nodes.

Just because you can't come up with a counterexample easily doesn't make it obvious or even true. Of course in this case it is indeed true, but I'm asking what makes it obvious

deleted 2y ago

[deleted]

deleted 2y ago

[deleted]

bongodongobob 2y ago

Because it's saying "you have 6 blocks, they can be either green or blue. No matter what colors they are, you'll always have either 3 blue or 3 green."

yongjik 2y ago
You misunderstood the problem. That's not what it's saying at all.
- bongodongobob 2y ago
  How isn't it? There's no way to have 3 connected friends and 4 unconnected friends.
  - Dylan16807 2y ago
    You can have all 6 connected and still be in either category. For example, 6 friends in a loop can be divided into even and odd trios, where each trio has no direct friend connections within it. But six people in two separate triangles fall into the other category, with two trios of mutual friends. Notice how both of these cases give each person 2 friends. It's not nearly as simple as assigning everyone a color at the start. Another thing to think about: If you have a triangle of 3, and a line of 3, then you can find 3 mutual friends and three mutual non-friends. How would you use colors to differentiate this situation from the two-triangles situation?
    - bongodongobob 2y ago
      No, that's what I'm saying. You're either a member of the 3-group or you're not. It clearly requires 3 members, so...
      - Dylan16807 2y ago
        It's proving the 3 nodes with no direct connections to each other that is the complicated part. It's not "you have a group of 3 or you don't". You can have all six people tangled up in lots of different combinations, so how do you prove there's a way to pick three that only connect indirectly?
  - drekipus 2y ago
    You could have one green and five blue
    - bongodongobob 2y ago
      Uh, exactly. You've got 3 blue in that 5.
      - drekipus 2y ago
        Sorry I was thinking too fast
michael_nielsen 2y ago
Just so you know: you've completely misunderstood the statement.
lcnPylGDnU4H9OF 2y ago
I think it’s more accurate as: at least 3 which are blue or at least 3 which aren’t blue. Which is obvious even if perhaps the statement at the top of the thread is not.
- michael_nielsen 2y ago
  You have not understood the statement.
  - lcnPylGDnU4H9OF 2y ago
    In that case, would you mind writing a more enlightening comment?
    - rcxdude 2y ago
      It's probably most clearly stated in the original post, but the point is you would either be able to find three people who are all friends with the other two, or you would be able to find three friends who are not friends with any of the others. The non-obviousness is due to the fact that someone may have only one friend, or someone may have two friends but those two would not be friends with each other, so I wouldn't call it blindingly obvious that there would always be a subset with one of these properties (I think the main intuition that is useful is that if you have a sparsely connected graph of friends, it's easy to find a group that aren't friends at all, and if you have a densely connected graph then you can find a group that are mutual friends. The theorem is then proving that there's no middle ground: it's either dense enough a mutual group must exist or sparse enough a non-friend group must exist.)
    - monktastic1 2y ago
      In your version, the color of a vertex is independent of other vertices. The real problem is about entirely about connections to other vertices. The latter cannot be reduced to the former.
    - shard 2y ago
      Does this formulation work? You have 6 wooden blocks, each can be 1 of 6 colors. There will always be either (A) 3 blocks of the same color, or (B) 3 blocks of different colors. Iterating through all possibilities: 6 of 1 color - case A 5 of 1 color, 1 of another - case A 4 of 1 color, 2 of another - case A 4 of 1 color, 1 of another, 1 of yet another - case A and B 3 of 1 color, 3 of another - case A 3 of 1 color, 2 of another, 1 of yet another - case A and B 3 of 1 color, 1 of another, 1 of yet another, 1 of another another - case A and B 2 of 1 color, 2 of another, 2 of yet another - case B 2 of 1 color, 2 of another, 1 of yet another, 1 of another another - case B 2 of 1 color, 1 of another, 1 of yet another, 1 of another another, 1 of another another another - case B all colors different - case B
gweinberg 2y ago
Let me see if I can clear up your misunderstanding: it is totally possible to have 5 people without having a group of 3 which are all friends nor a group of 3 none of which are friends. Draw a fully connected pentagon with all the outer edges one color and the inner edges another color. There is no triangle that is all the same color. But with 6 nodes you must have a triangle that is all the same color. It is the edges that are colored, not the nodes.