Least amount of terms for sum.

[martix]

I was trying to design some GUI for a tool I'm making and I noticed there's a hidden math problem somewhere in there. Not being one to let the opportunity slide, I decided it's worth exploring.

Basically there's 3 buttons that add to a variable.
What are the best values to put on those buttons so any number up to 100 can be made with the least amount of clicks.

Only I don't know how to approach this systematically. Best I got is intuition at this point. Or the brute-force approach.

 

[1MileCrash]

I don't think there is an answer to the question as posed.

You want every number to be possible, up to 100, with the least number of clicks, but no solution will have the fewest clicks for every number.

So can it be clarified? Where do you want the fewest clicks to occur? For a random number maybe? (I think that can be solved)

If we go with the random number idea, I think it can be looked at as follows:

#1.) One button must be 1
#2.) If the two other buttons are dubbed X and Y, the optimal value for X and Y are the values such that the set {s | s is expressible as nX + k or lY + m} is equal to [1,100] for the minimum values of n and l (k and m are in the interval [0,9]…

But I am just thinking out loud, this may be wrong but it is what my intuition says. Kudos for the cool question!

 

[martix]

That much is obvious, it will vary. The question was, what's the set of numbers which will produce the least average clicks over 1-100.

 

[KenJackson]

... the set {s | s is expressible as nX + k or lY + m} ...

Shouldn't that be k + nX + mY?
That is, k clicks of '1' plus n clicks of X plus m clicks of Y, where the sum k+n+m is minimized.

On an unrelated note, I always find it interesting that people so quickly gravitate toward clicking the mouse when pushing a key seems easier.

 

[1MileCrash]

http://math.stackexchange.com/questions/645317/3-incrementing-buttons-optimal-value

I hope the OP doesn't mind, but I posted this question on Math.SE because I was so interested in seeing a nice solution.

Someone wrote a program and included a chart, and explained the results.

For our specific case [1,100], his finding was (1,12,19), which gives about an average of 5 clicks.

There was also a remark about a connection to the Fibonacci numbers (woah!) in that the two remaining numbers were likely to be adjacent Fibonacci numbers, and that he would "not be surprised" if the ratio of the two remaining buttons approached phi as we considered bigger and bigger [1,*] intervals. That text has been removed, I'm not sure if it was retracted for being wrong, or just removed for some other reason, but if that's true, this is an even cooler problem!

Shouldn't that be k + nX + mY?
That is, k clicks of '1' plus n clicks of X plus m clicks of Y, where the sum k+n+m is minimized.

On an unrelated note, I always find it interesting that people so quickly gravitate toward clicking the mouse when pushing a key seems easier.

Yes, you are right, both of the other numbers can be pressed for a value, not sure what I was thinking.

 

[gopher_p]

I believe your question is related to a somewhat famous problem:
http://datagenetics.com/blog/july22012/index.html .

It's possible that they're actually the same problem.

 

[uart]

http://math.stackexchange.com/questions/645317/3-incrementing-buttons-optimal-value

I hope the OP doesn't mind, but I posted this question on Math.SE because I was so interested in seeing a nice solution.

Someone wrote a program and included a chart, and explained the results.

For our specific case [1,100], his finding was (1,12,19), which gives about an average of 5 clicks.

I don't agree with that finding. Assuming we're limited to non negatives*, my first hunch on this was (1,\, 100^{1/3},\, 100^{2/3}), which rounds to (1,5,22). Testing this solution it gives an average of 5.26 clicks and a worst case of 10 clicks. The (1,12,19) solution fared worse on both counts.

Testing with a program to run all combinations it turns out that (1,5,22) is indeed optimal. The solution is not however unique, there were several combination which gave an equal average value and many that gave an equal worst case count. There were however only two non negative solutions which were optimal for both the average and the worst case counts. These are (1,5,22) as already stated, and also (1,5,23) which was equivalent.

*BTW. Including "1" as one of the increments is only necessary if you disallow negatives. If you allow negative numbers then including "1" is no longer mandatory, for example (-2,3,10) could clearly construct all possible numbers 1..100.

EDIT: And I could be wrong.
I just noticed that my program exhausts the multiples of the larger increments before moving on to the smaller ones. This may well be suboptimal for cases like (1,12,19), so I have probably unfairly dismissed that solution.

 

[martix]

That's actually rather interesting. :)
I guess an exhaustive search is the go-to approach.

I knew this reminded me of something!

The whole discussion spurred my memory:
I believe we are looking at a variation of the coin-counting problem.

uart, there's two approaches. One is the greedy algorithm which you have used, but for certain cases where the terms are not proper multiples of each other, the algorithm is insufficient.
The SE solution with the weird terms needs to be covered by the dynamic programming algorithm.

HOWEVER!

On further consideration - given that the original problem of this going into a UI - something a human would use, the go-to approach of a person will probably be the greedy one. I mean I can't imagine a person trying to enter stuff like that is going to consider the mathematical ramifications of how to most efficiently go about doing so.
Therefore a solution that is mathematically the most efficient might not turn out to be as good an idea for a human interface. :)

 

[1MileCrash]

Well, if we're accounting for how humans will decide to use the buttons, it's kind of hard to answer the question.

 

[martix]

No, we aren't, I don't mind the discussion, it was just a very sudden realization. :P

 

[uart]

HOWEVER!

On further consideration - given that the original problem of this going into a UI - something a human would use, the go-to approach of a person will probably be the greedy one. I mean I can't imagine a person trying to enter stuff like that is going to consider the mathematical ramifications of how to most efficiently go about doing so.
Therefore a solution that is mathematically the most efficient might not turn out to be as good an idea for a human interface. :)

Exactly. This is something I was going to suggest. As far as human interaction is concerned, either one of (1,5,20) or (1,5,25) are close enough to optimal to make one of these the best choice in my opinion. And yes you are correct, this is precisely the coin problem.