I was doing some reading and came across this problem (which was solved). I laughed when I saw the solution. I could probably never figure out 'the way' to solve this in a million years. -- Let m and n be natural numbers greater than one. Let S be an n-element set and let A1,...,Am be subsets of S. Assume that for any two elements x and y in S there is a set Ai such that x is in Ai and y is not or x is not in Ai and y is. Show that n <= 2^m
Determine the maximum among all numbers obtained by deleting 100 digits from the number 123456789101112....9899100, whose digits from left to right are the integers 1 through 100.
(1) Are you sure you stated this problem correctly? For starters, can I assume the m subsets are distinct? Can I construct the m subsets, or are they given? Finally, are you sure n<=2^m is correct? There are 2^n subsets of S, after all. (2) 9999996666666676869...9899100
Suppose that the elements of S is numbered from 1 to n. Then construct mxn matrix \((a_{ik})\), by \(a_{ik}=1\) if k-th element of S is in \(A_i\), and \(a_{ik}=0\) otherwise. From the statement of the problem, for any two columns x and y, there is a row i such that the columns differ at the row i. In other words, all the columns of the matrix are distinct. But with m rows we can generate at most \(2^m\) distinct columns with 0's and 1's.
temur is correct. Subsets are assumed by hypothesis to exist. I believe it is irrelevant whether or not they are disjoint, so far as they satisfy the hypothesis. DH, 2 is incorrect. To clarify, if we delete '2' from '123', we get '13'. When you delete the digit, everything to the right shifts 1 to the left (unless of course you're deleting the last digit Please Register or Log in to view the hidden image! ). You can't permute the digits; you can only repeat this process.
Here's an easier one: Compute the probability that a randomly chosen positive divisor of 10^99 is an integer multiple of 10^88.
\(\underbrace{99999}_{\text{five\ } 9s}\underbrace{555555}_{\text{six\ } 5s} \,5,57\,58\cdots99\,100\) You obviously want the longest leading sequence of 9s possible. The first nine in the sequence results from throwing out the first 8, or 28, or 38, or 48, or ... digits. From then on, throw out 19, or 39, or 59, or ... digits. I can only throw out 100 digits. To maximize the number of 9s I want to minimize the step sizes, so 8+19+19+19+19=84. This leaves me with five leading 9s, and I can't get to the sixth nine at 59. So now I throw out the units: 0 from 50, 1 from 51, ... 5 from 55, at which point I've used up my 100 discards.
D H, once you've gotten rid of the five leading nines, how about getting rid of the 15 digit string 5051...565? You can take it from here.
I didn't get rid of that string because of my superb addition talents. :grumble: I used these superb talents in the first post, where 8+19+19+19+19+19 summed to 95. I once again applied these superb skills in my next attempt. This time, 8+19+19+19+19=84 Please Register or Log in to view the hidden image! but 84+6=100. I wasn't born to be an accountant.
Lessee... \(10^{99}=2^{99}\times5^{99}\) The positive divisors of \(10^{99}\) all have the form \(2^n\times5^m\), and since there are \(100\) possible choices for each of \(n\) and \(m\), there are \(100^2=10000\) possible divisors to choose from in total. Now the subset of these divisors which consists of integer multiples of \(10^{88}\) is the set of all products of the form \(2^j\times5^k\), where \(88\leq j,k \leq 99\). So we have \(12\) possible choices for each of \(j\) and \(k\), hence there are \(12^2=144\) elements in this set. I therefore claim that the probability of randomly choosing a positive divisor of \(10^{99}\) such that it also happens to be an integer multiple of \(10^{88}\) is \(\frac{144}{10000}=1.44%\). Do you agree?
Correct! What more types of problems do you want to see? Real analysis? Or more such combinatorics problems?
Ehm... whatever challenges you feel like throwing out there sound good to me. I'm quite rusty with my combinatorics and advanced real analysis though, just to warn you. I've got like a zillion textbooks and notebooks from my undergrad years and it's hard to keep track of all that knowledge.
Evaluate these limits \( {\lim }\limits_{x \to \infty } \left[ {\frac{1}{e}\left( {1 + \frac{1}{x}} \right)^x } \right]^x \) \( {\lim }\limits_{x \to 0} \frac{{\ln \cos x}}{{(\sin x)^2 }}\)
I think there is a more elementary solution to this problem: Given the sets {A_m}, think of the worst possible case. Then argue: \(n \leq \left( \begin{array} m \\ 0 \end{array} \right)+ \cdots + \left( \begin{array} m \\ m \end{array} \right) = 2^m \). I think there is another neat argument: set out for a contradiction and use the pigeon hole principle. Please Register or Log in to view the hidden image!
I will honestly answer, that the period, or interval slope is found to be \(\mp\) or \( \pm\) where it is found equivalant to the mass raised to the second power... It may describe tachyonic-like systems.
Reiku, WTF? Like seriously, WTF? That has nothing, absolutely nothing whatsoever to do with the question that was asked.
No it doesn't, it's a pure mathematical combinatorics problem, no physics or tachyons or anything of the sort involved.
I disagree. The first of those limits doesn't look so obvious at all to me. Can you do the calculation and show us what you think it should be?
