Little math problem(s) February 2019 - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: Little math problem(s) February 2019 (/thread-12373.html) Pages: 1 2 Little math problem(s) February 2019 - pier4r - 02-07-2019 12:14 PM I saw this packing problem on an android program. It shouldn't be terribly difficult with brute force (only time consuming). One has the following space around a base building (determined by the B cells) Code:        ssssss     ssssssssss    ssssssssssss   ssssssssssssss  ssssssssssssssss  ssssssssssssssss ssssssssssssssssss ssssssssssssssssss ssssssssBBssssssss ssssssssBBssssssss ssssssssssssssssss ssssssssssssssssss  ssssssssssssssss  ssssssssssssssss   ssssssssssssss    ssssssssssss     ssssssssss       ssssss There are two other types of buildings. A 3x3 and a 2x2. There is a caveat, they need empty space around them to be placed. As follows. 2x2 Code:   ee eBBe eBBe  ee 3x3 Code:    eee    eBBBe  eBBBe  eBBBe   eee Empty space can overlap but should not be occupied by buildings. What is the packing that fits two 3x3 buildings and then as many 2x2 as possible? Of course the problem can be extended to a combination of different numbers of 3x3 and 2x2 (or even other size and starting space). I'll try to give it a shot with the 50g if I see in my mind something better than brute force. RE: Little math problem(s) February 2019 - pier4r - 02-11-2019 10:10 AM And another little one. A participant has 30 attempts to hit a target. If they hit a target they get A points (A in {7,8,9,10,12} because it is important compared to the number of attempts), if they hit the target at the next attempt too, they get the amount of points they got at the successful previous attempt plus one. Therefore in a streak of successful n attempts, they get: A, A+1, A+2, ..., A+(n-1) . If they an attempt is unsuccessful it ends the streak and the next successful attempt will give again A points. Problems: (a): Is the sum of the points collected in the 30 attempts always unique? That is: for a given sum one has only one way to score the points to attain it. In this case I intend independently from failures that do not affect the score. For example: Fail, Fail, Success, Success, Fail, Success Success, Fail, Success, Success, Fail Fail, Success, Fail, Fail, Fail, Success, Success are all considered equal as the sum is composed by one streak of two successes and one isolated success. (b): Is the percentage of successes on 30 attempts is known, is the combination of the sum of the points plus the success percentage unique? That is, for a given sum of points and success percentage one has only one way to attain it. Again here some distributions of failures that do not really affect the score or the success percentage are not considered different. For example: Success, Fail, Success, Success, Fail Fail, Success, Fail, Success, Success are considered equal as they have one isolated success and one streak of two successes (and have the same success percentage). while Fail, Success, Fail, Fail, Fail, Success, Success is different as the success percentage is different from above. (c) If the percentage of successes is known, and the final sum of points is known, but the participant didn't necessarily use all 30 attempts, is it possible to determine uniquely how they attained the score? There is a good possibility I was not clear. In that case please ask for clarification! Code:  Spoiler alret as usual (a) No. 7+8+9+10+11+12+13+14 (one single streak of 8 successes) or 7+8+9+10+11+12+13+7+7 (one streak with 7 successes and two isolated ones) give the same amount of points (b) (c) RE: Little math problem(s) February 2019 - pier4r - 02-13-2019 12:31 PM Wrong thread: See http://www.hpmuseum.org/forum/thread-8209-post-112147.html#pid112147 RE: Little math problem(s) February 2019 - pier4r - 02-19-2019 07:40 PM And another little one. There are Alice and Barbara that play a game. Barbara wins alice 60% of the times. They want to organize a tournament, but they would like to avoid to rely on luck. Therefore they want to make a match be long enough to determine the better player with a certain accuracy. They know that between players that have 50% chances of win in a games (or close to that) the game would be very long, therefore they decide to pick another case as reference. They decide to make a tournament with a match composed of "Best of N" games, where N is the number of games needed to ensure that at least 90% of the times a player with 60% chances of winning a game against their opponent will win. Which N is that? What is N when the better player has 65% chances of winning a game? What is N when the better player has 70% chances of winning a game? RE: Little math problem(s) February 2019 - Albert Chan - 02-20-2019 02:14 AM For best of N match puzzle, think binary, 0=lost, 1=win let probability of better player winning be p, for whole tournament be T Best of 1: 1 ==> T = p Best of 2: 011 101 11 ==> T = p^2 *(1 + 2(1-p)) Best of 3: 00111 01011 01101 0111 10011 10101 1011 11001 1101 111 sort by length of games: 1x3 + 3x4 + 6x5, total 1+3+6 = 10 cases ==> T = p^3 * (1 + 3(1-p) + 6(1-p)²) Best of 4: ... got coefficient of 1,4,10,20. My guess is the trend continues. ==> Best of N: T = p^N * sum(nCr(N-1+k,k) * (1-p)^k, k = 0 to N-1) Code: Best-of     Whole Tournament, expected better player winning 1      p =  60%    65%    70% 2         64.8%  71.8%  78.4% 3         68.3%  76.5%  83.7% 4         71.0%  80.0%  87.4% 5         73.3%  82.8%  90.1%  <-- T>90% for p=70%, best-of-5 6         75.3%  85.1%  92.2% 7         77.1%  87.1%  93.8% 8         78.6%  88.7%  95.0% 9         80.1%  90.1%  96.0%  <-- T>90% for p=65%, best-of-9 21        90.3%  97.6%  99.6%  <-- T>90% for p=60%, best-of-21 RE: Little math problem(s) February 2019 - pier4r - 02-20-2019 05:26 PM The trend is indeed "N choose k" (it is like pick K positions from N available). Plus the binomial distribution. Only I want to write something more about your solution (that should be correct) when I have a bit more time. Are you sure it is 21 not 41 ? RE: Little math problem(s) February 2019 - Albert Chan - 02-20-2019 06:39 PM Hi, pier4r After the few best-of-n's, computations by calculator a bit too much. This is the Python code that I used to build the winning percentages: PHP Code: from gmpy2 import comb as nCrdef win_percent(coefs, x, r=0):    for coef in coefs: r = r * x + coef     # Horner's rule    return (100 * r * (1-x)**len(coefs),)   # scaled to percentfor n in range(1,25):                       # best-of-n    coefs = [ nCr(n-1+i, i) for i in range(n-1,-1,-1) ]    print n, '\t',    for p in [0.60, 0.65, 0.7]: print '%5.1f' % win_percent(coefs, 1-p),    print  If I extend the range to best-of-41, winning precentages = 96.6, 99.7, 100.0 RE: Little math problem(s) February 2019 - pier4r - 02-20-2019 09:44 PM Ok if I find the time I will try to test your results. As I did it first on paper, then simulated (not using the binomial coefficient) and the simulated result for 60% differ a bit from theory. Interesting RE: Little math problem(s) February 2019 - Albert Chan - 02-20-2019 10:55 PM I tried best-of-21 simulation, the result match theoretical numbers well. PHP Code: from random import randomdef simulation(n, best_of, total_win=0, random=random):    for t in xrange(n):        lst = [0,0]        while max(lst) < best_of: lst[random() >= 0.6] += 1        if lst[0] == best_of: total_win += 1    return total_win / n  for i in range(10): print simulation(10000, 21) 0.904 0.9069 0.9079 0.9043 0.9046 0.9042 0.8995 0.9003 0.9062 0.9037 RE: Little math problem(s) February 2019 - Albert Chan - 02-21-2019 02:28 AM If the distribution is normal, to get 90%+ winning, z-score ≥ 1.2816 If n is high enough, binomial distribution approx. well to normal curve: mean = N*p std-dev = √(N*p*(1-p)) To simplify, assume game continue to N=2n, even if winner already decided z-score = (2np - n) / √(2np*(1-p)) ≥ 1.2816 n ≥ ceil( (2p) (1-p) (1.2816/(2p-1))² ) For p=70%, n ≥ ceil(4.3) = 5 For p=65%, n ≥ ceil(8.3) = 9 For p=60%, n ≥ ceil(19.7) = 20 Slightly under-estimated for p=60% (should be best-of-21 wins), but not bad. update: Tried p = 51%, for 90% chance of winning: Normal distribution estimate => best-of-2053 wins. Binomial distribution estimate => best-of-2053 wins. RE: Little math problem(s) February 2019 - lrdheat - 02-21-2019 03:58 AM Perhaps (that is, likely) I don't understand... If I want at least 90% of a binomial cumulative population to lie above some number of successes by a player that had a probability of a win of 60% on any given try where this is a best of "x" number of games, I am finding that 30 successes out of a 59 game tourney would be the lowest number of tourney games that would satisfy this problem. Brute force solution on a TI-30X Pro MathPrint RE: Little math problem(s) February 2019 - lrdheat - 02-21-2019 04:42 AM Example of my misunderstanding of this problem...from the viewpoint of the 40% probability of a win on a given try player, just a best of 41 would be sufficient for at least 90% of the distribution to lie below 20 games won (and fail to win the tourney). What am I missing here? RE: Little math problem(s) February 2019 - ijabbott - 02-21-2019 07:53 AM (02-21-2019 04:42 AM)lrdheat Wrote:  Example of my misunderstanding of this problem...from the viewpoint of the 40% probability of a win on a given try player, just a best of 41 would be sufficient for at least 90% of the distribution to lie below 20 games won (and fail to win the tourney). What am I missing here? There is an off-by-one error in the above. You want at least 90% to lie below 21 games won (i.e. <= 20 games won). RE: Little math problem(s) February 2019 - Albert Chan - 02-21-2019 10:59 AM Perhaps my wording is a bit confusing. I meant best-of-21 wins, with whatever games needed to achieve it. Total games are variable, upto max of N = 2n-1 = 41 games. RE: Little math problem(s) February 2019 - lrdheat - 02-21-2019 02:09 PM Thank you for the clarification. Now I have to think so more on what was wrong with my calculation from the perspective of the player with a 60% probability of a win on a given try! RE: Little math problem(s) February 2019 - Albert Chan - 02-22-2019 02:51 PM (02-21-2019 10:59 AM)Albert Chan Wrote:  I meant best-of-21 wins, with whatever games needed to achieve it. Total games are variable, upto max of N = 2n-1 = 41 games. Expected total games to finish is less than 2n-1 = sum((games played) * (probability of games played produced a winner)) = sum((n+k) * nCr(n-1+k, k) * (p^n (1-p)^k + (1-p)^n p^k), k = 0 to n-1) -> Best-of-21 wins, p=50%, expected total games ≈ 36.8598 ; maximum expected value -> Best-of-21 wins, p=60%, expected total games ≈ 34.4171 ; Probability of reaching 41 games = 1 in 18 RE: Little math problem(s) February 2019 - pier4r - 02-23-2019 01:15 PM (02-21-2019 10:59 AM)Albert Chan Wrote:  Perhaps my wording is a bit confusing. I meant best-of-21 wins, with whatever games needed to achieve it. Total games are variable, upto max of N = 2n-1 = 41 games. Ah now it fits. So you considered the number of victories. The best of N for me means: bo5 : 3 victories determine the winner. bo41 : 21 victories determine the winner. So for this I was asking about 41 rather than 21. RE: Little math problem(s) February 2019 - pier4r - 02-23-2019 01:23 PM And another problem. Although I didn't dive deep in it yet. (I may have already exposed it in other threads) One has a set of positive integers $$I = \{ i_1,...., i_N \}$$ the question is: can we identify uniquely I if the sum $$S_1= \sum (i_1, ... , i_N)$$ and $$S_2 = \sum (i_1^2, ..., i_N^2 )$$ are given? What if N is fixed (say, 30 elements)? Does it help us to identify I uniquely? If N is not fixed, does it mean that it is easier to find a I1 and a I2 of different size (and therefore elements) that have the same S1 and S2 ? The problem here is to find either an argument for uniqueness or a counterexample that uniqueness is not always true. Inspiration: monthly stats on the bank account. It's easy to use LaTeX in your posts - Thomas Klemm - 02-23-2019 04:06 PM (02-23-2019 01:23 PM)pier4r Wrote:  One has a set of positive integers I = { i1,...., iN } the question is: can we identify uniquely I if the sum S1= sum (i1, ... , iN) and S2 = sum (i1^2, ..., iN^2 ) are given? This is all I had to add to make it LaTeX: Code: I = \{ i_1,...., i_N \} S_1= \sum (i_1, ... , i_N) S_2 = \sum (i_1^2, ..., i_N^2 ) Include everything in \​(…)\ and we're done: One has a set of positive integers $$I = \{ i_1,...., i_N \}$$ the question is: can we identify uniquely I if the sum $$S_1= \sum (i_1, ... , i_N)$$ and $$S_2 = \sum (i_1^2, ..., i_N^2 )$$ are given? This online LaTeX Equation Editor may help. Cheers Thomas RE: Little math problem(s) February 2019 - Albert Chan - 02-23-2019 04:23 PM (02-23-2019 01:23 PM)pier4r Wrote:  One has a set of positive integers I = { i1,...., iN } If ... meant any positive integers, with no relation to each other, S1 and S2 is not enough. If ... meant I = {i1, i1 + 1, ... i1 + N-1}, I may be recovered from S1, S2. S1 = N * (i1 + i1 + N-1) / 2 i1 = 1/2 - N/2 + S1/N If N is a fixed, i1 is unique, thus I is unique. If N is variable, substitute i1 into S2 expression, it created a quartic polynomial: N^4 - N^2 - 12 S2 N + 12 S1² = 0 With i1 and N only allowed positive integer, my guess is I is still unique. If 2 list have the same S1, S2 of shorter list should be bigger. Example: sum(k, k, 100, 200) => 15150 sum(k, k, 102, 201) => 15150 sum(k^2, k, 100, 200) => 2358350 sum(k^2, k, 102, 201) => 2378550