Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
nitsujrehtona wrote:
Hm. Randil's formulas are correct, but I can't tell whether they're just a restatement of what needs to be proved or an allusion to (censored by font color:) the formula for the binomial coefficients.
I came up with a better proof when I went to bed today. The product of k consecutive integers, starting from c is c*(c+1)*...*(c+k-1). This can be seen as (c+k-1)!/(c-1)!. If we take out k! from this expression, we are left with:
k! * (k+1)*...*(c+k-1) / (c-1)!. For this to be divisible with k!, we now need to show that (k+1)*...*(c+k-1) / (c-1)! is an integer.
The factors of (k+1)*...*(c+k-1) consist of c consecutive integers. The factors of (c-1)! consist of c-1 consecutive integers. I will now use the same fact that HHS used in his proof. I won't prove it though, but I guess it could warrant its own proof, but for now, let's just accept it:
"If c and d are both integers, then c*(c+1)*...*(d+c-1) / (d-1)! is an integer." You convince yourself of this if you look at the number of factors in the nominator and the denominator - If the nominator has more consecutive factors than the denominator (in this case one more), then it has to include a multiple of each and every one of the factors in the denominator, thus dividing it.
Using this fact, we now see that c*(c+1)*...*(c+k-1) = k! * (k+1)*...*(c+k-1) / (c-1)! = k! * d, where d is an integer. This shows that the product in question is divisible by k!. Is this an ok proof?
I just noticed that I stated the same thing in my proof twice. The first "Therefore" and the sentence before it just prove the same thing that I started with. This may have been confusing.
And, well, I don't think allusions are accepted in mathematical proofs :P
Randil wrote:
You convince yourself of this if you look at the number of factors in the nominator and the denominator - If the nominator has more consecutive factors than the denominator (in this case one more), then it has to include a multiple of each and every one of the factors in the denominator, thus dividing it.
It seems that this (which you skip) is what one is supposed to prove. It isn't immediately obvious. It's easy to see that each factor is present in at least as many integers in that range as it is in the range 1 to k, but you must prove that these integers are distinct from the ones containing multiples of those factors.
I think my proof works, if we insert this in place of the first "Therefore" but keep the previous sentence: Therefore, in addition to all the integers in the range n to n+k-1 that can be divided by multiples of l, there is at least one other such integer that can be divided by l.
I don't know if this counts as mathematical proof, but every 2nd number is divisable by 2, every 3rd by 3, every Nth by N. So if you multiply 7 consecutive numbers with each other, the result is at least divisable by 2,3,4,5,6 and 7. 7! is exactly the product of these numbers. So it seems very logical to be true. The only problem is that I don't know how to formulate mathematical proves. :X
Joined: 3/17/2007
Posts: 97
Location: Berkeley, CA
Sorry, long post. And sorry if the technical details took the fun out of the problem. :)
HHS has me convinced, and also anticipated the problem with Kuwaga's answer: if you find factors of 2, 3, 4, 5, 6, and 7 (separately) in the product, you have to make sure you didn't double-count any factors: 350 is a multiple of all of them, but not of 7!. (Mathematicians aren't picky about the "form" of a proof as long as it explains any potentially tricky issues.)
Here's the "proof by allusion" with details filled in: Assuming c,k>0, and letting n=c+k-1, you need to show n!/(k!(n-k)!) is an integer. That formula actually gives the number of ways to choose k objects from a collection of n objects (which would obviously be an integer). That's a standard fact, proved as follows: on one hand there are n! ways to line up the whole collection in some order (one of the n objects comes first, followed by one of the remaining (n-1), etc.); on the other hand there are (n choose k)*k!*(n-k)! ways, since you can pick which k of the objects come first, then arrange the first k & last (n-k) objects. So (n choose k)=n!/(k!(n-k)!). Actually, the "binomial coefficients" (n choose k) work when n isn't a positive integer, but not for the reasons above. (Wikipedia can explain the name and why they'd ever make sense for negative n.) Alternatively, split into two cases (if there's a 0 factor, 0 is divisible by anything; if not, collect the minus signs and you're left with a product of consecutive positive integers). Or you can work modulo k!, if you know what that means.
They are not double counted. Every 6th number is divisable by 6, that means by 2 and 3. So there are enough '2' and '3' factors in the final number to be divisable by 7!. I don't see a problem there. I think it's half as complicated as it seems. o_o
They are not double counted. Every 6th number is divisable by 6, that means by 2 and 3. So there are enough '2' and '3' factors in the final number to be divisable by 7!. I don't see a problem there. I think it's half as complicated as it seems. o_o
So a corollary to this argument is, if you have three consecutive numbers n,n+1,n+2, and n and n+2 are prime, then n+1 must be divisible by 6, for n > 3.
Edit: Yep. http://en.wikipedia.org/wiki/Twin_prime
Here's one. Find an a bijective map from the real numbers to a subset of the real numbers that has no interior points.
Or: Show that any polygon can be subdivided into a number of parts that can be rearranged to form a circle.
Or: Can a nonempty region of physical space be shaped like a two-sided polygon?
Here's one. Find an a bijective map from the real numbers to a subset of the real numbers that has no interior points.
Define f: real number x maps to y as follows:
- the integer part of y is the integer part of x
- for the fractional part of y:
-- the (2n)-th decimal digit of y is the n-th decimal digit of x, n>=1
-- the (2n-1)-th decimal digit of y is the n-th decimal digit of pi, n>=1
Then f is a bijective map from the real numbers to a subset of the irrational numbers A. The set of irrational numbers has no interior points. Therefore, A has no interior points.
What is a subset of the real numbers that has no interior points?
Interior point
Basically, x is an interior point of a real subset A if there exists an interval of positive width (however small) centered on x that is (completely) contained in A.
e.g.
The set of interior points of closed interval [0,1] is open interval (0,1).
The set of interior points of the set of irrational numbers is empty. There are no interior points, because every interval of positive width contains a rational number.
P.S. I had to check Wikipedia for the definition as well.
Joined: 10/28/2007
Posts: 1360
Location: The dark horror in the back of your mind
FractalFusion wrote:
Define f: real number x maps to y as follows:
- the integer part of y is the integer part of x
- for the fractional part of y:
-- the (2n)-th decimal digit of y is the n-th decimal digit of x, n>=1
-- the (2n-1)-th decimal digit of y is the n-th decimal digit of pi, n>=1
Then f is a bijective map from the real numbers to a subset of the irrational numbers A. The set of irrational numbers has no interior points. Therefore, A has no interior points.
There exist irrational numbers such that the (2n)-th decimal digit is also that of pi, whereas the (2n-1)th digit does not. The map you describe would map all of these numbers to the same irrational number and therefore is not bijective.
There exist irrational numbers such that the (2n)-th decimal digit is also that of pi, whereas the (2n-1)th digit does not. The map you describe would map all of these numbers to the same irrational number and therefore is not bijective.
Note that the (2n)-th decimal digit of y is the n-th decimal digit of x, not the (2n)-th decimal digit of x. I ensure all the digits of x are used here.
This type of decimal place weaving comes from set theory, where it is possible to show that the cardinality of R^n (set of n-tuples of real numbers) and R (set of real numbers) are the same.
Here's one. Find an a bijective map from the real numbers to a subset of the real numbers that has no interior points.
Let F be the Cantor Ternary set and let f be the cantor ternary function. Then g=tan(pi*(f(x)-1/2)) is a one-to-one map of the Cantor Ternary set to the real numbers. Since the complement of the Cantor Ternary set is dense, the Cantor ternary set has no interior points, and thus g is the desired function.
HHS wrote:
Or: Show that any polygon can be subdivided into a number of parts that can be rearranged to form a circle.
Need these parts be measurable? If not, we can do basically anything.
Need these parts be finite in number? If so, there is no possiblility.
Need these parts be countably infinite? If not, we simply rearrange all the points individually.
However, if we require countably many measurable parts, then I'm not so sure.
Define f: real number x maps to y as follows:
- the integer part of y is the integer part of x
- for the fractional part of y:
-- the (2n)-th decimal digit of y is the n-th decimal digit of x, n>=1
-- the (2n-1)-th decimal digit of y is the n-th decimal digit of pi, n>=1
Let F be the Cantor Ternary set and let f be the cantor ternary function. Then g=tan(pi*(f(x)-1/2)) is a one-to-one map of the Cantor Ternary set to the real numbers. Since the complement of the Cantor Ternary set is dense, the Cantor ternary set has no interior points, and thus g is the desired function.
Yep, both correct. The tangent operation is unnecessary, though.
Need these parts be measurable? If not, we can do basically anything.
Need these parts be finite in number? If so, there is no possiblility.
Need these parts be countably infinite? If not, we simply rearrange all the points individually.
Finite, but not necessarily measurable. (And by rearranging I mean translation by some vector, by the way)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Here's another (hopefully not too easy) problem from me: Say you have a wooden rod that is exactly 100 centimeters long. You cut the rod in two random places (the two coordinates where you cut are independent). You will now have three wooden rods. What is the probability that you can form a triangle of these three parts? The width of the rod is insignificant.
A triangle can be formed as long as every piece is shorter than the two others together, and therefore less than 50 cm in length. Therefore, if the first cut is A centimeters into the rod from either side, the other cut must be between 50 and A+50 centimeters into the rod along the same direction. Therefore, the probabililty is 1/4.
A problem I came across a while ago. Calculate the average distance between two points on the surface of the unit sphere. That is, if two points were placed on the surface of a sphere with a radius of one and a chord drawn between them, the average length of the chord if the points were selected at random.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
xenos wrote:
A problem I came across a while ago. Calculate the average distance between two points on the surface of the unit sphere. That is, if two points were placed on the surface of a sphere with a radius of one and a chord drawn between them, the average length of the chord if the points were selected at random.
Completely intuitively (I hope that's a word), I feel that the distance should be Pi/2. All possible distances between the points is half a circle with a radius of 1. Because of symmetry, it's equally likely to appear to the left of the middle point of this half circle, therefor the expectation value should be on the middle of this half circle, thus the average distance is Pi/(2*2) = Pi/4. Don't throw rocks on me if this is wrong!
Choose a coordinate system such that the first point is located at (1,0,0) and the second at (x,y,z).
The distance from the first point to the second point is sqrt((x-1)^2+1-x^2) = sqrt(2-2x). We must then calculate the integral of sqrt(2-2X)dP(x<X) with X going from -1 to 1.
The distance sqrt(1-x^2) shall be called r and we note that dr/dx = -x/r. The surface area of the portion of the sphere for which X ≤ x ≤ X+dX is 2*pi*r*sqrt(dX^2+dr^2) = 2*pi*r*sqrt((1+X^2/r^2)dX^2) = 2*pi*r*sqrt(dX^2/r^2) = 2*pi*dX. Therefore, dP(x<X) = 1/2dX.
The answer becomes (4^(3/2)*2/3)/2 = 8/3.
Choose a coordinate system such that the first point is located at (1,0,0) and the second at (x,y,z).
The distance from the first point to the second point is sqrt((x-1)^2+1-x^2) = sqrt(2-2x). We must then calculate the integral of sqrt(2-2X)dP(x<X) with X going from -1 to 1.
The distance sqrt(1-x^2) shall be called r and we note that dr/dx = -x/r. The surface area of the portion of the sphere for which X ≤ x ≤ X+dX is 2*pi*r*sqrt(dX^2+dr^2) = 2*pi*r*sqrt((1+X^2/r^2)dX^2) = 2*pi*r*sqrt(dX^2/r^2) = 2*pi*dX. Therefore, dP(x<X) = 1/2dX.
The answer becomes (4^(3/2)*2/3)/2 = 8/3.
Hmm. I think you're off by a factor of 2 (during the integration). It should be 4/3.
I came up with 4/3 by starting with an angle theta between the two points, and that the probability of a point being at angle theta is sin(theta)/2. The rest is similar to what HHS wrote.
