Monday, November 21, 2016

Solutions
369 Smorgasbord
364 Paradox
339 Brad Pitt
338
337
336 Dick Cheney
335 Divine intervention
334
333 Jason Segel
332
331
330
329
328 Chamomile
327 I'll be damned
326 Raise the stakes
325 Emoji
324
323 Project runway
322 Pisces
321 Catastrophe
320 Season finale
319 I'll pencil you in
318 Illegal Aliens
317 Euthanasia
316 Safety in numbers
315 Scar face
314 Movers and Shakers
313 Wisconsin
312 Back to the drawing board
311 Red White and Blue
310 No chance in hell
309 Contact Solution
308 Mayonnaise
307 Tie Breaker
306 Alfalfa
305 Dodge Charger
304 George Washington
303 Overnight Delivery
302 World Series
301 HBO
300 Station Wagon
299 You'll be sorry
298 Settle a score
297 Meteor shower
296 Pigeon toed
295 Freaky Friday
294 Automatic Weapons
293 Third time's the charm
292 MTV
291 West Palm Beach
290 Long time no see
289 Amazeballs
288 Frankincense
287 USB port
286 Cover charge
285 Go for broke
284 Hedge Bets
283 Miley Cyrus
282 Hugh Grant
281 Ooze and Oz
280 Ponytail
279 Quiznos
278 Bartender
277 Yogi Bear
276 Little rock Arkansas
275 Jheri curl
274 Running behind schedule
273 Boulder Colorado
272 Polariod
271 Search Party
270 Page Turner
269 Run for office
268 Plot Twist
267 Bloomingdales
266 Twenty thousand leagues under the sea
265 Monologue
264 Range rover
263 Nestle quick
262 Pumpernickel
261 Baskin robbins
260 Spreadsheet
259 Austin Powers
258 Masturbate
257 Even Stevens
256 Tit for tat
255 Goalkeeper
254 Mixed Martial Arts
253 Butt dial
252 Dim Sum
251 Boarding school
250 German Engineering
249 Cher Crop
248 Steer clear
247 Vanity Fair
246 Pickup artist
245 Dane Cook
244 Pinky swear
243 Mix and match.
242 Ceiling fan
241 Sausage links
240 Cross dresser
239 Barnes and Nobles
238 Made in China
237 Taylor Swift
236 Hostle takeover
235 Instagram
234 Xbox
233 Porcupine
232 Bruno Mars
231 Pandora's box
230 50 cent
229 Dramatic pause
228 Make up for lost time
227 Goldie Hawn
226 General Mills
225
224
223
222
221
220
219
218
217
216
215
214
213
212
211
210
209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1




Sunday, November 16, 2014

Alternating T-Shirt Colors

This is a puzzle from Microsoft Research Page: "Ten friends walk into a room where each one of them receives a hat.  On each hat is written a real number; no two hats have the same number.  Each person can see the numbers written on his friends' hats, but cannot see his own.  The friends then go into individual rooms where they are each given the choice between a white T-shirt and a black T-shirt.  Wearing the respective T-shirts they selected, the friends gather again and are lined up in the order of their hat numbers.  The desired property is that the T-shirts colors now alternate.The friends are allowed to decide on a strategy before walking into the room with the hats, but they are not otherwise allowed to communicate with each other (except that they can see each other's hat numbers).  Design a strategy that lets the friends always end up with alternating T-shirt colors."

My solution is based on induction. 
Assume we have a numbered sequence 
1 2 3 4 5 6 7 8 ...
We may assign alternating ranks to to stand for the alternating colors for each number. 
1 0 1 0 1 0 1 0 ...

Now if we permutate 2 arbitrary numbers once with exactly the same rank, for example
1 2 7 4 5 6 3 8...

We can see any number beside the chosen 2 numbers will observe one permutation. For the 2 numbers themselves, because the chosen 2 numbers have the same rank, there were always odd number of digits between them (4, 5, 6) . Once the permutation happened, the numbers that are switched will be observing odd number of permutations. In conclusion,  the parity of the number of permutation will be preserved by an observation made by inside numbers and outside numbers alike.

Next if we permuate 2 arbitrary numbers of different ranks, for example
1 2 6 4 5 3 7 8

For an outside observer (those numbers which are not permutated), an odd number of permutation is observed, yet an even number of permutation is observed by the numbers which are permutated. We can extend this rule to multiple permutations of numbers of different ranks. In conclusion, the parity of the number of permutation will be preserved by an outsider's observation, and will be reverted by an insider's observation if its final position is in a different rank. 

Any other case can be reduced to the above 2 cases, for example
1 2 4 6 5 3 7 8 is a combination of 1 2 3  6 5 4 7 8 and then 1 2 4 6 5 3 7 8

Base on the above properties of permutations, we can conclude that the solution to the puzzle is: Each number observes the parity of the permutations. If it's odd then it switches its rank and if it's even then it retains its rank.