Skilled player (1882)
Joined: 4/20/2005
Posts: 2160
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?
HHS
Active player (282)
Joined: 10/8/2006
Posts: 356
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.
Joined: 10/20/2006
Posts: 1248
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.
IRC nick: UncombedCoconut
Joined: 10/20/2006
Posts: 1248
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
Joined: 3/25/2004
Posts: 459
Kuwaga wrote:
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
HHS
Active player (282)
Joined: 10/8/2006
Posts: 356
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?
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
HHS wrote:
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.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
HHS wrote:
Here's one. Find an a bijective map from the real numbers to a subset of the real numbers that has no interior points.
What is a subset of the real numbers that has no interior points?
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
Warp wrote:
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.
sgrunt
He/Him
Emulator Coder
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.
Editor, Player (67)
Joined: 6/22/2005
Posts: 1041
HHS wrote:
Or: Can a nonempty region of physical space be shaped like a two-sided polygon?
Is it even possible to have a two-sided polygon? I thought a polygon needs to be closed.
Current Projects: TAS: Wizards & Warriors III.
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
sgrunt wrote:
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.
Player (36)
Joined: 9/11/2004
Posts: 2623
Dacicus wrote:
HHS wrote:
Or: Can a nonempty region of physical space be shaped like a two-sided polygon?
Is it even possible to have a two-sided polygon? I thought a polygon needs to be closed.
In non-euclidian space a two sided polygon with non-zero area can exist.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Joined: 7/16/2006
Posts: 635
HHS wrote:
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.
HHS
Active player (282)
Joined: 10/8/2006
Posts: 356
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)
Skilled player (1882)
Joined: 4/20/2005
Posts: 2160
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.
HHS
Active player (282)
Joined: 10/8/2006
Posts: 356
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.
Player (119)
Joined: 1/30/2007
Posts: 82
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.
Skilled player (1882)
Joined: 4/20/2005
Posts: 2160
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!
HHS
Active player (282)
Joined: 10/8/2006
Posts: 356
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.
Editor, Skilled player (1936)
Joined: 6/15/2005
Posts: 3239
HHS wrote:
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.
Joined: 10/6/2007
Posts: 330
Location: B.C Canada
There are 5 apples. you take away two. How many do you have?
Joined: 10/20/2006
Posts: 1248
2
Joined: 10/6/2007
Posts: 330
Location: B.C Canada
Yay! you got it. That's one of my favourite riddles