1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is this problem solvable analytically?

  1. Apr 30, 2007 #1
    Suppose we have a row of n squares. A device is made such as it prints on the squares. This device can print every square individually, or "copy" m squares and "paste" them on the rest of the row. For example, the device could print first 5 squares of a 80 squares row, individually, then take these 5 squares and paste them 15 times on the remaining 75 squares. This gives in total of 5 + 15 = 20 printings. Now, suppose we have any natural number of squares in the row. If we chose to print m squares before pasting them on the rest of the row, the number of printings k is

    [tex] k = m + \left \lceil \frac{n - m}{m} \right \rceil [/tex]

    Now since this is a discrete function, is there a way to analytically determine which value m will give the least number of printings?
    Last edited: Apr 30, 2007
  2. jcsd
  3. Apr 30, 2007 #2
    I have strong evidence that the minimums of

    [tex]m + \left \lceil \frac{n - m}{m} \right \rceil[/tex]

    coincide with the minimum of

    [tex]m + \frac{n - m}{m}[/tex]

    With [itex]m[/itex] as a continuous variable, this is easy to analyze. Now we just have to show that [itex]m[/itex] that achieves the minimum value of this function gives a minimizing [itex]m[/itex] for the discrete case as well (by rounding, ceiling, or floor, I don't know).
  4. Apr 30, 2007 #3
    “k” is the number of printings. “n” is a constant the total number of squares. For a given value of “n” you want to know for what value of “m” is ”k” lowest. “k” is a function of “m” so if one were to have a graph of that one would look for the lowest point on that graph, or its minimum. The analytic technique you seek is the derivative. Rewriting your equation to:

    [tex] \frac{\delta k}{\delta m} = 1 - \frac{n}{m^2} + 0 = 0 \mbox{ at a mimimum (or maximum)} [/tex]
    [tex] m =< \sqrt{n}[/tex]
    Last edited: Apr 30, 2007
  5. Apr 30, 2007 #4
    Well, Moo Of Doom, I did try to go in that direction... we get [tex]\sqrt{n}[/tex] as the minimum. Now, if you were dealing with the continuous function, we would have to compare the values of ceiling of n and the floor and chose the lowest. Now if we have [tex]a < b < \sqrt{n}[/tex], we need to show that

    [tex]a + \left \lceil \frac{n - a}{a} \right \rceil > b + \left \lceil \frac{n - b}{b} \right \rceil [/tex]

    and for [tex]a > b > \sqrt{n}[/tex]

    [tex]a + \left \lceil \frac{n - a}{a} \right \rceil > b + \left \lceil \frac{n - b}{b} \right \rceil [/tex]

    Edit; NanoTec: there was never any question on weather or not we needed to make use of differentiation here... the problem here is that we're dealing with a discrete function and not a continuous one...
    Last edited: Apr 30, 2007
  6. Apr 30, 2007 #5
    I don't think there is an analytical solution. but it is quite the same except that you need to check a couple values.

    you can rewrite things in terms of fractional function... ie {x}= fractional part of x, you'll get
    [tex]k\ge m+\frac{n}{m} \ge 2\sqrt{n}[/tex]

    find m that minimizes [tex]m+\frac{n}{m}[/tex]
    find a couple integers that are near that value of m. find the k values for them and compare. the min of k should occur around this neighborhood since the fractional part of anything is less than 1. whenever you get a difference in k (from the min) that is greater than 1 when you vary m, you are done (in other words, the fractional part will never make up for the difference of 1).
    Last edited: May 1, 2007
  7. May 1, 2007 #6
    This is related to the theory of encoding strings of numbers in the most compact manner. You're asking for an efficient way of encoding a binary number- taking into account that there could be repeats in the string.
  8. May 1, 2007 #7
    Tim Lou: Your expression of k is only valid for non-integer n/m. It is the same as the expression

    [tex] k = m + \left \lfloor \frac{n}{m} \right \rfloor [/tex]

    Which clearly shows that for an integer n/m, we get a different expression than what originally intended.
  9. May 1, 2007 #8
    yes, you are correct, for that we can let {x}=fraction part of x when x is not an integer, and =1 when x is an integer. still {x} is bounded by 1.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for problem solvable analytically
I A problem in combinatorics
B Optimisation problem