tag:blogger.com,1999:blog-4115025577315673827.post6865298703186604157..comments2020-01-23T12:35:45.593+05:30Comments on CSE Blog - quant, math, computer science puzzles: Maxima Property SubsetPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger25125tag:blogger.com,1999:blog-4115025577315673827.post-61640846344338952332016-11-13T12:46:20.365+05:302016-11-13T12:46:20.365+05:30^@gaurushh Abey, ghar se hagg ke aaya kr na. Itne ...^@gaurushh Abey, ghar se hagg ke aaya kr na. Itne toh subsets hi nhin hote total.Rohan Jainhttps://www.blogger.com/profile/15391484841580161769noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-15576559227916063192014-06-10T23:35:07.124+05:302014-06-10T23:35:07.124+05:30The answer would be:
n*2^(n-1).
First you can pick...The answer would be:<br />n*2^(n-1).<br />First you can pick any number and then, build any set from the rest of the numbers. And put the initial number into that set as well. This way you can have the number of sets such that exactly one element is common.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-39336564182415958182013-03-20T16:28:13.049+05:302013-03-20T16:28:13.049+05:30Let any subset be represented by a n-length binary...Let any subset be represented by a n-length binary bit string.<br />It is easy to see that we can form n subsets.<br />eg: {1,2,3,...,n-1},{1,n},{2,n},{3,n},...{n-1,n} (many other combinations are possible)<br />So we get the number of subsets, N>=n<br />Now consider 3 distinct subsets in the form of binary bit strings - a, b, and c.<br />[+ and . are bit-wise OR and AND operators]<br />So a.b, b.c and c.a has 1 element only, as per the criteria.<br />For N>n, we must have some vectors which are linear combinations of other vectors.<br />Let c be one such vector, such that c=a+b<br />a.c = a.(a+b) = a.a + a.b -> It will have one element only if a is a single element vector.<br />Similarly, b.c = b.b + b.a -> Here again, b will have to be a single element vector.<br />Also, a.b = 1<br />If a and b are single element vectors and a.b=1, then a = b -> contradiction!<br />So c cannot be a linear combination of a and b i.e. no vector in the set can be a linear combination of other vectors => N<=n<br /><br />Combining both inequalities, we get N = n.<br />Arnabhttps://www.blogger.com/profile/13734216328461677608noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-73008630474589139232012-10-28T22:26:54.473+05:302012-10-28T22:26:54.473+05:30@Dinesh: Awesome solution! By the way how did u ca...@Dinesh: Awesome solution! By the way how did u calculate the determinant of the matrix? Is it a well known formula?sidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-10217159256748497042012-10-19T16:46:22.552+05:302012-10-19T16:46:22.552+05:30for those of you who came up with formulas other t...for those of you who came up with formulas other than f(n)=f(f)+f(n-k)+k*(n-k)<br />explain why f(4)=8 {1 2 3 4 14 24 13 23 }Nikhil Simha Rhttps://www.blogger.com/profile/09880727972082313533noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-90327586810384607882012-10-19T16:41:18.904+05:302012-10-19T16:41:18.904+05:30I am not sure if this has a closed form expression...I am not sure if this has a closed form expression. But I remember solving this using DP for some coding competition.<br /><br />DP step is f(n)=max(f(k)+f(n-k)+k*n-k) (for k=1...n-1)<br /><br />Explanation: say you partitioned {1..n} into to subsets, one of size k and the other of size n-k. <br />(f computer the answer at any x)<br />now the subsets with this partitioning would be f(k)+f(n-k) (obviously)<br />and now the interesting part k*(n-k) , this represents the number of sets that can be included in your set of sets that contains elements from both the partitions. And it is easy to see why you have to pick exactly one from each partition for the condition to hold to form a new set that you would want to include.<br /><br />Nikhil Simha Rhttps://www.blogger.com/profile/09880727972082313533noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-88885619261751909882012-09-26T19:50:17.898+05:302012-09-26T19:50:17.898+05:30Let the intersection element be 1 to start with,
N...Let the intersection element be 1 to start with,<br />Now, the 2 subsets could be (or can be selected by) -> C(n-1,x)*(2^n-1-x) (if x=1 it means one of the 2 subsets has only one element i.e. =1)<br />So, total no. of subsets = n*C(n-1,x)*(2^n-1-x)Grijesh Agrawalhttps://www.blogger.com/profile/18415445465697970868noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-47961051776973807402012-09-25T10:54:47.081+05:302012-09-25T10:54:47.081+05:30Agree with ur logic....but as it clearly specify t...Agree with ur logic....but as it clearly specify that we shud have exactly one common element in any 2 set... it means Eg:{1}&{2,3} both are not possible bcoz they dont have common element.<br />U can take any number 1 or 2....n.<br />for eg:{3,1},{3,2},{3},{3,4}....{3,n} = n subsets.<br />The answer is n.Shashank Gaurhttps://www.blogger.com/profile/00582297651961722369noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-70555025851150684672012-09-25T10:47:59.173+05:302012-09-25T10:47:59.173+05:30The answer is n.
Try induction:
for n=1: {1};
for ...The answer is n.<br />Try induction:<br />for n=1: {1};<br />for n=2: {1},{1,2};<br />for n=3: {1},{1,2},{1,3};<br />for n=4: {1},{1,2},{1,3},{1,4};<br />.......<br />for n=n: {1},.........{1,n);<br />Shashank Gaurhttps://www.blogger.com/profile/00582297651961722369noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-14843720946078115072012-08-29T00:52:16.932+05:302012-08-29T00:52:16.932+05:30It should be seen like this, intersection should g...It should be seen like this, intersection should give only one element so we can have 1,2,3 ...n as intersection, <br />for 1 as intersection we can have subsets: {1} {1,2} {1,3} {1,4}......{1,n} we cant have more than 2 elements in a subset other wise it would give two element by intersection with some subset out of {1,2} to {1,n}<br /><br />for 2 as intersection we can have subsets{ {2} {2,3} {2,4}......{2,n}<br /><br />so it is n+(n-1)+(n-2)+....+1 =n*(n-1)/2saurav@iitdhttps://www.blogger.com/profile/02079602412561742857noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-91785885098797306752012-08-29T00:46:35.700+05:302012-08-29T00:46:35.700+05:30it should be n*(n-1)/2it should be n*(n-1)/2saurav@iitdhttps://www.blogger.com/profile/02079602412561742857noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-37739311581523738042012-08-06T01:20:08.440+05:302012-08-06T01:20:08.440+05:30It is easy to see that the answer is n for n=2
Now...It is easy to see that the answer is n for n=2<br />Now, using induction, lets suppose that answer is k for k-set for all k <=n-1<br />So, if answer is more than n for an n-set, then removing n from each of the chosen subsets, we have two possibilities:<br />a) one of the subsets is {n} itself<br />b) none of the subsets is {n}<br />Case b) : immediately a contradiction after removal of n from each of the subsets<br />Case a) : every other subset contains {n}. Also, all the other subsets have only {n} as their intersection. So, there can be atmost n-1 more subsets. But, our supposition was that we have more than n subsets, which is proved wrong.<br /><br />So, in both of the cases a and b, we have proved that the answer is <=n for an n-set.<br />And we have an example of n subsets for every n. So, the answer is nKapil Dubeyhttps://www.blogger.com/profile/00388428302950969251noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-84922908436715943942012-06-13T10:11:41.839+05:302012-06-13T10:11:41.839+05:30It should be n, the only way this seems possible i...It should be n, the only way this seems possible is if (n-1) elements are taken in one of the subsets, and in each of the remaining subsets, the one element left out in the first subset is paired with the remaining elements of the first subset. (one by one) This makes n-1 subsets(with 2 elements each) plus the initial sub set (with n-1 elements).constantinehttps://www.blogger.com/profile/01525373399730159704noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-44060683424656264552012-06-04T19:39:42.079+05:302012-06-04T19:39:42.079+05:30The answer should be n.I agree with Karthi's l...The answer should be n.I agree with Karthi's logic and explanation.<br />@gj: You forgot the n-th element could individually forma a subset as wellAnuraag Gutgutiahttps://www.blogger.com/profile/09978408619628730485noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-60997437776543648442012-05-31T01:30:53.229+05:302012-05-31T01:30:53.229+05:30i think it's n-1.
n-1 different elements in n-...i think it's n-1.<br />n-1 different elements in n-1 different subsets while remaining 1 element with each of the n-1 subsets.gjhttps://www.blogger.com/profile/12510270934879404415noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-18624083510600084222012-04-04T21:09:56.250+05:302012-04-04T21:09:56.250+05:30n
explanation:
1 element can be chosen to shared....n<br /><br />explanation:<br />1 element can be chosen to shared.<br />then there be a maximum of n-1 disjoint sets of the left out n-1 elements, now if removed element is added to each of these sets we have n-1 subsets, the removed element itself will intersect with the rest of subsets in only one element,<br />hence the total no of subsets is n.<br /><br />Incresing the size of any of these sets decreases the number of disjoint sets available, so the number of elements in each set should be kept to bare minumum ie 1karthihttps://www.blogger.com/profile/16855378817364835421noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-41994420306179497582012-03-29T22:26:54.535+05:302012-03-29T22:26:54.535+05:30i think it is n*2^(n-1) using the same logic as ab...i think it is n*2^(n-1) using the same logic as above.javahttps://www.blogger.com/profile/16147070392349934379noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-13732458440636803052012-03-26T13:31:54.419+05:302012-03-26T13:31:54.419+05:30n*3^(n-1)
Find number of subsets such that element...n*3^(n-1)<br />Find number of subsets such that element 1 is common between them. It is equivalent to choosing 2 disjoint subsets from remaining n-1 elements which is 3^(n-1).<br />Do that for element in the set.Gibraltarhttps://www.blogger.com/profile/10155367076484523248noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-57508801872274837672012-03-08T15:39:50.213+05:302012-03-08T15:39:50.213+05:30"any 2 should intersect in exactly 1 element&..."any 2 should intersect in exactly 1 element".<br /><br />I should change my answer to C(n,2).Anujhttps://www.blogger.com/profile/12653610823760365520noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-37424844735571672592012-03-08T01:47:15.330+05:302012-03-08T01:47:15.330+05:30Any 3 element subset, say (i,j,k) cannot be in the...Any 3 element subset, say (i,j,k) cannot be in the answer, because you can remove it and include (i,j) and (j,k) instead. Same holds for subsets with 4,5,... elements.<br /><br />So the answer is C(n,2)+C(n,1)+C(n,0).Anujhttps://www.blogger.com/profile/12653610823760365520noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86923249695560318092012-03-03T23:57:51.934+05:302012-03-03T23:57:51.934+05:302^n-2 if sum of elements of subset should be n
oth...2^n-2 if sum of elements of subset should be n<br />otherwise<br /><br />n-2<br />Σ r(n-r-1)<br />r=1Ashish Mishrahttps://www.blogger.com/profile/01992700453626275637noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-75620635436164224892012-03-02T23:44:30.177+05:302012-03-02T23:44:30.177+05:30A similar approach:
The characteristic functions o...A similar approach:<br />The characteristic functions of the sets can be viewed as vectors in n dimensions (with the added restriction that all components are either 1 or 0).<br /><br />Upper bound:<br />Consider solving the problem: Given an n-dimensional space, find the largest set S of vectors such that the pairwise dot product is <i>a</i>.<br /><br />We attempt a problem reduction as follows: Choose an arbitrary vector from the set, <b>v</b>. Rotate the space such that <b>v</b> points along one of the axes, say <b>x</b>. This does not change the pairwise dot product. Let the length of <b>v</b> be <i>b</i>. Now, since the dot product of <b>v</b> with all other vectors is <i>a</i>, for any other vector <b>w</b> in S, <b> w . x </b> = <i>a / b</i>.<br />Therefore, we must now solve the problem - find the set S' of vectors in <i>n - 1</i> dimensions such that the pairwise dot product is a - a/ b.<br /><br />This problem makes sense when a > a / b (This is always true). In the best case, we can assume that the dot product does not reduce in each step. Since each step reduces the number of dimensions by 1, |S| is upper bounded by <i>n</i>.<br /><br />Lower bound: Example - The vectors <br />1 0 0 0 ...<br />1 1 0 0 0 ...<br />1 0 1 0 0 ...<br />1 0 0 1 0 ...<br />i.e.<br />x_0 = 1, x_i (i > 0) = 0;<br />x_0 = 1, x_i (unique i) = 1;<br /><br />satisfy the conditions. This set is of size n.A Rustlehttps://www.blogger.com/profile/02337350008237724548noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-12838552655960054302012-02-27T14:25:17.359+05:302012-02-27T14:25:17.359+05:30For each set in the family, let v be a n-length bi...For each set in the family, let v be a n-length binary vector that indicates which elements of {1,2,...,n} belong to that set. Then, the intersection criterion becomes v_i^T v_j = 1. Let K be the largest collection of sets satisfying this criterion. If we can find the rank of {v_1,v_2,...,v_K} as a function of K, this will have to be upper bounded by n and we will have an upper bound on K. <br /><br />Some experimentation shows that K=n is possible. Take the family to be {{1,2,3,...,n-1},{1,n},{2,n},...{n-1,n}}. For n=2, it is easy to see that we can't do better than K=2. This suggests that we should try to prove that the vectors v1,v2...,v_K are linearly independent.<br /><br />Computing the Gram determinant of these basis vectors is easy. The diagonal elements are the cardinalities of the sets in the family and all off-diagonals are 1. The determinant of this matrix is P + \sum_{i=1}^n P/(|A_i|-1) where P = \prod_{i=1}^n (|A_i|-1). Thus, as long as the sets are not singletons, the vectors will be linearly independent. QED.<br /><br />Coming up with a non-easy example (other than the example above and {{1,n},{2,n}...{n-1,n},{n}}) of such families is an interesting exercise in its own right.Dinesh Krithivasanhttps://www.blogger.com/profile/13437484936096983201noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-62201356837836695552012-02-25T13:47:35.838+05:302012-02-25T13:47:35.838+05:30Is the set A itself is excluded from the set of th...Is the set A itself is excluded from the set of those subsets? Because the answer will be different in that case.Rakeshhttps://www.blogger.com/profile/07043855126262381716noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-52845578745611762692012-02-25T13:24:37.465+05:302012-02-25T13:24:37.465+05:30is it 2 raised to n-1??
because u can include one ...is it 2 raised to n-1??<br />because u can include one element in all the sets and then u have n-1 elements left , which can have 2^n-1 subsets....Amithttps://www.blogger.com/profile/03939988723575403670noreply@blogger.com