ES214. Discrete Mathematics. Tutorial 01 Quiz.
ES214. Discrete Mathematics
Tutorial 01
Imagine a friend gives you a deck of cards and lets you shuffle it a few times. They then ask vou to deal out the top 26 cards face down, which divides the deck into two.
You keep one half and they take the other. They ask you to count how many red cards you have. In the meantime, you notice that they are silently looking through their own half of the deck. But whatever they are doing they did it as quickly as you, because once you’re done they declare that they know how many red cards you counted, and correctly announce the answer!
How did they do it?
Deduce how the following trick works.
Mr. and Mrs. Sharma invited four couples to their home. Some guests were friends of Mr. Sharma, and some others were friends of Mrs. Sharma. When the guests arrived, people who knew each other beforehand shook hands, those who did not know each other just greeted each other.
After all this took place, the observant Mr. Sharma said “How interesting. If you disregard me, there are no two people present who shook hands the same number of times
How many times did Mrs. Sharma shake hands?
Alice begins by marking a corner square of an n × n chessboard; Bob marks an orthogonally adjacent square.
Thereafter, Alice and Bob continue alternating. each marking a square adjacent to the last one marked, until no unmarked adjacent square is available at which time the player whose turn it is to play loses.
For which n does Alice have a winning strategy? For which n does she win if the first square marked is instead a neighbor of a corner square?
Hint: dominoes.
You are at a party where any two people have an odd number of mutual friends at the party.
Show that there are an odd number of attendees.