Little math problem(s) February 2019

[pier4r]

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.

[pier4r]

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)

[pier4r]

Wrong thread:

See http://www.hpmuseum.org/forum/thread-820...#pid112147

[pier4r]

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?

[Albert Chan]

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

[pier4r]

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 ?

[Albert Chan]

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 nCr

def 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 percent

for 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

[pier4r]

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

[Albert Chan]

I tried best-of-21 simulation, the result match theoretical numbers well.

PHP Code:

from random import random

def 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

[Albert Chan]

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.

[lrdheat]

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

[lrdheat]

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?

[ijabbott]

(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).

[Albert Chan]

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.

[lrdheat]

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!

[Albert Chan]

(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

[pier4r]

(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.

[pier4r]

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.

[Thomas Klemm]

(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

[Albert Chan]

(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