For every integer n between 1 and 10100 (inclusive), take the product of the non-zero digits of n. Then find the sum of these 10100 products. What is the last digit (i.e., the one’s digit) of this sum?
Alice, Bob, and Charlie are all put in a room together. Each person has a hat –
either black or white, chosen at random – placed on their head. Each person can see the color of the others’ hats, but not their own. Alice, Bob, and Charlie are then placed in separate rooms and asked to guess the color of their own hat. They can only either guess white or black, or they can choose to “pass”.
The trio wins if at least one person guesses their own hat color correctly.
The trio loses if anyone guess incorrectly, or if everyone passes.
They can decided on a strategy ahead of time, but cannot communicate once the process begins.
What is the optimal strategy, and what are the odds that the trio succeeds if they employ this strategy?
Some sets sum
Alice and Bob decide to play a game. Alice thinks of a set, S, of any number of integers. Alice can then put this set into any order that she chooses. Bob wins if he can find a contiguous subset of S such that the sum over the subset is divisible by the number of elements in S – while Alice wins if Bob is unsuccessful.
After a few rounds, Bob realizes that he can always guarantee that he will win. What is his strategy?
The Third Sign
Prove that sin(10 degrees) is irrational. Hint: start with sin(30 degrees), and find a polynomial.
You get together 100,000 people into room A, and give each of them a fair coin. You then issue the following instructions:
“Flip your coin, and write down H if it is heads and T if it is tails. Each flip’s result should be written next to the previous flip’s result. For example, if you flip heads, tails, heads, heads, then your paper should say HTHH. Keep on flipping until the last three letters you have written are HTH. Then stop, count how many flips you have performed, and tell me the result.”
You then get together a different group of 100,000 people into room B, and give each of them a fair coin. You issue the same instructions as before, except they are to stop flipping when the last three letters they have written is HTT.
Take all the numbers that you heard from room A and find the average. Then take all the numbers you heard from room B, and find the average. Are these two averages the same, or is one bigger than the other? Hint: it’s probably not what you think.
Alice thinks of a polynomial p(x) of arbitrary degree, with non-negative integer coefficients. How can Bob determine the Alice’s polynomial by asking for only two evaluations of her polynomial, say p(a) and p(b) (where a and b are positive integers decided by Bob)? Bob may hear the result of p(a) before requesting p(b). If you think this is impossible, try it for yourself here (be warned, though, the source code contains hints!)
Prove that ∑i=0 to N i! cannot be a perfect square for N>2.
Hareway to Heaven
How many ways can a rabbit get to the top of a 10-stair staircase, if the rabbit can either hop up one step at a time, or hop up two steps at a time?
Prove that ∑i=1 to N iN is divisible by N for odd N.
You see a number written on a piece of paper. It’s written in roman numerals – unfortunately whoever wrote it forgot which letters stood for what values. However, they remembered the rules correctly (just not the letter to number correlation). If the number that was written was ABACDDEFFF, and A=1000, then what was the value of the entire number?
Prove that at all points in time, there exists at least one pair of antipodal points on the Earth’s equator that are at the exact same temperature (a pair of antipodal points consists of two points on exactly the opposite side of the Earth). In order to prove this, you will need to make only one (very safe) assumption about how the temperature varies with longitude.
Two friends from college bump into eachother for the first time in years.
Alice: How are you?
Bob: Great! I remember you like math puzzles. I have 3 children. The product of their ages is 72, and the sum of their ages equals my room number our freshman year.
Alice: Oh, ok…actually no, I still don’t know their ages.
Bob: Right, sorry. My youngest’s name is Charlie.
Alice: Oh, got it! Isn’t being a parent great?
How old are Bob’s kids?
100 blue-eyed dragons live on a beautiful island. These dragons are very happy on the island, but they are bound by a very specific rule: if a dragon ever knows for sure that she has blue eyes, then that dragon must leave the island at midnight on the day she found out. Luckily, there are no reflective surfaces on the island, and dragons have a strict rule that they never talk about eye color with each-other. So the dragons have lived for many blissful years on the island — each dragon sees 99 other blue-eyed dragons, but doesn’t know for sure that she herself has blue eyes.
One day, a human shows up to the island. This human wants the island for himself, but he knows if he tries to live there, the dragons will eat him. So he hides on the island for a few days, until he sees all the dragons gathered on the beach for a party. Then the human runs onto the beach, where all the dragons can hear him, and yells “I see at least one dragon with blue eyes!”. Then the human runs back into the island’s dense foliage to hide.
The human is convinced that his actions will make him the sole occupant of the island. Is he correct? All the dragons are perfectly logical, and will always reason their way to a conclusion if enough information is present to reach that conclusion.
Let S=1! x 2! x 3! x … x 119! x 120!. S/(m!) is a perfect square, for some 0<m<120. What is m?
Loading the Deck
Alice and Bob are on a team. Together they go up to a random stranger and ask that person to choose five cards from a deck. The stranger does so, and then shows the cards to Alice. Alice then chooses one of those five cards and puts it in a box. She then rearranges the remaining cards, and then shows these four cards to Bob. Bob can see the cards as well as the order in which Alice arranged them. With this information, Bob must predict what card Alice put into the box (i.e. the fifth card). What strategy can Alice and Bob agree on ahead of time so that Bob is correct 100% of the time?
A Broken Clock…
You walk into a truth-machine shop, looking for a truth machine. The shop sells the base variety, which can only answer True/False questions. The owner tells you that he only has three machines left in stock, and unfortunately one of them is broken — it will answer randomly (True or False) to any question asked of it (note that this necessarily means that it can answer a question correctly, by chance). You are allowed to ask one of the three machines one question, once. How do you ensure that you will walk out of the shop with a working truth machine?
A class of 52 students are told by their teacher that she wants to play a game with them. If the students win, everyone will get an A — however if they lose, they will all fail the class. The teacher explains the rules of the game: she will give each person in the class a card from her deck of 52 cards. Each student is to memorize his or her card, and then hand the card back to the teacher. The teacher will then shuffle the cards once, and then lay them out in a line across her deck (facedown).
One by one, the students will be brought to the front, and allowed to flip up to 26 cards face-up. A student wins if he or she is able to find their card in that process. If any single student fails to find their card after 26 flips, then the entire class fails. If every single student successfully finds their card after 26 flips, then the entire class wins. After each student finishes flipping, the cards are all put back face-down. Cards are never removed from the line, and the order of the cards in the line is never changed. Once the flipping process has started, no students are allowed to communicate with each other in any manner. Students sitting at their desks cannot see the cards on the teachers desk.
To make their lives easier, the teacher explains to the class that she will allow the principal of the school to examine all the cards in the line face-up. After seeing all the cards and their order, the principal is allowed to swap the positions of exactly one pair of cards in the line. The students will be able to give the principal a set of instructions to follow to decide what cards to swap. The principal will not speak to the students or tell them anything about the order of the deck.
The teacher tells the students that she will give them some time to confer. What strategy can the students use when drawing cards, and what set of instructions can they give the principal, to guarantee that the entire class gets an A?