n-choose-k is equal to n factorial divided by the product of k factorial and the factorial of the difference. It is often written (shorthand) nCk. Because, as I outlined earlier, there is and can be only one winning ticket, you must buy all the tickets, that is, nCk tickets (for k draws from a set of n symbols).
someone is out there who will like you. take off your mask so they can find you faster.
I support the new Nekketsu Kouha Kunio-kun.
Find a 10-digit number which uses each of the digits 0-9 only once, such that the number created by the first two digits is divisible by 2, the number created by the first 3 digits is divisible by 3, et cetera, all the way up to the entire number being divisible by 10.
Highlight for answer: 3816547290
And if I did this correctly, then this is the only number that works.
Thanks, it was a fun problem!
<Swordless> Go hug a tree, you vegetarian (I bet you really are one)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Here's another fun, and not that hard problem.
Let's say you have a dice with k sides. You throw the dice, and subtract c from the result. If c is greater than the result of the dice, the result will be 0. Both k and c are positive integers. Determine the expectation value of the result as a function of k and c. Go! (for example, if c=0, the result will of course be (k+1)/2)
And if I did this correctly, then this is the only number that works.
Thanks, it was a fun problem!
got the same result, ruled out every other number as well.
dito, it was fun!
Randil:
there's positive results ranging from 1 to (k-c) points, and there's k events with equal probability. The expectation value is thus the sum of the values divided by the amount of events:
((k-c+1) * (k-c) / 2) / k
Joined: 6/4/2006
Posts: 97
Location: Everywhere including nowhere
HHS wrote:
However, when imaginary numbers are involved logrithms to weird stuff. The logrithm function isn't actually a function in the imaginary plane.
No, every function is a function. To prove this, if there was a function f that wasn't a function, there would be numbers a, b and c where b ≠ c, f(a) = b and f(a) = c, thus giving b = c (an impossibility), indicating that the function that wasn't a function, had to be a function after all.
If we have a function f and numbers a, b, and c such that b ≠ c and f(a) = b and f(a) = c, then we have judged incorrectly - either f is not a function or b = c. Remember, a function cannot return two different values given the same value.
When we say "The logarithm function is not a function in the imaginary plane," we mean that ln(x) does not exist if x is imaginary. It is not a "nonfunction" or whatever you were talking about, it simply is not there, just like sqrt(x) doesn't exist for x < 0, and just like a function a^x doesn't exist if a is negative.
Are you getting at the domain and range stuff then?
If so, then functions are very often defined for particular domains, regardless of if they are imaginary or real.
If we have a function f and numbers a, b, and c such that b ≠ c and f(a) = b and f(a) = c, then we have judged incorrectly - either f is not a function or b = c. Remember, a function cannot return two different values given the same value.
When we say "The logarithm function is not a function in the imaginary plane," we mean that ln(x) does not exist if x is imaginary. It is not a "nonfunction" or whatever you were talking about, it simply is not there, just like sqrt(x) doesn't exist for x < 0, and just like a function a^x doesn't exist if a is negative.
Yeah, like I said. A function that wasn't a function, which is impossible :P "Returning" is something that algorithmical functions in computer languages do, by the way. Mathematical functions just have values.
I haven't heard of the imaginary plane before. Perhaps you meant the imaginary axis. But ln(x) is defined for the entire complex plane except at x=0, and is in fact injective.
a^x is also defined everywhere except when a=0 and x≤0, and is also real for all integer values of x when it is defined.
ln(x) is defined for the entire complex plane except at x=0, and is in fact injective
Yes, there is such a complex function, but it is either non-continuous, or requires a branch cut (i.e. all complex z for which Re(z)<=0 and Im(z)=0).
This ln(x) HHS is talking about is the complex ln(z), not the real ln(x), and it makes no sense to say "[real] ln(x) does not exist if x is imaginary" even though it is true by default. On the other hand, saying "ln(x) does not exist if x<=0" makes sense.
Also see http://en.wikipedia.org/wiki/Multivalued_function for a description of a "function" that maps to multiple values. What it actually is is a function (in the correct sense) that maps a value to a set of values.
This is easy compared to other problems posted here, but I thought it was very elegant.
Given an integer N, find if it is a power of 2 in the most efficient way possible.
I have found a way faster than using a loop with modulo and division, and does not use table lookup, or uses any math log function, and is extremely compact.
The answer is in the small white text below...
N & (N-1);//if this is 0, then you have a power of 2 number, note I'm using bitwise negation ~, and bitwise and &
Loop with multiplication allowed?
Multiply 2 by itself over and over until it is greater than or equal to N. If the result is equal to N, then yes, it is a power of two; otherwise, no.
P.S. Oh, actually you only need to square 2 by itself over and over, and multiply terms to get the appropriate power.
No loops please! Besides, that only cuts the efficiency of the modulo and divide method in half. :D I'm looking for a huge reduction. O(1) time.
I actually got this question in an interview I had a few hours ago. It was a definite brain teaser, but I had 1 more clue (but I won't give it to you).
Is it already represented in binary? Or base 4, 8, 16? Base 2^n?
I mean, it is easy to say "write N in binary, and if (and only if) it is of the form 10000...0, then it is a power of 2". Note the key word is 'say'.
Is it already represented in binary? Or base 4, 8, 16? Base 2^n?
I mean, it is easy to say "write N in binary, and if (and only if) it is of the form 10000...0, then it is a power of 2". Note the key word is 'say'.
Interesting thinking... You're on the right track, now code it. In fact, you're extremely close. Take a look at my answer (in small white text) if you want to see the solution.
No loops please! Besides, that only cuts the efficiency of the modulo and divide method in half. :D I'm looking for a huge reduction. O(1) time.
You should have mentioned O(1) in the first post. My first thought was the same as FractalFusion's, and I wish I'd known to look for a better solution. The answer isn't as elegant or magical as Carmack's Q_rsqrt function, but it's similar in its own way.
edit: It's not actually Carmack's. The magic is deep and has a long history, much of which is enumerated in this /. post.
Joined: 3/17/2007
Posts: 97
Location: Berkeley, CA
Along those lines, prove the product of k consecutive integers is divisible by k!. (No shame in restricting to the case where they're all positive, but it's true in general.)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
nitsujrehtona wrote:
Along those lines, prove the product of k consecutive integers is divisible by k!. (No shame in restricting to the case where they're all positive, but it's true in general.)
Let's call the number you start from c. We have the product which can be simplified to . The gamma function has the property that . Because both c and k are integers, we are given that the prodcut can be simplified to , which is divisible by k! if c is 1 or larger. Correct?
Here's a problem I came up with when riding the bus today:
Prove that the sum of k consecutive integers is divisible by k if k is odd.
The sum of k consecutive integers from an arbitrary start, c, is given by the summation:
Sum[c+i, i=0, k-1]. Read: The sum of c+i from i equals zero to k-1.
Since there will be k repeated c terms, we can pull them out of the expression. So we have: ck + Sum[i, i=0, k-1]. The second term in this expression is a simple summation equal to (k/2)*(k+1).
After making like denominators and factoring, we arrive at:
k(2c+k+1)/2. The part inside the parentheses is odd when k is even, and even when k is odd. So, the only way that (2c+k+1)/2 can result in an integer is when k is odd. From here, k clearly divides k, and the rest we know to be an integer. Thus, we know that k divides k*(2c+k+1)/2.
I knew about the AND trick... It's sort of obvious when you think about it. But you only wrote that it was an integer, not that it was represented in a binary form on a computer which is important.
The sum of k consecutive integers starting from n can be expressed as the sum of n+i with i ranging from 0 to k-1, and equivalently as the sum of k-1+n-i with i ranging from 0 to k-1. By averaging, we get the constant (k-1)/2+n. The sum is therefore equal to k((k-1)/2+n) which is divisible by k when k is odd.
Let me try the product problem. For any integer l between 1 and k, the number of integers between 1 and k that are divisible by l is equal to floor(k/l), while the number of integers in the range n to n+k-1 that are divisible by l is equal to floor((n+k-1)/l)-floor((n-1)/l), which is greater than or equal to floor(k/l). If l is divisible by a number m, then all integers that are divisible by l are also divisible by m, but the number of integers divisible by m is greater than the total number of integers in the range n to n+k-1 that are divisible by any number that is divisible by m (excluding m itself). Therefore, the number of integers between n and n+k-1 that are divisible by l is always greater than or equal to the number of integers between 1 and k that are divisible by l. Therefore, the product is divisible by the product of any integers between 1 and k that are divisible by l. Then, it is also divisible by the product of this and any other integer that the product of the consecutive integers is divisible by, and which is coprime to the aforementioned product of the integers less than or equal to k that are divisible by l. This proves that the product is divisible by k!.
Joined: 3/17/2007
Posts: 97
Location: Berkeley, CA
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.
HHS, I'm not sure I understood your number-theoretic proof. But you're right that any integer l appears as a factor in at least as many integers in the range n..n+k-1 as in the range 1..k. If you let l range over the powers of a given prime p, you should be able to conclude that the number of p-factors of (n)*..*(n+k-1) is no smaller than the number of p-factors of (1)*..*(k). But the step with the prime powers is crucial.
which can be simplified to 
. The gamma function has the property that 
. Because both c and k are integers, we are given that the prodcut can be simplified to 
, which is divisible by k! if c is 1 or larger. Correct?
