Is this problem solvable analytically?

[Werg22]

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

$$k = m + \left \lceil \frac{n - m}{m} \right \rceil$$

Now since this is a discrete function, is there a way to analytically determine which value m will give the least number of printings?

 

[Moo Of Doom]

I have strong evidence that the minimums of

$$m + \left \lceil \frac{n - m}{m} \right \rceil$$

coincide with the minimum of

$$m + \frac{n - m}{m}$$

With $m$ as a continuous variable, this is easy to analyze. Now we just have to show that $m$ that achieves the minimum value of this function gives a minimizing $m$ for the discrete case as well (by rounding, ceiling, or floor, I don't know).

 

[NanoTec]

“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:

$$k=m+\frac{n}{m}-1$$
$$\frac{\delta k}{\delta m} = 1 - \frac{n}{m^2} + 0 = 0 \mbox{ at a mimimum (or maximum)}$$
$$m =< \sqrt{n}$$

 

[Werg22]

Well, Moo Of Doom, I did try to go in that direction... we get $$\sqrt{n}$$ 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 $$a < b < \sqrt{n}$$, we need to show that$$a + \left \lceil \frac{n - a}{a} \right \rceil > b + \left \lceil \frac{n - b}{b} \right \rceil$$

and for $$a > b > \sqrt{n}$$$$a + \left \lceil \frac{n - a}{a} \right \rceil > b + \left \lceil \frac{n - b}{b} \right \rceil$$
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...

 

[tim_lou]

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
$$k=m+\frac{n}{m}-\left\{\frac{n}{m}\right\}$$
so
$$k\ge m+\frac{n}{m} \ge 2\sqrt{n}$$

find m that minimizes $$m+\frac{n}{m}$$
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).

 

[christianjb]

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.

 

[Werg22]

Tim Lou: Your expression of k is only valid for non-integer n/m. It is the same as the expression

$$k = m + \left \lfloor \frac{n}{m} \right \rfloor$$

Which clearly shows that for an integer n/m, we get a different expression than what originally intended.

 

[tim_lou]

Tim Lou: Your expression of k is only valid for non-integer n/m. It is the same as the expression

$$k = m + \left \lfloor \frac{n}{m} \right \rfloor$$

Which clearly shows that for an integer n/m, we get a different expression than what originally intended.

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.