# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
bendykst
Icarian Member

 Posted: Sat Apr 18, 2009 8:22 am    Post subject: 1 I have been thinking about this for some time, but I can't find an answer. I'm hoping someone smarter than me will be able to figure this out. ======================= From Wikipedia: In the Chinese remainder theorem, there exists an integer x which is the solution of the system of congruences: % = (modulus) x%n1 = a1%n1 x%n2 = a2%n2 ... x%nk = ak%nk for positive pairwise coprime integers {n1...nk} and positive integers {a1..ak}. ================================= There are infinitely many solutions for each system, but for our purposes, let x be the smallest positive integer which solves the system. So, here's the puzzle: Say instead of a single integer a1 or a2, we have a set of integers, so that each n has an associated set of integers. From this we generate a set of solutions, picking one integer from each set for each n. I.E. x%3 = { (1), 2} %3 x%5 = { 3, (4) } %5 x%7 = { (1), 3, 5 } %7 Gives x=64 while x%3 = { 1, (2)} %3 x%5 = { 3, (4) } %5 x%7 = { 1, 3, (5)} %7 Gives x=89 Is there an efficient way to find the smallest x? We could generate all the solutions and do a search, but this could take until the heat death of the universe for some applications.
bendykst
Icarian Member

 Posted: Sat Apr 18, 2009 8:32 am    Post subject: 2 Related puzzle, say we have a structure as described above, a list of n's with associated sets. We partition this into two new structures with roughly the same number of n's. Is there an efficient way to find solutions common to both sets?
Amb*
Guest

 Posted: Tue Apr 21, 2009 6:05 am    Post subject: 3 Maybe this should be in Visitor Submitted Puzzles?
Antrax
ESL Student

 Posted: Tue Apr 21, 2009 10:25 am    Post subject: 4 It's not really a puzzle, it's just a question about mathematics. I'll give it some thought later, I looked at it yesterday but I was too tired to make any progress._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
Pablo
Never Draws a Blank

Posted: Wed May 06, 2009 2:30 pm    Post subject: 5

 Antrax wrote: It's not really a puzzle, it's just a question about mathematics. I'll give it some thought later, I looked at it yesterday but I was too tired to make any progress.

Me too. Well, I wasn't too tired before I looked at it, but I was after I looked at ........zzzzzzzzzzz
L'lanmal
Daedalian Member

Posted: Sat May 16, 2009 1:15 am    Post subject: 6

 bendykst wrote: Related puzzle, say we have a structure as described above, a list of n's with associated sets. We partition this into two new structures with roughly the same number of n's. Is there an efficient way to find solutions common to both sets?

I am confused by your seeming to use "set" to mean both a collection of integers, and a collection of sets. But if I'm reading this right, solutions common to the partitioned listings are the same as solutions to the original listing.

Worst case on the size on the size of the sets, you can use a seive method to find all solutions and take the smallest.
e.g.
x%3 = { 1, 2} %3
x%5 = { 3, 4 } %5
x%7 = { 1, 3, 5 } %7

 Code: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 . . . 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105

Cross out the columns corresponding to the compliments of your choices. (Columns 3, 6, 9, 12, 15 since they contain all 0 mod 3. Columns 1, 2, 5, 6, 7, 10, 11, 12, 15 since they contain all 1, 2, or 5 mod 5. Then cross out all numbers that are 0, 2, 4, 6 mod 7.)

The remaining numbers + 105*n are all solutions to your problem, take the smallest. (Here, 8.)

Undoubtly not the fastest computational way to a single solution, but it has the advantage that as your sets increase in size, the problem becomes less complex, rather than more.
Zahariel
Daedalian Member

 Posted: Sat May 16, 2009 2:04 am    Post subject: 7 If we take N as the product of n1 through nk, L'lanmal's solution uses Theta(N) space and O(Nk) time (but this isn't a very tight bound on time unless the ai are very small). I think k is at worst proportional to log(n), but I don't remember how to prove it. The cartesian product method of constructing all the solutions and then picking the smallest one has worst case time behavior approximately O(N*k*log 2 (N)), since solving a CRT problem is O(k*log 2 (N)) (I had to look this up, it's equal to running Euclid's algorithm k times) and you're doing it a number of times equal to the product of the sizes of the ai, which might be arbitrarily close to N but normally isn't. So L'lanmal wins there in the worst case. However, this solution only uses O(k) space if that's important, which might as well be constant since the problem statement uses more than that in general. Basically L'lanmal's solution is clearly better if the ai are relatively large (compared to ni), but if you know (from real-world domain knowledge) that each ai is approximately a constant size c rather than proportional to ni then the cartesian product algorithm gets O(kc k log 2 (N)), which is much better in addition to not taking all the space in the universe. (L'lanmal's still has pretty much O(N) behavior even if you know that the ai are usually all of [ni] except for a constant number of elements, so that still blows.) I'm not sure if there's another solution that beats both of them, but I sort of doubt it. This looks like a typical time/space tradeoff. Sieve methods are space-hungry, but have very very reliable time behavior, whereas the cartesian product method uses practically no space but might take all the time ever in the worst case. A conceivably better method might just be linear search. This takes essentially no space and O(Nk*log(N)) time, but if the ai are very large you're likely to find a solution a lot quicker than that. Sometimes the simple solutions are the best. Actually, I'm pretty sure you can't do better than this in the general case, but the cartesian product is cheaper if the sets are always very small. Note: I'm doing all these analyses in my head, so if I blew it, sorry. I believe the only gratuitous approximation I'm making is rounding log(nk) up to log(N), but that's fine for figuring out an O bound anyway.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAnonymousAntraxbendykstL'lanmalPabloZahariel Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum