• rdore

(no subject)

Suppose that n people are seated around a table. Is it possible to rearrange them so that no pair of people is in the same relative position. For example, if Alice is two seats to Bob's left, then after rearranging, Alice cannot still be exactly two seats to Bob's left. (Your answer should be a function of n.)
  • mathic

(no subject)

Not a difficult problem, but it was on the exam I was invigilating and I thought it was cute.

If G and G' are graphs isomorphic to K_{n,n} (complete bipartite), how many isomorphisms are there from G to G'?

Dropping the Balls

You have two crystal balls and an N-story building (N a positive integer) with windows on each floor.  If you place a crystal ball on the ground, nothing will happen, but if you drop one off the roof, it will shatter upon hitting the ground.  Your goal is to find the highest floor from which you can drop a ball out the window and not have it shatter (or show that no such floor exists).  To do this, you will drop balls out of windows and see what happens.  Naturally, if a ball doesn't shatter, it can be used in later drops, but once a ball shatters it is no longer useful.  Subject to these limitations, you'd like to minimize the maximum number of drops you might have to make.  What will your strategy be, and what's the maximum number of drops you might have to make?

Same (Sum of) Differences

For nN, suppose that the set S ≡ {1, 2, 3, ..., 2n} is partitioned into two sets A and B of size n each.  (That is, AB = S and |A| = n = |B|.)  Say A = {ai}in= 1 and B = {bi}in= 1 with a1 < a2 < a3 < ... < an and b1 < b2 < b3 < ... < bn.  Prove that Σin= 1 |ai - bn-i+1| = n2.
  • Current Mood
    amused amused

Playing with Chips

    Suppose you have a stack of N poker chips.  If N ≥ 2, you split the stack into two smaller stacks of sizes m and n with both new sizes positive integers and, of course, m + n = N.  While you're at it, note the product mn.  You can now repeat the process, splitting any stack(s) of size ≥ 2 into two smaller stacks and noting the product of the two new sizes.  After N - 1 steps, you will have N stacks of size 1 each, hence no more splitting will be possible, and you will have noted a bunch of products.  Add all these products together.  As an example, if N = 5, you could follow the final steps:
  1. Split the stack of size 5 into stacks of size 2 and 3 and note the product 2 × 3 = 6.
  2. Split the stack of size 2 into stacks of size 1 and 1 and note the product 1 × 1 = 1.
  3. Split the stack of size 3 into stacks of size 2 and 1 and note the product 2 × 1 = 2.
  4. Split the stack of size 2 into stacks of size 1 and 1 and note the product 1 × 1 = 1.
  5. Add all the products together, arriving at 6 + 1 + 2 + 1 = 10.
Of course, there are choices along the way, as there may be more than one way to split a stack into two smaller stacks.  Show, however, that the final sum of the products (10 in the example above) is independent of the choices made (though it may depend on N).
  • Current Mood
    amused amused
math, nerdy

Everybody likes circles. Let's do a circle problem

In the Cartesian plane, draw a circle of radius r = 0.1 centered at (1, 0). Also draw identical circles centered at each of (0, 1), (-1, 0), and (0, -1).

Define a function P(R) such that, if a circle C of radius R is drawn centered at the origin and a point (x1, y1) on (but not within) circle C is randomly chosen, P(R) equals the probability that (x1, y1) lies on or within any of the smaller circles.

1. Is the shape of P(R) symmetric or asymmetric? (If you plot P as a function of R, will the line you draw have any axes of symmetry?)

2. For what value of R does P(R) reach a maximum value?

3. What is P(R)'s maximum value?

Extra credit: Generalize your solution to apply to all values of r.
  • rdore

group theory

Suppose that G is a finite group, and f is a homomorphism from G to G so that for more than three fourths of the g in G, f(g)=g-1. Prove that f(g) = g-1 for all g in G.

(This is problem 2.5.52 in Herstein's Abstract Algebra.)
  • rdore

(no subject)

Let F be a field and X a set. The functions from X to F form an F vector space. Let A be a set of linearly independent functions from X to F. Prove that there is Y a subset of X, with |Y|=|A| so that

{f restricted to Y : f in A}

is linearly independent (in the space of functions from Y to F).
complex, subtle, carbon, reverse, fractal

Battleship theory

A few days ago, I happened to be playing an old "Battleship"-style game. It was a bitterly fought struggle, but IIRC I prevailed over the computer in this contest. At one point my "attack grid" (showing the results of my shots) looked something like the following:

  A B C D E F G H
1|. . X . . . . .|   X = miss
2|. X O . . . O .|   O = hit
3|. . X . . . X .|   . = not fired upon yet
4|. . . . . . . .|
5|. . . . O . X .|
6|. . . . O . O .|
7|. . . . . . X .|
8|. . . . X . . .|

I don't remember the layout entirely, of course, but assume that I had inundated the grid sufficiently to be certain that I must have hit each enemy ship at least once by this point. In this particular round, my opponent had three 3-square ships and one 5-square ship to arrange horizontally and vertically (with no overlapping) in the 8x8 grid allotted.

Given the diagram shown, then:

1) List all of the possible layouts of the enemy fleet. (If you like, you can denote the poistion of a ship by listing the coordinates of its ends.)

2) At this point in the game I had the opportunity to use a special trick shot. I could fire upon a single square and, if a ship occupied that square, a chain reaction would start: The ship I hit would blow up, along with any ship occupying a square that was next to, above, or below a square occupied by the ship I hit, along with any ship immediately beside that ship, and if the fourth ship were unlucky enough to be beside any of these it would be blown up as well. Determine my best-percentage shot in terms of expected damage done. (Obviously I would be sure to hit something at D2, for example, but would that necessarily do the best average damage?)