Old Königsberg and its bridges
A compilation of my answers in Graph Theory class:
Question from Session 2: Two people perform a card trick. The first performer takes 5 cards from a 52-card deck (previously shuffled by a member of the audience), looks at them, keeps one of the cards and arranges the remaining four in a row from left to right, face up. The second performer guesses correctly the hidden card. Prove that the performers can agree on a system which always makes this possible, and devise one such system. Answer
Question from Session 3: Baron Münchhausen is very proud: "I chose a huge set of positive integers smaller than 2013, and yet among any four elements there are two such that one is divisible by the other." He went on boasting to his stupefied audience: "I bet no one could ever find such a set with more elements." However, the infamous storyteller was exaggerating again. The set he had found was rather small. Help him find a set that could save his honor. Answer
Question of Session 5: Dwellers of Flatplanet are hostile creatures. Their countries don't even share borders, but are well separated from each other. There are six countries in total, three of them are the Allies, and the other three are, not surprisingly, the Axis. For strategic reasons, each country is topologically connected. An embedded correspondent is informing us that the shortest distance from any of the Allies countries to any of the Axis countries is equal to 1 flatkilometer (a unit of length widely used on Flatplanet). Could she be right? Answer
Question from Session 7: There are 1900 one-Swiss-franc coins lying on an enormous table. Some of them might touch each other, but they don't overlap. Show that you can always choose 475 of them such that no two chosen coins touch each other. Can you always choose 601 such coins? Answer
Problem from Session 10: Prove that if mankind will live forever, then there is a woman alive today who will have a daughter who will have a daughter who will have a daughter... for eternity! Answer
