tag:blogger.com,1999:blog-4115025577315673827.post9033102000438445927..comments2020-07-30T14:44:21.349+05:30Comments on CSE Blog - quant, math, computer science puzzles: Discrete Mathematics Problem - Grouping StudentsPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-4115025577315673827.post-65508697403470919782019-09-22T07:16:10.390+05:302019-09-22T07:16:10.390+05:30try for n=4, this is not true try for n=4, this is not true adhityahttps://www.blogger.com/profile/07410233231398685654noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-73775358512889707932019-09-22T07:15:47.959+05:302019-09-22T07:15:47.959+05:30try for n=4,this is not truetry for n=4,this is not trueadhityahttps://www.blogger.com/profile/07410233231398685654noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-82762546932419145922013-12-31T16:34:59.708+05:302013-12-31T16:34:59.708+05:30The answer is (n+1).
Example: take n = 3. And you...The answer is (n+1). <br />Example: take n = 3. And you form three groups for 9 students. Let they are numbered from 1, 2,..., 9.<br />The first group. Let call it Grouping A.<br />1 2 3 | 4 5 6 | 7 8 9<br />Now you can just use the positions of the students. Suppose you put a difference of 0 positions. That means you take first student from each of the Grouping A to form the first group. Then you take second student from each group for the second group. And so for the third. This will give:<br />1 4 7 | 2 5 8 | 3 6 9<br />Now, you take the difference of 1 position. Now, to create the first group you take first student from first group of Grouping A, then second student from the second group of grouping A, then the third student from the third group of Grouping A. This will give:<br />1 5 9 | 2 6 7 | 3 4 8<br />Now, you put a difference of 2 positions. This will give<br />1 6 8 | 2 4 9 | 3 5 7<br />In this way you have 4 groupings.<br /><br />So, for generalized case you can put difference of 0 ,1 , 2.... till (n-1) after you form the Grouping A like done in the example.<br />So, the answer would be (n+1).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-27377138913684394862013-11-11T03:40:57.505+05:302013-11-11T03:40:57.505+05:30For 6*6 students, how do you do this for 5 days? For 6*6 students, how do you do this for 5 days? Mike Earnesthttps://www.blogger.com/profile/10706561663990058978noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-14684925778358349342013-10-26T14:38:35.702+05:302013-10-26T14:38:35.702+05:30N+1-(no. of factors of N except 1 and N)N+1-(no. of factors of N except 1 and N)Anonymoushttps://www.blogger.com/profile/07080711391743702683noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-74350415162236568512013-10-24T00:09:20.175+05:302013-10-24T00:09:20.175+05:30This comment has been removed by the author.Mike Earnesthttps://www.blogger.com/profile/10706561663990058978noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-9458652195033543372013-10-24T00:06:15.269+05:302013-10-24T00:06:15.269+05:30For general N, this the number of days you can do ...For general N, this the number of days you can do this is equal to 2 plus the maximum number of mutually orthogonal Latin Squares of order N. When N is any prime power, this means we can do this for N+1 days, but for most N, this is a hard open problem.Mike Earnesthttps://www.blogger.com/profile/10706561663990058978noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-39986090167330770812013-10-23T14:30:05.005+05:302013-10-23T14:30:05.005+05:30Only N+1 days as if there are four students ABCB, ...Only N+1 days as if there are four students ABCB, then only groups possible is<br />{AB,CD}, {AC,BD}, {AD,BC} i.e. 2+1=3 days. if there are 9 students 1,2,3,4,5,6,7,8,9<br />then possible configuration will be <br />[123,456,789],<br />[147,258,369],<br />[159,357,168],<br />[249,267,384]<br />i.e.3+1=4 days and so on,<br />so for N^2 students making N group each day having N students in each group without having 2 students in same group gain we can adjust only for N+1 daysRaaJhttps://www.blogger.com/profile/14602621039520518468noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-71741926414295436862013-10-23T12:51:59.416+05:302013-10-23T12:51:59.416+05:3018 days...
For N^2 students, number of days we can...18 days...<br />For N^2 students, number of days we can do this is (N+1).Anonymoushttps://www.blogger.com/profile/06036546577349442982noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-30324092193045592592013-10-23T10:37:35.636+05:302013-10-23T10:37:35.636+05:30N+1;
Note that, A guy finishes his grouping stin...N+1; <br /><br />Note that, A guy finishes his grouping stint with N-1 students in each day and there are N^2-1 students other than the guy himself. So there are maximum (N^2-1)/(N-1) = N+1 days are possible before he exhaust grouping with all the students. Now, you can show N+1 is achievable as follows : <br /><br />First day <br />1,2,3<br />4,5,6<br />7,8,9<br />2nd day (transpose)<br />1,4,7<br />2,5,8<br />3,6,9<br />Now in 3rd day, you group members diagonally from previous one ( cyclically) <br />(for example if you notice main diagonal is [1,5,9] , you take it, similarly for [2,6 and wrapped around to 7] <br />1,5,9<br />2,6,7<br />3,4,8<br /><br />Group elements diagonally again<br />1,6,8<br />2,4,9<br />3,5,7<br /><br />So there will be initial matrix, its transpose with N possible diagonal rotation, hence total N+1 days possible.Piyushhttps://www.blogger.com/profile/03036531175753773520noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-55774416799915856212013-10-23T10:34:30.088+05:302013-10-23T10:34:30.088+05:3018 days. Each person sees 16 different people on e...18 days. Each person sees 16 different people on each day, so 288 different people in 18 days. In the 19th day he will see more than 288, so it's not possible. <br />Groups are numbered 0,1,2,...16. People are numbered 0,1,...288.<br />On day 0, person i is in group floor(i/17).<br />On day j (for j=1,2,...17), group k contains persons 17m+ [k+(m(j-1))%17] for m=0,1,2,...16.The % operator is modulo division.<br />We need to show: 1) On each day, each group has 17 distinct people and each pair of groups is disjoint. 2) Each person is grouped with every other person exactly once.<br />To show 1): Suppose 17m+ [k+(m(j-1))%17] = 17m'+[k'+(m'(j-1))%17]<br />Then m'=m and k'=k. This shows that each person is distinct on a particular day.<br />To show 2): Suppose that the m1_th person and m2_th person in group k of day j also occur together in group k' of day j' as the m1'-th and m2'-th persons respectively. Then<br />17m1+ [k+(m1(j-1))%17] = 17m1'+[k'+(m1'(j'-1))%17] and<br />17m2+ [k+(m2(j-1))%17] = 17m1'+[k'+(m2'(j'-1))%17]<br />Therefore, m1=m1',<br />k+m1(j-1) = k'+m1(j'-1) (mod 17) and<br />k+m2(j-1) = k'+m2(j'-1) (mod 17) <br />Subtracting the last 2 congruences gives<br />(m1-m2)(j-1)=(m1-m2)(j'-1) (mod 17)<br />thus 17 divides (m1-m2)(j-j')<br />but 17 is prime, and |m1-m2|, |j-j'| are both between 1 and 16. Hence, it's a contradiction.<br /><br />The approach works for n^2 people when n is prime. I am not sure if it can be generalized for composite n.<br />GoKuhttps://www.blogger.com/profile/05674743004147477362noreply@blogger.com