Register to reply 
Least amount of terms for sum.by martix
Tags: terms 
Share this thread: 
#1
Jan1414, 01:43 PM

P: 130

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 bruteforce approach. 


#2
Jan1414, 01:52 PM

P: 1,302

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! 


#3
Jan1414, 02:10 PM

P: 130

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



#4
Jan1814, 01:05 PM

P: 19

Least amount of terms for sum.
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. 


#5
Jan2214, 10:22 AM

P: 1,302

http://math.stackexchange.com/questions/645317/3incrementingbuttonsoptimalvalue
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! 


#6
Jan2214, 01:07 PM

P: 477

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. 


#7
Jan2314, 08:49 AM

Sci Advisor
P: 2,751

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. 


#8
Jan2314, 04:16 PM

P: 130

That's actually rather interesting. :)
I guess an exhaustive search is the goto approach. I knew this reminded me of something! The whole discussion spurred my memory: I believe we are looking at a variation of the coincounting 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 goto 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. :) 


#9
Jan2314, 07:27 PM

P: 1,302

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



#10
Jan2414, 08:56 AM

P: 130

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



#11
Jan2514, 08:20 AM

Sci Advisor
P: 2,751




Register to reply 
Related Discussions  
Transforming velocity in terms of displacement to velocity in terms of time  Calculus & Beyond Homework  2  
Electrolysis When calculating amount of charge from an amount of  Chemistry  1  
Are all quadratic terms in gauge fields necessarily mass terms?  Quantum Physics  0  
Charge density in terms of (r,θ) but need it in terms of the vector r'  Advanced Physics Homework  8  
Amount of Terms Required to Find a Sum at an Indicated Accuracy  Calculus & Beyond Homework  3 