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!

Least amount of terms for sum.

  1. Jan 14, 2014 #1
    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.
  2. jcsd
  3. Jan 14, 2014 #2
    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!
    Last edited: Jan 14, 2014
  4. Jan 14, 2014 #3
    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.
  5. Jan 18, 2014 #4
    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.
  6. Jan 22, 2014 #5

    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!

    Yes, you are right, both of the other numbers can be pressed for a value, not sure what I was thinking.
  7. Jan 22, 2014 #6
  8. Jan 23, 2014 #7


    User Avatar
    Science Advisor

    I don't agree with that finding. Assuming we're limited to non negatives*, my first hunch on this was [itex](1,\, 100^{1/3},\, 100^{2/3})[/itex], 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. :blushing:
    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.
    Last edited: Jan 23, 2014
  9. Jan 23, 2014 #8
    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.


    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. :)
    Last edited: Jan 23, 2014
  10. Jan 23, 2014 #9
    Well, if we're accounting for how humans will decide to use the buttons, it's kind of hard to answer the question.
  11. Jan 24, 2014 #10
    No, we aren't, I don't mind the discussion, it was just a very sudden realization. :P
  12. Jan 25, 2014 #11


    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook