Un matemático y un equipo que está jugando un juego: en Primer lugar, el matemático elige un entero en el rango de $2,...,1000$. A continuación, el equipo elige un entero uniformemente al azar de la misma gama. Si el número elegido compartir un primer factor, el mayor número de victorias. Si no lo hacen, el menor número de victorias. (Si los dos números son iguales, el juego es un empate.)
Qué número debe al matemático elegir con el fin de maximizar sus posibilidades de ganar?
De intervalo fijo:
range = 16;
a = Table[Table[FactorInteger[y][[n, 1]], {n, 1, PrimeNu[y]}], {y, 1, range}];
b = Table[Sort@DeleteDuplicates@ Flatten@Table[
Table[Position[a, a[[y, m]]][[n, 1]],
{n, 1, Length@Position[a, a[[y, m]]]}], {m, 1, PrimeNu[y]}], {y, 1, range}];
c = Table[Complement[Range[range], b[[n]]], {n, 1, range}];
d = Table[Range[n, range], {n, 1, range}];
e = Table[Range[1, n], {n, 1, range}];
w = Table[DeleteCases[DeleteCases[Join[Intersection[c[[n]], e[[n]]],
Intersection[b[[n]], d[[n]]]], 1], n], {n, 1, range}];
l = Table[DeleteCases[DeleteCases[Complement[Range[range], w[[n]]], 1],
n], {n, 1, range}];
results = Table[Length@l[[n]], {n, 1, range}];
cf = Grid[{{Join[{"n"}, Rest@(r = Range[range])] // ColumnForm,
Join[{"win against n"}, Rest@w] // ColumnForm,
Join[{"lose against n"}, Rest@l] // ColumnForm,
Join[{"probability win for n"}, (p = Drop[Table[
results[[n]]/Total@Drop[results, 1] // N,{n, 1, range}], 1])] // ColumnForm}}]
Flatten[Position[p, Max@p] + 1]
no es un gran código, pero divertido para jugar con pequeños intervalos, da
y tal vez, más reveladora
rr = 20; Grid[{{Join[{"range"}, Rest@(r = Range[rr])] // ColumnForm,
Join[{"best n"}, (t = Rest@Table[
a = Table[Table[FactorInteger[y][[n, 1]], {n, 1, PrimeNu[y]}], {y, 1, range}];
b = Table[Sort@DeleteDuplicates@Flatten@Table[Table[
Position[a, a[[y, m]]][[n, 1]], {n, 1,Length@Position[a, a[[y, m]]]}],
{m, 1,PrimeNu[y]}], {y, 1, range}];
c = Table[Complement[Range[range], b[[n]]], {n, 1, range}];
d = Table[Range[n, range], {n, 1, range}];
e = Table[Range[1, n], {n, 1, range}];
w = Table[DeleteCases[DeleteCases[Join[Intersection[c[[n]], e[[n]]],
Intersection[b[[n]], d[[n]]]], 1], n], {n, 1, range}];
l = Table[DeleteCases[DeleteCases[Complement[Range[range], w[[n]]], 1], n],
{n,1, range}];
results = Table[Length@l[[n]], {n, 1, range}];
p = Drop[Table[results[[n]]/Total@Drop[results, 1] // N,
{n, 1, range}], 1];
{Flatten[Position[p, Max@p] + 1], Max@p}, {range, 1, rr}]/.Indeterminate-> draw);
Table[t[[n, 1]], {n, 1, rr - 1}]] // ColumnForm,
Join[{"probability for win"}, Table[t[[n, 2]], {n, 1, rr - 1}]] // ColumnForm}}]
compara los rangos:
Trazado significa "mejor $n$" en contra de $\sqrt{\text{range}}$ da
Para el rango=$1000,$ "mejor $n$" se $29$$31$, que puede ser visto como maxima en este gráfico:
A la luz de DanielV el comentario de que "los números primos vs winchance" graph probablemente sería esclarecedor, hice un poco de investigación, y resulta que es. Mirando el "winchance" (sólo una ponderación de $n$) de los números primos en el rango, es posible dar una bastante exacta predicción utilizando
range = 1000;
a = Table[Table[FactorInteger[y][[n, 1]], {n, 1, PrimeNu[y]}], {y, 1, range}];
b = Table[Sort@DeleteDuplicates@Flatten@Table[
Table[Position[a, a[[y, m]]][[n, 1]], {n, 1,
Length@Position[a, a[[y, m]]]}], {m, 1, PrimeNu[y]}], {y, 1, range}];
c = Table[Complement[Range[range], b[[n]]], {n, 1, range}];
d = Table[Range[n, range], {n, 1, range}];
e = Table[Range[1, n], {n, 1, range}];
w = Table[ DeleteCases[ DeleteCases[
Join[Intersection[c[[n]], e[[n]]], Intersection[b[[n]], d[[n]]]],
1], n], {n, 1, range}];
l = Table[
DeleteCases[DeleteCases[Complement[Range[range], w[[n]]], 1],
n], {n, 1, range}];
results = Table[Length@l[[n]], {n, 1, range}];
p = Drop[Table[
results[[n]]/Total@Drop[results, 1] // N, {n, 1, range}], 1];
{Flatten[Position[p, Max@p] + 1], Max@p};
qq = Prime[Range[PrimePi[2], PrimePi[range]]] - 1;
Show[ListLinePlot[Table[p[[t]] range, {t, qq}],
DataRange -> {1, Length@qq}],
ListLinePlot[
Table[2 - 2/Prime[x] - 2/range (-E + Prime[x]), {x, 1, Length@qq + 0}],
PlotStyle -> Red], PlotRange -> All]
La trama anterior (se $2$ parcelas aquí) muestran los valores de "winchance" para los números primos en contra de una parcela de $$2+\frac{2 (e-p_n)}{\text{range}}-\frac{2}{p_n}$$
where $p_n$ is the $n$th prime, and "winchance" is the number of possible wins for $n$ divided by total number of possible wins in range ie $$\dfrac{\text{range}}{2}\left(\text{range}-1\right)$$ eg $499500$ for range $1000$.
Show[p // ListLinePlot, ListPlot[N[
Transpose@{Prime[Range[PrimePi[2] PrimePi[range]]],
Table[(2 + (2*(E - Prime[x]))/range - 2/Prime[x])/range, {x, 1,
Length@qq}]}], PlotStyle -> {Thick, Red, PointSize[Medium]},
DataRange -> {1, range}]]
Bit of fun with game simulation:
games = 100; range = 30;
table = Prime[Range[PrimePi[range]]];
choice = Nearest[table, Round[Sqrt[range]]][[1]];
y = RandomChoice[Range[2, range], games]; z = Table[
Table[FactorInteger[y[[m]]][[n, 1]], {n, 1, PrimeNu[y[[m]]]}], {m, 1, games}];
Count[Table[If[Count[z, choice] == 0 && y[[m]] < choice \[Or]
Count[z, choice] > 0 && y[[m]] < choice, "lose", "win"],
{m, 1, games}], "win"]
& simulated wins against computer over variety of ranges
with
Clear[range]
highestRange = 1000;
ListLinePlot[Table[games = 100;
table = Prime[Range[PrimePi[range]]];
choice = Nearest[table, Round[Sqrt[range]]][[1]];
y = RandomChoice[Range[2, range], games];
z = Table[Table[FactorInteger[y[[m]]][[n, 1]], {n, 1, PrimeNu[y[[m]]]}], {m,
1, games}];
Count[Table[ If[Count[z, choice] == 0 && y[[m]] < choice \[Or]
Count[z, choice] > 0 && y[[m]] < choice, "lose", "win"], {m, 1,
games}], "win"], {range,2, highestRange}], Filling -> Axis, PlotRange-> All]
Plot of mean "best $n$" up to range$=1000$ with tentative conjectured error bound of $\pm\dfrac{\sqrt{\text{range}}}{\log(\text{range})}$ for range$>30$.
Yo podría estar equivocado, sin embargo. - De hecho, en la reflexión, creo que yo soy (relacionados).
Considerar en primer lugar la elección de un primer $p$ en el rango $[2,N]$. Usted pierde sólo si el equipo elige un múltiplo de $p$ o un número menor que $p$, lo cual ocurre con probabilidad $$ \frac{(\lfloor{N/p}\rfloor-1)+(p-2)}{N-1}=\frac{\lfloor{p+N/p}\rfloor-3}{N-1}. $$ El término dentro de la función del suelo ha derivado $$ 1-\frac{N}{p^2}, $$ lo que se incrementa por $p\le \sqrt{N}$ y disminuye a partir de entonces. La función del suelo no cambiar este comportamiento. Así que el mejor primer elegir es siempre uno de los dos más cercanos primos de a $\sqrt{N}$ (el de su izquierda y su derecha, a menos que $N$ es el cuadrado de un primo). Su posibilidad de perder con esta estrategia se $\sim 2/\sqrt{N}$.
Por otro lado, considerar la elección de un compuesto de $q$ cuyos factores primos son $$p_1 \le p_2 \le \ldots \le p_k.$$ Then the computer certainly wins if it chooses a prime number less than $q$ (other than any of the $p$'s); there are about $p / \log p$ of these by the prime number theorem. It also wins if it chooses a multiple of $p_1$ larger than $p$; there are about $(N-q)/p_1$ of these. Since $p_1 \le \sqrt{q}$ (because $p$ es compuesto), el equipo la oportunidad de ganar aquí es al menos aproximadamente $$ \frac{q}{N\log q}+\frac{N-q}{N\sqrt{q}}. $$ El primer término se incrementa con la $q$, y el segundo término disminuye. El segundo término es mayor que $(1/3)/\sqrt{N}$ hasta $q \ge (19-\sqrt{37})N/18 \approx 0.72 N$, momento en el que la primera ya es $0.72 / \log{N}$, lo que en sí es más grande que la de $(5/3)/\sqrt{N}$ mientras $N > 124$. Por lo que la suma de estos términos siempre será mayor que $2/\sqrt{N}$ $N > 124$ o así, lo que significa que el equipo tiene una mejor oportunidad de ganar que si hubiera elegido el mejor prime.
Este cálculo aproximado demuestra que la elección de los primos más cercanos a $\sqrt{N}$ es la mejor estrategia para suficientemente grande $N$, donde "lo suficientemente grande" significa mayor que alrededor de $100$. (Otras respuestas han enumerado las excepciones, la más grande de lo que parece ser $N=30$, en consonancia con este cálculo).
Esquema:
(define (range a b) (if (> a b) '() (cons a (range (+ a 1) b))))
;; Probability of Winning if you Choose N out of NRange
(define (ProbOfWinning N NRange)
;; how many numbers k for which
;; GCD(k, N)=1 and N < k
;; or
;; GCD(k, N)>1 and N > k
;; N beats K
(define (Wins k)
(if (= (gcd k N) 1) (< N k) (> N k)))
(/ (length (filter Wins NRange)) (length NRange)))
(define GameRange (range 2 1000))
(define WinChances (map (λ (N) (list N (ProbOfWinning N GameRange))) GameRange))
(sort WinChances (λ (a b) (< (second a) (second b))) )
Las mejores posibilidades de ganar son $31$$29$, con una probabilidad de $938/999$, y cerca de la tercera $37$ $937/999$
He utilizado Javascript y ataque de fuerza bruta la solución. Ella no era muy rápido, pero funcionó. 29 o 31 son los mejores números para elegir.
function find_primes(max) {
// returns all primes less than or equal to max
for (var primes = [], i = 2; i <= max; ++ i) {
for (var j = 0; j < primes.length; ++ j)
if (i % primes[j] == 0) break; // stop if it's divisible by a prime
if (j >= primes.length) primes.push(i);
}
return primes;
}
function winner(a, b, primes) {
// primes must contain all primes less than or equal to the largest a or b
for (var j = 0; j < primes.length; ++ j)
if (!(a % primes[j] + b % primes[j])) return Math.max(a, b);
return Math.min(a, b);
}
var min = 2, max = 1000, primes = find_primes(max), plays = [];
for (var i = min; i <= max; ++ i) {
plays[i] = {play: i, opponents: 0, wins: 0};
for (var j = min; j <= max; ++ j) {
++ plays[i].opponents;
if (i != j && winner(i, j, primes) == i) ++ plays[i].wins;
}
}
// sort, highest number of wins first
plays.sort(function (a, b) { return a.wins < b.wins; });
// display the results
plays.map(function (e) {
return e.play + ": " + e.wins + " wins (" + (e.wins / e.opponents * 100).toFixed(2) * 1 + "%)";
});
(editar) también se obtiene un patrón interesante si imprime la lista completa con los números primos de relieve, como este:
Me siento como todas las otras respuestas son un poco más complicadas y difíciles de seguir, así que espero que ofrecer algo más sencillo. Siempre estoy impresionado con la hermosa formato MSE, a pesar de que.
En primer lugar, cualquier número $n$ usted elija tendrá un conjunto de factores primos $(p1, p2, ...)$. Para cada factor primordial $p_i$, $x_i =\lfloor \frac{1000}{p_i} \rfloor$ números para considerar que se tiene que el factor común. Si $n$ es el elegido para ser una de las primeras en sí, no se $\lfloor \frac{1000}{n} \rfloor - 1$ números de mayor a $n$ que va a vencer, y que pierde a cualquier número menor que sí mismo, para un total de $$f(n)=n + \lfloor \frac{1000}{n} \rfloor - 2$$
Ahora si $n$ es compuesto, se pierde para todos los números mayores que lo que comparten factores comunes
$$g(n)=\sum{\lfloor{\frac{1000}{p_i}}\rfloor} - \lfloor\frac{n}{p_i}\rfloor$$
así como $\phi(n)$ números menores que n que no comparten factores comunes, con $\phi$ de Euler totient función.
Claramente grandes números primos fallar, ya que $\phi(n) =n-1$ cuando n es primo. Asimismo, pequeño compuesto de números de fallar, ya que $g(n)$ domina allí.
Si examinamos la fórmula de los números primos, podemos ver que está minimizado aproximadamente al $n^2=1000$ tomando un derivado de problemas y solución de problemas. Esta curva monótona disminuye a medida que se está dominada por $\lfloor\frac{1000}{n}\rfloor$ y aumenta monótonamente como está dominado por $n$. Así, sólo un par de primos necesita ser tratado de descubrir que $n=29$ $n=31$ dar el mejor prime soluciones.
Si cualquier solución compuesta va a realizar un primer uno, debe tener un totient menor que $f(31)=61$, por lo menos, y como consecuencia de ello, no puede exceder $210$. Así también debe tener menos de $61$ números entre el $210$ $1000$ que comparte un factor. $\lfloor(1000-210) / 61 \rfloor= 12$, por lo que ninguno de los factores puede ser menos de $12$, pero si hay más de un factor, se tendría un totient demasiado grande. Por lo tanto, no puede haber ninguna solución compuesta mejor que el primer uno.
Intuitivamente, se le acaba la comparación de la cuadrática de crecimiento de las pequeñas excelente elección a la $n/\log{n}$ el crecimiento de la gran opción de composición
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
