Google Perplexed

For every integer n between 1 and 10¹⁰⁰ (inclusive),  take the product of the non-zero digits of n. Then find the sum of these 10¹⁰⁰ products. What is the last digit (i.e., the one’s digit) of this sum?

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?

Lost marbles

You walk into a knickknack shop, which has four large bags of marbles for sale for $100 each. The bags bear the labels Red, Blue, Green, and Mixed (the Mixed bag has a random assortment of red, blue, and green marbles). You would like to buy two bags of marbles – you don’t really care what you purchase, as long as you don’t end up with a Mixed bag. You hand over $200 to the shopkeeper – but before you can make your selection, the miserly shop-keeper warns you: “I failed to pay my assistant, and in revenge she mixed up the labels on the bags! Every bag is guaranteed to have the wrong label, relative to its actual contents.” Seeing that you are still interested in making a purchase, the shop-keeper’s eyes light up, saying “I will let you take a marble out of a bag, one at a time, to inspect it – for the very reasonable price of one dollar per marble”.

You only have two extra dollars in your pocket – what strategy can you use to guarantee that you leave with two bags of marbles, such that neither bag is Mixed? (credit to Alec Stein)

The Third Sign

Prove that sin(10 degrees) is irrational. Hint: start with sin(30 degrees), and find a polynomial.

Flipped

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.

Magic Polynomial

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!)

Prime Evil

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?

Binomial expanse

Prove that ∑_{i=1 to N} i^N is divisible by N for odd N.

Quad power

Find all six real solutions to the expression (x²-7x+11)^(x2-13x+42) = 1 .

Lost Count

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?

Tropical twins

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.

Added Information 

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?

Dragon’s Dilemma

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.

Towering Factorial

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?

Loopy

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?

Hard as hadamard

Alice, Bob, and Charlie will play a game together. They will win or lose this game as a group. The trio is blind-folded and then brought into a room together. A black or white hat is randomly selected for each player, and placed on that player’s head. Then the blindfolds are removed. Once Alice, Bob, and Charlie have had a good look at each other, they are each brought into private rooms and asked to state the color their own hat. They allowed responses to this query are “Black”, “White”, or “Pass”.

The trio will lose (as a group) if either a) everyone passes, or b) anyone guesses incorrectly. The trio wins (as a group) otherwise. What is a strategy they can use that will yield a probability of winning greater than 50%?

Classic with a twist

You are a prisoner who has escaped his cell. You have made your way through the long twisting tunnels of the prison, and you know you are very close to freedom. You come to a fork in the tunnel. From the prison’s blueprint, you remember that one direction leads to freedom, and the other to certain death – but you cannot recall which direction is which. Standing at the fork are two guards. One, both, or neither of the guards always tells the truth. Any guard that doesn’t tell the truth always lies. You can ask each guard one question. How do you guarantee that you will walk down the tunnel of freedom?

So very close

Four prisoners stand in a line. Each prisoner can see all the prisoners ahead of them in line. One of 8 random colored hats are placed on each prisoner’s head, without replacement (no color is repeated). Starting with the back-most prisoner, each person is asked to guess the color of the hat on their head. They must guess one of the 8 available colors (the prisoners are told what the 8 possible colors are ahead of time). All prisoners can hear each other’s guesses. If two prisoners make the same guess, they are both executed. If a prisoner guesses incorrectly, they are executed. What strategy can the prisoners adopt to guarantee that at most one of them dies? (credit to David Zimmerman)

chomp

Jack and Jill play a game on an NxM grid. The first person to touch the cell at coordinate (N,M) loses. The players alternate turns. On a player’s turn, they must touch an active cell. When a player touches a cell at coordinate (i,j), all cells with coordinates (x,y) such that x<=i AND y<=j are deactivated. Jack goes first. Who has a winning strategy?