tag:blogger.com,1999:blog-4115025577315673827.post7757250044193865055..comments2020-01-23T12:35:45.593+05:30Comments on CSE Blog - quant, math, computer science puzzles: Buying DimsumsPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-4115025577315673827.post-20035447993221142332018-05-14T22:32:46.189+05:302018-05-14T22:32:46.189+05:30This should be 11 for 7 and 3. The generalized ans...This should be 11 for 7 and 3. The generalized answer for co-prime D and u would be x*y-(x+y)Ayush Tulsyanhttps://www.blogger.com/profile/10734366869835537064noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-38232130054725971402018-01-05T16:03:59.906+05:302018-01-05T16:03:59.906+05:30ans is 11.
ans is 11.<br />Unknownhttps://www.blogger.com/profile/15954789346628913360noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-83202253711385129312017-12-12T18:57:36.729+05:302017-12-12T18:57:36.729+05:30pq - (p+q)pq - (p+q)Unknownhttps://www.blogger.com/profile/07248089303593155882noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-1345804433391939122017-11-25T04:46:14.468+05:302017-11-25T04:46:14.468+05:3011.
Every other number can be expressed as 3k, 3k+...11.<br />Every other number can be expressed as 3k, 3k+7 or 3k+14 (and so on).Riya Guptahttps://www.blogger.com/profile/03460580968424082993noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-90067239665726062242017-11-21T21:19:47.068+05:302017-11-21T21:19:47.068+05:301111Brajraj Laddhahttps://www.blogger.com/profile/11545868892700264527noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-43008521944623573082017-11-20T14:07:35.366+05:302017-11-20T14:07:35.366+05:30Lets say X is the number of dimsums which i can...Lets say X is the number of dimsums which i can't buy, but I can buy (X+i) dimsums for every possible integer i. <br />Hence, X+1, X+2, X+3,...etc should all be of the form 7x+3y. <br />Now lets say X+1 is of the form 7x+3y. Then you should be able to get X+2 by either adding/removing 7s or 3s. <br />Now, X+3, X+6 and X+7 can easily be formed using 7s and 3s since X is of the form 7x + 3y. All I need to know is how do I add 1,2,4,5, to a number by adding/subtracting 3s and/or 7s. <br /><br />So if I need a 1, I add a 7 and remove a couple of 3s. i.e. 7 - 2(3)<br />Similarly, <br />1 = 7 - 2(3) <br />2 = 3(3) - 7 <br />4 = 7 - 3 <br />5 = 3(4) - 7 <br /><br />So if you are going from X to X+1 or X+2 or X+4 or X+5, then you need at least two 3s and at least one 7, because if you have them you can subtract them from X and add a few 7s and 3s (which are available to you anyway) and get your desired numbers. <br />Hence X = 2(3) + 7(1) = 13 <br />hence the number before 13 which can't be formed using 7s and 3s should be the answer. <br /><br />13 = 7+ 2(3) <br />12 = 3(4) <br />11 = can't be formed using 3s and/or 7s <br />Hence the answer should be 11. Nawroz Minsariahttps://www.blogger.com/profile/05536598744895514839noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-15167350072596961682017-11-20T13:26:59.669+05:302017-11-20T13:26:59.669+05:30Lets say X is the number of dimsums which i can...Lets say X is the number of dimsums which i can't buy, but I can buy (X+i) dimsums for every possible integer i. <br />Hence, X+1, X+2, X+3,...etc should all be of the form 7x+3y. <br />Now lets say X+1 is of the form 7x+3y. Then you should be able to get X+2 by either adding/removing 7s or 3s. <br />Now, X+3, X+6 and X+7 can easily be formed using 7s and 3s since X is of the form 7x + 3y. All I need to know is how do I add 1,2,4,5, to a number by adding/subtracting 3s and/or 7s. <br /><br />So if I need a 1, I add a 7 and remove a couple of 3s. i.e. 7 - 2(3)<br />Similarly, <br />1 = 7 - 2(3) <br />2 = 3(3) - 7 <br />4 = 7 - 3 <br />5 = 7(2) - 3(3) <br /><br />So if you are going from X to X+1 or X+2 or X+4 or X+5, then you need at least three 3s and at least one 7, because if you have them you can subtract them from X and add a few 7s and 3s (which are available to you anyway) and get your desired numbers. <br />Hence X = 3(3) + 7(1) = 16 <br />hence the number before 16 which can't be formed using 7s and 3s should be the answer. <br />15= 5(3) <br />14 = 2(7)<br />13 = 7+ 2(3) <br />12 = 3(4) <br />11 = ? <br />Hence the answer should be 11. Unknownhttps://www.blogger.com/profile/05536598744895514839noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-13502907825043678692017-11-18T14:45:54.466+05:302017-11-18T14:45:54.466+05:30This is the Frobenius Problem. The general solutio...This is the Frobenius Problem. The general solution for p,q is pq - p - q.<br />Sahil Aggarwalhttps://www.blogger.com/profile/06659414117930705341noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-15637771566078224902017-11-03T16:43:17.536+05:302017-11-03T16:43:17.536+05:30Where is the answer sir.Where is the answer sir.Winsant surathttps://www.blogger.com/profile/02474802599380470939noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-85281218022550688212017-10-13T16:53:12.937+05:302017-10-13T16:53:12.937+05:301111shramanhttps://www.blogger.com/profile/16399296865457066167noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-2025134165323727622017-09-25T13:25:20.864+05:302017-09-25T13:25:20.864+05:3011?11?Anonhttps://www.blogger.com/profile/00259617428339071518noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-36368669405798790862017-09-12T22:02:06.099+05:302017-09-12T22:02:06.099+05:301111Brian Gladmanhttps://www.blogger.com/profile/10418140796735474648noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-46368319023467324562017-08-30T17:47:14.975+05:302017-08-30T17:47:14.975+05:30i'm not sure if i understand this correctly-- ...i'm not sure if i understand this correctly-- but i am going to assume 'relatively prime' means that for some p, q they are consecutive prime numbers where p < q. if this is the case, i believe that the maximum number that person cannot buy using p, q is some number r = q + 1, assuming p =/=2.<br /><br />if p > 2, then we know that the set of possible values for p, q are all odd numbers. Also, with (p < q), the maximum number of buys that we can buy can only be made with linear combinations of (xp, yq) where x, y are the multiplicative factor. <br />Aside, given that p, q are odd, and if p is not 2, p + q > q + 1; and q + 1 is even number.. So basically the even number that is larger than q cannot be represented using p, q; and the smallest number that is larger than q is q+1. I know this is not rigorous but just wanted to see if this is the right approach. 0https://www.blogger.com/profile/07235895876337894550noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-2629463956255407012017-08-17T16:07:09.864+05:302017-08-17T16:07:09.864+05:30Is the answer 11?
Because working with mod 7:
0,3,...Is the answer 11?<br />Because working with mod 7:<br />0,3,6 are done.<br />For x modulo 1, we need to subtract 14 from biggest multiple of 7 less than x...i.e. x>=15 and x=1 mod 7 dimsums can be bought.<br />Similarly; x=2 mod 7 need to subtract 7; x=4 mod 7 need to subtract 14 and lastly x=5 mod 7 need to subtract 7. <br />Unknownhttps://www.blogger.com/profile/08752576015501186463noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-42162827822114758522017-08-06T11:47:17.695+05:302017-08-06T11:47:17.695+05:30pq-p-qpq-p-q@N$#ULhttps://www.blogger.com/profile/10712915892156367401noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-76232217443667762232017-06-10T10:28:30.802+05:302017-06-10T10:28:30.802+05:3088SaJaL kUmAr ???https://www.blogger.com/profile/15185278804081941865noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-91522294873538353212017-05-25T10:35:37.956+05:302017-05-25T10:35:37.956+05:301111Unknownhttps://www.blogger.com/profile/08672802212568973456noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-33961519198252598162017-05-11T09:57:48.022+05:302017-05-11T09:57:48.022+05:3011
3,6,9,12,15,18 ... all these can be ordered.
7...11<br /><br />3,6,9,12,15,18 ... all these can be ordered.<br />7,10,13,16,19... all these can be ordered.<br />14,17,20,23,... all these can be ordered.<br /><br />So, 11 is the one which can't be ordered.<br /><br />So, basic idea is to see the smallest number and try to find out all possible modular can be generated. As soon as this is achieved, we can get the largest number which can't be created.<br /><br />Thanks.VARUN PAHWAhttps://www.blogger.com/profile/06641326068253674149noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-57247703961181023542017-03-15T14:52:28.616+05:302017-03-15T14:52:28.616+05:30pq-p-q is the greatest such number. Proof:
WLOG a...pq-p-q is the greatest such number. Proof:<br /><br />WLOG assume q > p. Say p mod q = r. First we will prove that given any x > pq-p-q, there exists a >=0, b>= 0 s.t. ap + bq = x. We prove this in two parts:<br /><br />a) consider x >= pq-q = q(p-1). Say x mod p = s. Since gcd(p,q) = gcd(r,q) = 1, there exists some t with 0 <= t <= p-1 such that r*t = s mod p. Now, x >= q(p-1) >= qt, and x-qt = 0 mod p, thus, x-qt = pb for b >= 0.<br /><br />b) consider x > pq-p-q but < pq-q. In this case, note that we can tighten the bound of t to be 0 <= t <= p-2, since x != r(p-1) mod p (both the limits of q(p-1)-p and q(p-1) are excluded). Thus, x > pq-p-q = q(p-1) - p >= q(t+1) - p = qt + q-p. Thus, x-qt > q-p > 0, and x-qt = 0 mod p, which implies that x-qt = pb with b > 0.<br /><br />Finally, to show that pq-p-q can't be expressed as ap + bq, note that pq-p-q mod p = q(p-1) mod p. Also ap + bq = bq mod p. Thus, bq = q(p-1) mod p, which means b = p-1 mod p (since q is coprime to p). Any such b is >= p-1, but pq-p-q < q(p-1), thus it can't be expressed as ap + bq. QED.<br /><br />In the given specific case, we have the minimum such number as 3*7-3-7 = 11.Subhasishttps://www.blogger.com/profile/04740088350640659019noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-26124210115639299672017-03-13T10:27:29.770+05:302017-03-13T10:27:29.770+05:30For (7,3) combination the answer is 11. In general...For (7,3) combination the answer is 11. In general, it is pq-(P+Q)Vamsi Vintahttps://www.blogger.com/profile/12508241583879594008noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-35537376943990260722017-03-11T07:05:08.424+05:302017-03-11T07:05:08.424+05:30For (7,3) combination, the answer is 11. In genera...For (7,3) combination, the answer is 11. In general it is pq - (P+Q)Unknownhttps://www.blogger.com/profile/12508241583879594008noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-58683293763245017232017-03-10T11:53:52.035+05:302017-03-10T11:53:52.035+05:303*n+1
= 3(n-2) + 6 + 1
= 3(n-2) + 7
if n >= 2...3*n+1<br />= 3(n-2) + 6 + 1<br />= 3(n-2) + 7<br /><br />if n >= 2, 3*n + 1 will always be comb of 3 and 7<br />max num of such type - 5<br /><br />3*n + 2<br />= 3*(n-4) + 2*7<br /><br />if n >= 4, 3*n + 2 will always be comb of 3 and 7<br />max num of such type - 11<br /><br />Still thinking about generalization to p and qSumit Bhagwanihttps://www.blogger.com/profile/00094235259094340406noreply@blogger.com