# 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.

Message body

 Emoticons View more Emoticons
 [quote="Amb*"]Maybe this should be in Visitor Submitted Puzzles?[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 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
 Topic review
Author Message
Zahariel
Posted: Sat May 16, 2009 2:04 am    Post subject: 1

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.
L'lanmal
Posted: Sat May 16, 2009 1:15 am    Post subject: 0

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.
Pablo
Posted: Wed May 06, 2009 2:30 pm    Post subject: -1

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
Antrax
Posted: Tue Apr 21, 2009 10:25 am    Post subject: -2

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.
Amb*
Posted: Tue Apr 21, 2009 6:05 am    Post subject: -3

Maybe this should be in Visitor Submitted Puzzles?
bendykst
Posted: Sat Apr 18, 2009 8:32 am    Post subject: -4

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?
bendykst
Posted: Sat Apr 18, 2009 8:22 am    Post subject: -5

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.