Little math problem(s) February 2019
02-07-2019, 12:14 PM (This post was last modified: 02-07-2019 12:17 PM by pier4r.)
Post: #1
 pier4r Senior Member Posts: 1,976 Joined: Nov 2014
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:
       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.

Wikis are great, Contribute :)
02-11-2019, 10:10 AM (This post was last modified: 02-11-2019 10:14 AM by pier4r.)
Post: #2
 pier4r Senior Member Posts: 1,976 Joined: Nov 2014
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+(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)

Wikis are great, Contribute :)
02-13-2019, 12:31 PM (This post was last modified: 02-13-2019 01:30 PM by pier4r.)
Post: #3
 pier4r Senior Member Posts: 1,976 Joined: Nov 2014
RE: Little math problem(s) February 2019

Wikis are great, Contribute :)
02-19-2019, 07:40 PM (This post was last modified: 02-19-2019 07:41 PM by pier4r.)
Post: #4
 pier4r Senior Member Posts: 1,976 Joined: Nov 2014
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 :)
02-20-2019, 02:14 AM
Post: #5
 Albert Chan Senior Member Posts: 623 Joined: Jul 2018
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(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
02-20-2019, 05:26 PM (This post was last modified: 02-20-2019 05:26 PM by pier4r.)
Post: #6
 pier4r Senior Member Posts: 1,976 Joined: Nov 2014
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 :)
02-20-2019, 06:39 PM
Post: #7
 Albert Chan Senior Member Posts: 623 Joined: Jul 2018
RE: Little math problem(s) February 2019
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
02-20-2019, 09:44 PM
Post: #8
 pier4r Senior Member Posts: 1,976 Joined: Nov 2014
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 :)
02-20-2019, 10:55 PM
Post: #9
 Albert Chan Senior Member Posts: 623 Joined: Jul 2018
RE: Little math problem(s) February 2019
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
02-21-2019, 02:28 AM (This post was last modified: 02-21-2019 09:36 PM by Albert Chan.)
Post: #10
 Albert Chan Senior Member Posts: 623 Joined: Jul 2018
RE: Little math problem(s) February 2019
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.
02-21-2019, 03:58 AM
Post: #11
 lrdheat Senior Member Posts: 463 Joined: Feb 2014
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 TI-30X Pro MathPrint
02-21-2019, 04:42 AM
Post: #12
 lrdheat Senior Member Posts: 463 Joined: Feb 2014
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?
02-21-2019, 07:53 AM
Post: #13
 ijabbott Senior Member Posts: 557 Joined: Jul 2015
RE: Little math problem(s) February 2019
(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).

— Ian Abbott
02-21-2019, 10:59 AM
Post: #14
 Albert Chan Senior Member Posts: 623 Joined: Jul 2018
RE: Little math problem(s) February 2019
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.
02-21-2019, 02:09 PM
Post: #15
 lrdheat Senior Member Posts: 463 Joined: Feb 2014
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!
02-22-2019, 02:51 PM (This post was last modified: 02-22-2019 03:01 PM by Albert Chan.)
Post: #16
 Albert Chan Senior Member Posts: 623 Joined: Jul 2018
RE: Little math problem(s) February 2019
(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
02-23-2019, 01:15 PM
Post: #17
 pier4r Senior Member Posts: 1,976 Joined: Nov 2014
RE: Little math problem(s) February 2019
(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.

Wikis are great, Contribute :)
02-23-2019, 01:23 PM (This post was last modified: 02-23-2019 08:09 PM by pier4r.)
Post: #18
 pier4r Senior Member Posts: 1,976 Joined: Nov 2014
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 :)
02-23-2019, 04:06 PM (This post was last modified: 02-23-2019 04:07 PM by Thomas Klemm.)
Post: #19
 Thomas Klemm Senior Member Posts: 1,449 Joined: Dec 2013
It's easy to use LaTeX in your posts
(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?

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
02-23-2019, 04:23 PM
Post: #20
 Albert Chan Senior Member Posts: 623 Joined: Jul 2018
RE: Little math problem(s) February 2019
(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
 « Next Oldest | Next Newest »

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