-
Notifications
You must be signed in to change notification settings - Fork 0
/
answer_key.tex
167 lines (102 loc) · 14.8 KB
/
answer_key.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
\documentclass[10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{graphicx}
\usepackage[export]{adjustbox}
\graphicspath{ {./images/} }
\title{FOCS Solution}
\author{}
\date{}
\textwidth 7.1in
\oddsidemargin -0.35in
\evensidemargin -0.3in
\textheight 8.7in
\topmargin -0.3in
\begin{document}
\maketitle
\textbf{Problem 1.1.} \\[0.05in]
The parity of an integer is 0 if it is even and 1 if it is odd. Which operations preserve parity:\\[0.05in]
(a) Multiplying by an even.\\[0.05in]
(b) Multiplying by an odd.\\[0.05in]
(c) Raising to a positive integer power.\\[0.05in]
\textbf{Solution}
(a). Multiplying by an even number doesn't preserves parity.\\[0.05in]
Explanation: Multiplying an even integer by an even number gives an even number like 4x2=8. \\[0.05in]
But it fails to produce odd number if we multiply an odd number by an even number like 3x2=6 is not odd.\\[0.05in]
(b). Multiplying by an odd number preserves parity. \\[0.05in]
Explanation: Multiplying any even integer by an odd number always gives an even number like 4x5=20.\\[0.05in]
Multiplying any odd integer by an odd number always gives an odd number like 3x5=15.\\[0.05in]
(c). Raising to a positive integer power preserves parity.\\[0.05in]
Explanation: Raising even number to any positive integer power always gives an even number like:\\[0.05in]
$2^1=2, 2^2=4, 2^5=32$\\[0.05in]
All of them are even.\\[0.05in]
Raising odd number to any positive integer power always gives an odd number like:\\[0.05in]
$3^1=3, 3^2=9, 3^5=243$\\[0.05in]
All of them are odd.\\[0.05in]
Hence correct choices are b and c .\\[0.05in]
-----------------------------------------------------------------------------------------------------------------------------------------------------------
Problem 1.2. What's wrong with this comparison: Google's nett worth in 2017, about $\$ 700$ billion, exceeds the GDP of many countries, e.g. Argentina's 2016-GDP was about $\$ 550$ billion. (Look up nett worth and GDP.)
Problem 1.3. Consider 2-contact EBOLA on a grid. You have one immunization vaccine. We show two different immunization scenarios, where you immunize the green square. Show the final infection in each case and determine which person you prefer to immunize? How many vaccines are needed to ensure that nobody else gets infected?
Problem 1.4. For the speed-dating problem with 16 people, $A, B, \ldots, P$ and four tables, arrange the rounds so that:
(a) In two rounds, everyone meets 6 people.
(c) In four rounds, everyone meets 12 people.
(b) In three rounds, everyone meets 9 people.
(d) In five rounds, everyone meets 15 people?
Problem 1.5 (Social Golfer Problem). 32 golfers form 8 groups of 4 each week. Each group plays a round of golf. No two golfers can be in the same group more than once. For how many weeks can this golfing activity go on?
(a) "Prove" that this golfing activity cannot go on for more than 10 weeks.
(b) Try to create a scheduling of players for as many weeks as you can. (10 is possible.)
(c) How is this problem related to the speed-dating problem?
In general you must schedule $g$ groups of golfers each of size $s$ for $w$ weeks so that no two golfers meet more than once in the same group. Given $(g, s, w)$, can it can be done and what is the schedule? This is a hard problem.
Problem 1.6. Students $A, \ldots, H$ form a friendship network (right). To advertise a new smartphone, you plan to give some students free samples. Here are two models for the spread of phone-adoption.
Model 1 (WEak Majority): People buy a phone if at least as many friends have the phone as don't. Model 2 (Strong Majority): People buy a phone if more friends have the phone than don't
(a) Use your intuition and determine the most "central" of the people in this friend-network.
(b) If you give a phone only to this central node, who ultimately has a phone in: (i) Model 1 (ii) Model 2?
(c) How many phones must you distribute, and to whom, so that everyone switches to your phone in Model 2?
(d) Repeat part (c), but now you cannot give a phone to the central node.
(A slight change to a model can have a drastic impact on the conclusions. A good model is important.)
Problem 1.7. Five radio stations (red stars) broadcast to different regions, as shown. The FCC assigns radio-frequencies to stations. Two radio stations with overlapping broadcast regions must use different radio-frequencies so that the common listners do not hear garbled nonsense. What is the minimum number of radio-frequencies the government needs?
Discrete math problems are like childhood puzzles. Parity, symmetry and invariance often yield simple solutions.
Problem 1.8. Two players take turns placing identical circular quarters on a circular table. Coins cannot overlap and must remain on the table. The last person to play wins. Do you want to go first or second? [Hint: symmetry.]
Problem 1.9. A chocolate-bar has 50 squares $(5 \times 10)$. How many breaks are necessary to break the bar into its 50 individual squares? You may only break a piece along a straight line from one side to the other. No stacking allowed. [Hint: Define the invariant $\Delta=$ \#pieces - \#breaks. What happens to $\Delta$ with each break?]
Problem 1.10. A single-elimination tournament has 57 players. Players may receive byes in some rounds. How many matches are played before a winner is declared? Does it depend on how the tournament is configured? [Hint: Define the invariant $\Delta=$ \#players remaining + \#matches played. What happens to $\Delta$ after a match?]
Problem 1.11. Five pirates must share 100 gold coins. The most senior pirate proposes a division of coins and all pirates vote. If at least half the pirates agree, the coins are divided as proposed. If not, the proposer is killed and the process continues with the next most senior pirate. A pirates priority is to stay alive, and then to get as much gold as possible. What should the senior pirate propose? [Hint: Sometimes it is better to start with a smaller problem.]
Problem 1.12. Can you color squares of a $9 \times 9$ grid blue or red so that every square has one opposite color neighbor (neighbors are left, right, up or down).
Problem 1.13. 57 security guards are positioned so that no two pairs of guards are the same distance apart. Every guard watches the guard closest to him. Is there an arrangement of the guards so that every guard is being watched?
Problem 1.14. 10 trucks each have 100 gallons of fuel and use 1 gallon of fuel per mile. How far can you deliver a chest that fits in one truck? (You can transfer the chest and/or fuel from truck to truck.)
Problem 1.15. A camel owner wants to sell his 300 bananas at a market 100 miles away. The camel can carry at most 100 bananas, but eats a banana for every mile travelled. How many bananas can be sold at the market?
Problem 1.16. Show that fewer than $n$ initial infections cannot infect the whole $n \times n$ grid in 2-contact EBOLA. [Hint: For a square, define 4-outgoing links $(N, S, E, W)$ to its 4 neighbors. Pretend boundary-squares have neighbors. For an infected square, remove all outgoing links to infected neighbors. Let $\Delta$, the "wavefront" of the infected area, be all remaining outgoing links for infected squares. Can $\Delta$ increase? What is $\Delta$ when all squares are infected?]
Problem 1.17 (Chomp). In the grid of chocolate, if you eat the top-left square, you lose. Each player takes turns to eat a square plus all the chocolate below it and to the right. We show a possible first move and the chocolate that removed in blue. Do you want to go first or second? [Hint: Either eating the bottom right piece wins or not. If not, what should you do?]
Problem 1.18. A man has a boat which can carry him and one other thing. How can the man get a fox, a chicken and a bag of corn across the river, if, when unattended, the fox eats the chicken and the chicken eats the corn.
Problem 1.19. Tasks involving covering an area using different shaped tiles are a treasure trove of interesting puzzles.
Problem 1.20. There are 13 purple, 15 red and 17 green chameleons. When chameleons of different colors meet they both transform to the third color. Will all 45 chameleons ever be the same color? [Hint: Consider $\Delta=\#$ purple-\#red.]
Problem 1.21. A building has 1000 floors. You wish to determine the highest floor from which you can drop an egg without the egg breaking. If you had 1000 identical eggs, you could drop one from each floor and see which eggs survive. How many egg drop trials do you need if you have: (a) One egg. $\quad$ (b) Two identical eggs.
Problem 1.22. Four boys take $1 \mathrm{~min}, 2 \mathrm{~min}, 7 \mathrm{~min}$ and $10 \mathrm{~min}$ to cross a bridge. The bridge only holds two boys at a time. It is dark and there is only one flashlight, which is needed to cross the bridge. Two boys cross at the speed of the slower boy who holds the flashlight. All four boys must get across the bridge. If the fastest boy acts as chauffeur for the other three, all four can cross in $21 \mathrm{~min}$. Can all four get across the bridge faster?
Problem 1.23. Two consecutive positive numbers $n$ and $n+1$ are given to you and a friend. One player gets $n$ and the other gets $n+1$, at random. You look at your number and shout out your opponents number if you know it, otherwise you pass the turn to your opponent. Will this game ever stop?
Problem 1.24. You have a gold chain with 63 links. You would like to cut some links to obtain a set of links of different sizes. You goal is to be able to represent any number of links from 1 to 63 as a collection of some of your pieces in order to trade. What is the minimum number of links you need to cut to be able to do so?
Problem 1.25. Three ants $a, b, c$ are on the vertices $A, B, C$ of a triangle. Each ant randomly picks one of the other vertices and walks to it. What are the chances that no ants colide on an edge or at a destination vertex)?
What if there are four ants $a, b, c, d$ on the vertices $A, B, C, D$ of a tetrahedron?
Problem 1.26. Two players alternately pick numbers without replacement from the set $\{1,2,3, \ldots, 9\}$. The first player to obtain three numbers that sum to 15 wins. What is your strategy?
Problem 1.27. A maharaja has 100 amphoras of wine. A traitor poisons one amphora, gets detected and killed. The poisoned amphora is not known and the poison kills in exactly one month. The maharaja uses tasters to tell if wine is safe, depending on whether the taster lives or dies after a month.
(a) The maharaja wants to safely drink wine in a month, what is the minimum number of tasters he needs.
(b) The maharaja wants to use all safe amphoras to throw an orgy in a month. What is the minimum number of tasters he needs. A simple solution is 100 tasters, one on each amphora. One can do much better though.
Problem 1.28. Two players take turns picking a coin from either end of a line of 20 coins. In the example below, if player 1 always takes from the left and player 2 from the right, then player 1's coins total 80 , and player 2's total is 146 .
\section*{(3) (7) (4) (19) (13) (2) (14) (7) (5) (6) (7) (11) (8) (2) (32) (47) (11) (6) (9) (13)}
The player with the highest total wins, player 2 in the example. Do you want to play first or second?
Problem 1.29. To weigh sugar, you have a comparison scale that can compare weights (illustrated). Give the fewest weights that are needed to measure out $1,2, \ldots, 121$ pounds of sugar.
For example, to measure 3 pounds of sugar with 2 and 5 pound weights, place the sugar and 2 pounds on the one side, and 5 pounds on the other side. The sugar weighs 3 pounds if the scale balances.
Problem 1.30. More than half of 99 processors are good and the rest are bad. You may ask a processor to evaluate another processor. A good processor always gives the correct answer and a bad one gives the wrong answer. How many times must you ask some (any) processor to evaluate another before you can identify a good processor?
Problem 1.31. A plane has fuel capacity to fly half way around the world. A plane can refuel from another plane in mid-air. All planes are at the airport. How many planes and tanks of gas do you need so that you can support a single plane to fly around the world? All planes must return to the airport.
Problem 1.32. 25 horses have different speeds. You can race up to 5 horses at a time and observe the order in which the horses finish. You have no stop-watch. Show that 7 races suffice to determine the fastest 3 horses.
Problem 1.33. 100 prisoners are up for a pardon. Prisoners will be lined in random order with a randomly chosen red or blue hat on each head. A prisoner sees only those ahead of them in the line. The last in line shouts the color of his hat. If he gets it right, he is pardoned. Then the second-last prisoner gets a chance and so on until the first in line.
The night before pardoning, the prisoners may strategize. During the pardoning process, the prisoners cannot communicate except to shout out a hat color. If the prisoners optimally strategize the night before, what are the chances that the first to shout is pardoned, the second to shout, the third to shout and so on up to the final prisoner?
Problem 1.34. At a puzzle-party with 32 guests, the host will shuffle a 52-card deck and paste a card on each guest's forhead. A guest will see every other guest's card but not their own card. After the cards are pasted on forheads, each guest, one by one, must shout out a card (e.g. 4\$.). At the end the number of guests who correctly shouted out their card is multiplied by $\$ 1,000$ to get a prize amount which is split evenly among all guests.
Intense discussion breaks out among the guests as they arrive. A philosopher suggests breaking into 16 pairs. In each pair, the first to shout says their partner's card so the partner can guess correctly. This strategy guarantees $\$ 16,000$. A FOCS-student claims, "I can guarantee we will share $\$ 31,000$." Can you come up with a strategy to guarantee $\$ 31,000$ ?
Problem 1.35. Three friends $A, B, C$ each have tokens $a, b, c$. At every step a random pair of friends is picked to swap whatever tokens they currently have. If the first pair picked is $(A, B)$ and then $(A, C)$ then the tokens are distributed $c, a, b$ after the two swaps. What are the chances each friend has their own token after 2015 swaps?
Problem 1.36. On a table are some red and blue cards. Two players take turns picking two cards. If the two cards picked are the same color, both cards are replaced by one red card. If the two cards picked are different colors, both cards are replaced by one blue card. When one card remains, you win if it is blue and your opponent wins if it is red.
(a) Must the game always end, or can it go on forever?
(b) Who wins if there are 8 blue and 11 red cards to start? Does it matter who goes first? [Hint: Parity invariant.]