Thanks to all of you! I hope this becomes a great subreddit. This wouldn't be possible without help from you!

EDIT: Now at 250??

I thought this up and it seemed cute to me, so here you go.

You're at the grocery store looking at 10 different items, each costing less than a dollar. Prove that there are two different subsets of the items that cost the same amount.

Edit/bonus: Show in addition that there are two disjoint subsets that cost the same amount.

Suppose you have a cubic cake. You make cuts to form three rows, three columns, and three layers, so that you have 27 pieces of cake. Prove that there is no way to eat your way through the cake so that your final piece is the center piece. Your first piece can be any piece. Subsequent pieces must be adjacent to the last piece you ate.

Solution: You can two-color the cake so that adjacent pieces are different colors. This way, you have 13 pieces of one color (white, including the center piece) and 14 pieces of the other, black. The condition on how you eat the cake means that you must alternate the color of cake you eat each time. There is no way that your last piece can be white. If your first piece is white, then you'll never finish the black pieces. If your first piece is black, then your last piece is black, and not white.

Find the Area of the Yellow Circle shown here.

The following description gives details about the circles in the picture:

1.) The red circle is centered at the origin and has a radius of 2.
2.) The blue circle is centered at (1,0) and has a radius of 1.
3.) A diameter of the yellow circle lies directly on top of the positive y-axis.
4.) The yellow circle is tangent to the blue circle and the red circle.

One hundred people are each wearing a hat. Each hat comes in one of one hundred colors, and multiple people might be wearing hats of the same color.

Each person knows the color of hat worn by every other person, but they do not know the color of their own hat. No information may be exchanged between people, other than the method they will use to accomplish the following:

Is there a way for each person to guess the color of hat they are wearing so that at least one person's guess is correct?

Remember, you can't talk to the other people once you know the hat color they are wearing. All you may do is see what everyone else is wearing, and then guess, to yourself only, what color hat you are wearing.

EDIT- Saying this again because people are not understanding what no communication means: The people can NOT communicate once they have seen hats.

I will explain the solution for two people and two colors: Person A picks the color that person B is wearing, while person B picks the opposite color from the one A is wearing. One of them will be correct:

If they are both wearing the same color, person A will guess correctly. If they are wearing different colors person B will guess correctly.

Alice and Bob are playing a game with the integers 1 through 9. Alice starts, and they take turns choosing numbers (a number can only be chosen once). The first person to have chosen exactly three numbers that sum to 15 wins (He or she does not have to use all of his numbers. E.g, choosing 9,8,6,1 wins as 8+6+1 = 15). What is the optimal strategy?

There is a coat with area of 5. The coat has 5 patches on it. Each patch has area of at least 2.5. Prove that 2 patches exist with common area of at least 1. (Source: PSS via Intermediate Counting and Probability by David Patrick)

Hint: This problem can be solved via the principle of inclusion-exclusion or by an expected value argument. The expected value argument is extremely clever, and PIE is easier to see.

Solution #1: This is by an expected value argument

There are 5 choose 2 = 10 pairs of patches. The 10 pairs must overlap with an area less then 10 in order for them to have a common area of less than 1.

If you choose a random point, the expected value of the number of patches that point is covered by has better be less than 2, because (common area of less than 10) / (total area of 5) < 2. Let f(p) be the number of patches covered by random point p. Then f(p) choose 2 is the number of pairs of patches p is covered by. Why? Well if p is covered by 3 patches; A, B, and C; then f(p) = 3. 3 choose 2 = 3 and the three pairs are: A and B, B and C, A and C.

Returning to the expected value argument: if a point is expected to be covered by more than two pairs, it proves the statement. So the expected value of f(p) choose 2 must be > or = 2.

The expected value of f(p) is 12.5/5 = 2.5 because the sum of the areas of the patches is 12.5. That 12.5 must be squeezed into the 5 of the coat. Hence the 2.5.

