wu :: forums « wu :: forums - Minimizing sum of distances while numbering a net » Welcome, Guest. Please Login or Register. Nov 28th, 2024, 9:10pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    medium (Moderators: Eigenray, towr, ThudnBlunder, Grimbal, william wu, SMQ, Icarus)    Minimizing sum of distances while numbering a net « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Minimizing sum of distances while numbering a net  (Read 588 times) Hippo Uberpuzzler     Gender: Posts: 919 Minimizing sum of distances while numbering a net   « on: Nov 25th, 2007, 8:19am » Quote Modify Sorry, if the problem was presented here or does not belong here... (it has nontrivial but easy surprising solution but I cannot give a trivial formulation).   Suppose we have rectangle of  (n-1)x(m-1) squares. Their vertices and edges are what interests us.   Number vertices with 1,2,...,m.n in such a way the sum for all (m.(n-1)+n.(m-1)) edges of the absolute value of the difference of their vertex numbers is minimal. « Last Edit: Nov 25th, 2007, 8:20am by Hippo » IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Minimizing sum of distances while numbering a   « Reply #1 on: Nov 25th, 2007, 9:09am » Quote Modify It seems to me that a simple numbering by row and column is best.  take the shortest side first. IP Logged Hippo Uberpuzzler     Gender: Posts: 919 Re: Minimizing sum of distances while numbering a   « Reply #2 on: Nov 25th, 2007, 10:30am » Quote Modify on Nov 25th, 2007, 9:09am, Grimbal wrote: It seems to me that a simple numbering by row and column is best.  take the shortest side first. This is the trivial, but not the best solution « Last Edit: Nov 25th, 2007, 10:32am by Hippo » IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Minimizing sum of distances while numbering a   « Reply #3 on: Nov 25th, 2007, 11:38am » Quote Modify I am curious to see how.   For instance, with 3x4 nodes:  1  2  3  4  5  6  7  8  9 10 11 12 There are 8 horizontal links with distance 1 plus 9 vertical links with distance 3.  That makes a best sum of of 8+27 = 35.  Can you do less? IP Logged Hippo Uberpuzzler     Gender: Posts: 919 Re: Minimizing sum of distances while numbering a   « Reply #4 on: Nov 26th, 2007, 12:38am » Quote Modify OK, your solution is OK upto 6xm, (n<m). Try thinking about 7xm.   Oops, my memory ... OK only upto 4xm. « Last Edit: Nov 26th, 2007, 3:32am by Hippo » IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board