Little math problem(s) February 2019

02072019, 12:14 PM
(This post was last modified: 02072019 12:17 PM by pier4r.)
Post: #1




Little math problem(s) February 2019
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:
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:
3x3 Code:
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. Wikis are great, Contribute :) 

02112019, 10:10 AM
(This post was last modified: 02112019 10:14 AM by pier4r.)
Post: #2




RE: Little math problem(s) February 2019
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+(n1) . 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:
Wikis are great, Contribute :) 

02132019, 12:31 PM
(This post was last modified: 02132019 01:30 PM by pier4r.)
Post: #3




RE: Little math problem(s) February 2019
Wikis are great, Contribute :) 

02192019, 07:40 PM
(This post was last modified: 02192019 07:41 PM by pier4r.)
Post: #4




RE: Little math problem(s) February 2019
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? Wikis are great, Contribute :) 

02202019, 02:14 AM
Post: #5




RE: Little math problem(s) February 2019
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(1p)) 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(1p) + 6(1p)²) Best of 4: ... got coefficient of 1,4,10,20. My guess is the trend continues. ==> Best of N: T = p^N * sum(nCr(N1+k,k) * (1p)^k, k = 0 to N1) Code: Bestof Whole Tournament, expected better player winning 

02202019, 05:26 PM
(This post was last modified: 02202019 05:26 PM by pier4r.)
Post: #6




RE: Little math problem(s) February 2019
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 ? Wikis are great, Contribute :) 

02202019, 06:39 PM
Post: #7




RE: Little math problem(s) February 2019
Hi, pier4r
After the few bestofn'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 nCr If I extend the range to bestof41, winning precentages = 96.6, 99.7, 100.0 

02202019, 09:44 PM
Post: #8




RE: Little math problem(s) February 2019
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
Wikis are great, Contribute :) 

02202019, 10:55 PM
Post: #9




RE: Little math problem(s) February 2019
I tried bestof21 simulation, the result match theoretical numbers well.
PHP Code: from random import random 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 

02212019, 02:28 AM
(This post was last modified: 02212019 09:36 PM by Albert Chan.)
Post: #10




RE: Little math problem(s) February 2019
If the distribution is normal, to get 90%+ winning, zscore ≥ 1.2816
If n is high enough, binomial distribution approx. well to normal curve: mean = N*p stddev = √(N*p*(1p)) To simplify, assume game continue to N=2n, even if winner already decided zscore = (2np  n) / √(2np*(1p)) ≥ 1.2816 n ≥ ceil( (2p) (1p) (1.2816/(2p1))² ) 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 underestimated for p=60% (should be bestof21 wins), but not bad. update: Tried p = 51%, for 90% chance of winning: Normal distribution estimate => bestof2053 wins. Binomial distribution estimate => bestof2053 wins. 

02212019, 03:58 AM
Post: #11




RE: Little math problem(s) February 2019
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 TI30X Pro MathPrint 

02212019, 04:42 AM
Post: #12




RE: Little math problem(s) February 2019
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?


02212019, 07:53 AM
Post: #13




RE: Little math problem(s) February 2019
(02212019 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 offbyone error in the above. You want at least 90% to lie below 21 games won (i.e. <= 20 games won). — Ian Abbott 

02212019, 10:59 AM
Post: #14




RE: Little math problem(s) February 2019
Perhaps my wording is a bit confusing.
I meant bestof21 wins, with whatever games needed to achieve it. Total games are variable, upto max of N = 2n1 = 41 games. 

02212019, 02:09 PM
Post: #15




RE: Little math problem(s) February 2019
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!


02222019, 02:51 PM
(This post was last modified: 02222019 03:01 PM by Albert Chan.)
Post: #16




RE: Little math problem(s) February 2019
(02212019 10:59 AM)Albert Chan Wrote: I meant bestof21 wins, with whatever games needed to achieve it. Expected total games to finish is less than 2n1 = sum((games played) * (probability of games played produced a winner)) = sum((n+k) * nCr(n1+k, k) * (p^n (1p)^k + (1p)^n p^k), k = 0 to n1) > Bestof21 wins, p=50%, expected total games ≈ 36.8598 ; maximum expected value > Bestof21 wins, p=60%, expected total games ≈ 34.4171 ; Probability of reaching 41 games = 1 in 18 

02232019, 01:15 PM
Post: #17




RE: Little math problem(s) February 2019
(02212019 10:59 AM)Albert Chan Wrote: Perhaps my wording is a bit confusing. 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. Wikis are great, Contribute :) 

02232019, 01:23 PM
(This post was last modified: 02232019 08:09 PM by pier4r.)
Post: #18




RE: Little math problem(s) February 2019
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. Wikis are great, Contribute :) 

02232019, 04:06 PM
(This post was last modified: 02232019 04:07 PM by Thomas Klemm.)
Post: #19




It's easy to use LaTeX in your posts
(02232019 01:23 PM)pier4r Wrote: One has a set of positive integers This is all I had to add to make it LaTeX: Code: I = \{ i_1,...., i_N \} 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 

02232019, 04:23 PM
Post: #20




RE: Little math problem(s) February 2019
(02232019 01:23 PM)pier4r Wrote: One has a set of positive integers If ... meant any positive integers, with no relation to each other, S1 and S2 is not enough. If ... meant I = {i1, i1 + 1, ... i1 + N1}, I may be recovered from S1, S2. S1 = N * (i1 + i1 + N1) / 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 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)