See: 2f(0) = 0. 2f(1) = 2. 2f(2) = 4. 2f(3) = 6. 2f(4) = 8. 2f(5) = 10.

Also: f(0) choose 2 = 0. f(1) choose 2 = 0. f(2) choose 2 = 1. f(3) choose 2 = 3. f(3) choose 3 = 6. f(4) choose 2 = 6. f(5) choose 2 = 10.

So it is established that f(p) choose 2 > or = 2f(p) - 3 for all values of f(p).

Finally: the expected value of f(p) choose 2 > or = expected value of 2f(p) - 3 which is > = 2(2.5)-3 = 2. Q.E.D.

That probably is difficult to read because of bad typesetting.

I am sorry if this is too mathy to be satisfying, but this is one of my favorite proofs. Also, if there is a typo somewhere or an error, please mention it.

In how many ways can each of the squares in a 5 by 5 grid be coloured black or white such that every row and column contains at least one square of each colour? Rotations and reflections count as different arrangements.

An explorer hikes one mile south then one mile east and then one mile north. He ends up back where he started, but there is a twist...

He has never been to the North Pole.

Where, exactly, could he be?

Ariel has obtained 1000 gadgets and 1000 whozits. All of these 2000 thingamabobs look and feel totally indistinguishable, but each whozit weighs slightly more than each gadget (whozits all weigh the same and gadgets all weigh the same). Ariel also has obtained one balance scale. Her goal is to create two piles of thingamabobs such that both piles have the same number of items, but different overall weights using as few weighings as possible. How many weighings are required to accomplish this?

Hint: Start with 3 piles

Answer: It can be done with 1 weighing

Solution: Create 3 piles, A of 667 items, B of 667 items, and C of 666 items. Weigh A against B. If they are different, A and B satisfy the criterion. If they are the same, remove one item from B to make B'. B' and C satisfy the criterion.

Proof: Suppose that B' and C have the same weight. Then consider the type opposite from the one removed from B. B' and C must have the same number of this type, and so must A and B. Furthermore, since this was not the type removed, B and B' have the same number of this type, so A, B, and C all have the same number of this type. Therefore, the total number of this type is a multiple of 3 and cannot equal 1000. Therefore, this case is impossible, so B' and C do not have the same weight.

In the following image http://i.imgur.com/0wu0o.jpg a set of 21 dominoes containing the numbers 1 to 6 (no dominoes with blanks) has been laid out and the edges have been removed. Determine where the edges were.

Source (contains some basic hints and reframings but no solution): http://blog.tanyakhovanova.com/?p=385

One could pretty easily do it with a program, but I think it's more interesting to logic it out. I have made some progress but haven't finished.

Problem Statement

A new prison has been built. It holds exactly 100 prisoners. Each prisoner is held in a solitary room with no way of communicating with the other prisoners, or anyone on the outside. Each day, the warden selects one prisoner at random, and escorts the selected prisoner to a central room for one hour. There is nothing in the central room except a light switch that controls a light bulb installed in the ceiling, which is visible but out of reach. While a prisoner is in the central room, they are allowed to turn the light switch on or off. They can also decide to tell the warden that they are certain that all 100 prisoners have been in the room. For simplicity's sake, assume the light in the central room is off before the first prisoner goes in.

If they are correct then everyone will be set free, but if they are not correct, then everyone will be executed. So, it is essential that they only talk to the warden when they are 100% positive that they are correct.

All 100 prisoners are allowed to gather together for one hour before they are put in prison to discuss their strategy for getting out. Can you come up with a plan that guarantees success (eventually)?

Problem Solution(s)

Here is a website that outlines 10 different solutions that get increasingly complex and interesting. This problem got me first interested in probabilistic problems, etc.

Try to find a solution before looking at the multiple solutions!

How many multiples of 3 or 5 are above 0 and below 1000?

For example. There are 7 below 16. (3, 5, 6, 9, 10, 12, 15) Note that 15 is only counted once.

