bonanova Posted August 12, 2009 Report Share Posted August 12, 2009 You lay some white poker chips, all the same size, flat on the table so they touch only at their edges. Your friend wants to color them so that no two chips that touch [each other] will have the same color. What is the smallest number of chips you must place on the table to force the use of . 3 colors?4 colors?5 colors?. Note - all the chips are colored: none remain white. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 12, 2009 Report Share Posted August 12, 2009 You only ever need 3 colours, surely? Assuming you're arranging them in close packing layers. And the minimum number for that is 3. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 12, 2009 Report Share Posted August 12, 2009 (edited) . Edited August 12, 2009 by Steven136 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 12, 2009 Report Share Posted August 12, 2009 (edited) I was going to say 4 due to the Four-Color Theorem but I guess I'll assume the poker chips are circular in nature so only 3 colors are needed since 4 corners can not meet. Edited August 12, 2009 by Dempsey Collins Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 12, 2009 Report Share Posted August 12, 2009 (edited) After some thought I do think there can never be more than 3 colors. So you can not force the friend to use 4 or 5. Try it with pennies like I did. And the first poster should use spoiler next time, because I inadvertantly saw his answer. No fun. It should be edited so future viewers don't see the answer. Edited August 12, 2009 by Chewbacca Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 12, 2009 Report Share Posted August 12, 2009 (edited) I agree that if you must arrange all of the chips on the table before the coloring of the chips starts that you can only arrange them in such a way as to require at 3 different colors. However, if you are allowed to place a chip on the table and require that it be colored before placing the next chip, then it is possible to force your opponent to use a fourth color upon placement of the 5th chip. This can be done by placing the first three chips in a straight line. Then placing a fourth chip at the point at which two chips intersect, thus forcing the third color to be applied. Then place the fifth chip at the point intersecting the all of the first three colors. Edited August 12, 2009 by slowwitted Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 12, 2009 Report Share Posted August 12, 2009 But you cannot force 5 colors ever on a surface, 4 colors is enough You lay some white poker chips, all the same size, flat on the table so they touch only at their edges. Your friend wants to color them so that no two chips that touch [each other] will have the same color. What is the smallest number of chips you must place on the table to force the use of . 3 colors?4 colors?5 colors?. Note - all the chips are colored: none remain white. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 12, 2009 Report Share Posted August 12, 2009 I agree that if you must arrange all of the chips on the table before the coloring of the chips starts that you can only arrange them in such a way as to require at 3 different colors. However, if you are allowed to place a chip on the table and require that it be colored before placing the next chip, then it is possible to force your opponent to use a fourth color upon placement of the 5th chip. This can be done by placing the first three chips in a straight line. Then placing a fourth chip at the point at which two chips intersect, thus forcing the third color to be applied. Then place the fifth chip at the point intersecting the all of the first three colors. It only forces a 4th color if he used only 2 colors to begin with. If he used 3 colors to start, then you do not need a fourth color. Example: Put 3 chips in a row as you said and color them red, green, and blue. Add a fourth chip between the red and green and color it blue. Now add a fifth chip between the green and blue and touching the fourth chip and color it red. So you cannot force a fourth color -- it requires the other person to take a specific action first Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted August 12, 2009 Report Share Posted August 12, 2009 So, it looks like you can force 4... 3. 3 all touching. 4. My best solution has 19 poker chips currently. I may post a picture later if no one else comes up with a better solution (or posts a picture of my solution). 5. Impossible. As mentioned, it is essentially proven by the four color theorem even though it is not specific to coins. You can create a simple reduction by assuming you have a solution that forces 5 colors, letting the poker chips "bleed" and form a figure that has the same connectivity as the chips yet covers the surface (always possible, yet I won't prove it here), and then apply the four color theorem to show that it cannot exist. Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted August 12, 2009 Report Share Posted August 12, 2009 So, it looks like you can force 4... 3. 3 all touching. 4. My best solution has 19 poker chips currently. I may post a picture later if no one else comes up with a better solution (or posts a picture of my solution). 5. Impossible. As mentioned, it is essentially proven by the four color theorem even though it is not specific to coins. You can create a simple reduction by assuming you have a solution that forces 5 colors, letting the poker chips "bleed" and form a figure that has the same connectivity as the chips yet covers the surface (always possible, yet I won't prove it here), and then apply the four color theorem to show that it cannot exist. down to 16 for forcing 4 colors Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted August 12, 2009 Report Share Posted August 12, 2009 down to 11 for forcing 4 colors Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 13, 2009 Report Share Posted August 13, 2009 I retract my former post. here is what I found I cant seem to import the pic, but it is sort of a ring of (color1) touching (color2 and color3)touching (color 1) repeated and looped around until color 1 is forced to touch color 1, which cant happen thus forcing the 4th color. Gee it only took me all freaking day to think it through!!!! My brain hurts!!!!!!!!!!!!, it has 7 of each of the first 3 colors and it loops around forcing the 4th color where it connects at the ends. 22 chips in all. I think it is possible to reduce though. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 13, 2009 Report Share Posted August 13, 2009 You lay some white poker chips, all the same size, flat on the table so they touch only at their edges. Your friend wants to color them so that no two chips that touch [each other] will have the same color. What is the smallest number of chips you must place on the table to force the use of . 3 colors?4 colors?5 colors?. Note - all the chips are colored: none remain white. for three colors you need 3 chips. I think all the chips can be just painted with three colors to make sure that no two that touch have same color. so for 4 and 5 my answer is infinite. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 13, 2009 Report Share Posted August 13, 2009 3 chips are needed at least4 chips are needed at least5 chips are needed at least Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted August 14, 2009 Report Share Posted August 14, 2009 I retract my former post. here is what I found I cant seem to import the pic, but it is sort of a ring of (color1) touching (color2 and color3)touching (color 1) repeated and looped around until color 1 is forced to touch color 1, which cant happen thus forcing the 4th color. Gee it only took me all freaking day to think it through!!!! My brain hurts!!!!!!!!!!!!, it has 7 of each of the first 3 colors and it loops around forcing the 4th color where it connects at the ends. 22 chips in all. I think it is possible to reduce though. Exactly. If you take one section (one of each color) away you'll end up with my first posted solution. You can still remove quite a few more, but it requires a slight change in structure. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted August 14, 2009 Author Report Share Posted August 14, 2009 down to 11 for forcing 4 colors Bingo! Got a pic? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 14, 2009 Report Share Posted August 14, 2009 (edited) This is a 5 star puzzle in my book. I love it when I am soooo sure of something and then that idea just gets crushed by reality. Great job Bonanova! Here is my pic of the four color ring. I am sure it can be reduced by at least 3 while keeping the same basic configuration. I am still trying to think of the elusive 11 chip design. Edited August 14, 2009 by Chewbacca Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted August 16, 2009 Author Report Share Posted August 16, 2009 Chewbacca: thanks. Most replies correctly had 3 and infinity for the 3 and 5 color cases. has the lowest number of chips for 4 colors. To close this one out, is there a pic for the optimal 4-color case? Quote Link to comment Share on other sites More sharing options...
0 EventHorizon Posted August 17, 2009 Report Share Posted August 17, 2009 Chewbacca: thanks. Most replies correctly had 3 and infinity for the 3 and 5 color cases. has the lowest number of chips for 4 colors. To close this one out, is there a pic for the optimal 4-color case? Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted August 18, 2009 Author Report Share Posted August 18, 2009 Yup, that's the one I had. Quote Link to comment Share on other sites More sharing options...
Question
bonanova
You lay some white poker chips, all the same size, flat on the table so they touch only at their edges.
Your friend wants to color them so that no two chips that touch [each other] will have the same color.
What is the smallest number of chips you must place on the table to force the use of
.
.
Note - all the chips are colored: none remain white.
Link to comment
Share on other sites
19 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.