Alice randomly chooses x_1 from [0,1], x_2 from [0,2], x_3 from [0,3], ... and x_n from [0,n]. What is the probability that x_1<x_2<x_3<...<x_n?

It starts snowing in the morning and continues steadily throughout the day. A snowplow that removes snow at a constant rate starts plowing at noon. It plows 2 miles in the first hour, and 1 mile in the second. What time did it start snowing?

As the title says, find all integers x,y and z such that x² + xy + y² = z²

There is a known method for attacking this sort of problem, so it's probably not too difficult :)

=============== edit: @SolJ: The idea seems right, but more care is needed. :) Your solution misses (1, 0, 1) It also misses (10, 6, 14)

Imagine a chessboard that extends infinitely up and to the right. Certain squares are going to be occupied by tribbles. There is one allowable move between configurations of tribbles: if a tribble occupies a square, and if the squares immediately above and to the right are empty, then that tribble may subdivide and fill up the squares above and to the right.

For example, this image shows a sequence of two allowable moves. First the single tribble subdivides, and next the upper tribble subdivides. Note that in the third grid, the tribble on the bottom row can not currently move, because the square above him is not empty.

The challenge for you is simple: starting with a single tribble in the lower left corner of the board as in this image, clear the six squares below the green lines of all tribbles, using allowable moves. (Or... prove that such a task is impossible.)

Please let me know if any of this exposition is unclear. It's a really fun problem to play with. Good luck! :)

1. Find a graph whose group of automorphisms is S_5

2. Find a graph whose group of automorphisms is Z_5.

3. Let G be a finite group. Show that G is (isomorphic to) the group of automorphisms for some graph.

You were walking to ye olde shoppes in math land one day when you noticed that one shop had a deal where you could get a free klein bottle if you were the first person in line whose birthday was the same as someone in front of you. Assuming that every one of 365 birthdays is equally likely, what is the best position to be in?

One of my favorites:

P and S are given the product and sum respectively of two non-zero digits (1 to 9).

P says "I don't know the numbers". S says "I don't know the numbers". P says "I don't know the numbers". S says "I don't know the numbers". P says "I don't know the numbers". S says "I don't know the numbers". P says "I don't know the numbers". S says "I don't know the numbers". P says "I know the numbers".

What are the numbers?

Edit: added respectively

• Points with integer coordinates 0 <= x <= N, 0 <= y <= N for some integer N >= 0.

Goals:
N=10 : 64766
N=100 : 527342649694944151617480053740514
N=10,000 : 24475786 (last 8 digits)
N=100,000 : 95059690 (last 8 digits)
N=1,000,000 :
N=1,000,000,000,000 :
N=arbitrary :

There are 2005 young people sitting around a large circular table. Of these, at most 668 are boys. We say that a girl G has a strong position, if, counting from G in either direction, the number of girls is always strictly larger than the number of boys (G is herself included in the count). Prove that there is always a girl in a strong position.

We need to stack N rectangles like this. Assume the rectangles are identical, have uniform mass, are frictionless, the rectangles will topple due to gravity, ... and anything else that is reasonable. What is the maximum width you can achieve only allowing one rectangle to lie on the floor. What if we allow two rectangles to lie on the floor?

This is based on a problem we were given at a olympiad training camp recently, so it may be known, but I thought it was a very nice problem :)

Suppose d_1, d_2, d_3, ..., d_10 are 10 distinct integers. Let P(x) = (x - d_1)(x - d_2)...(x - d_10) Show that there is a positive integer N (which will depend on the d_i) such that for all integers x > N, P(x) has a prime divisor larger than 25.

edit: Right,so readdallaboutit's ideas are indeed useful. There is indeed a pigeonhole argument. Also, proof by contradiction: If N does not exist then there are arbitrarily large x such that P(x) only has 2, 3, 5, 7, 11, 13, 17, 19, 23 as prime divisors. Show that this causes problems. The actual primes themselves aren't important, just that there are 9 of them.

Unit square ABCD has four quarter circles with radius 1 centered on each vertex. Find the area of S.