¿Cuál es el número mínimo de conjuntos tales que el producto de los elementos en cada uno de ellos sea menor que k?

Question

¿Cuál es el número mínimo de conjuntos tales que el producto de los elementos en cada uno de ellos sea menor que k?

Matemáticas
combinatoria
teoría de los números
partición conjunto
teoría elemental de conjuntos
extremal-combinatorics

vacío_117

Dado un número positivo n y un número positivo k. Cómo encontrar el número mínimo de conjuntos tal que para cada conjunto s, el producto de todos los elementos en s sea menor o igual que k.

Y también todos los conjuntos deben contener solo elementos del 1 al n (ambos inclusive). Y cada número del 1 al n debe estar exactamente en un conjunto.

Mi enfoque fue encontrar primero la raíz cuadrada de k (sea t). Y luego divide los números del 1 al n en 2 partes. La primera parte tiene números menores o iguales a t, la segunda tiene números mayores que t y menores que n. Entonces podemos decir que dos números de la segunda parte no pueden estar en el mismo conjunto, porque su producto será más k. Pero esto no responde completamente la pregunta. ¿Cómo hacerlo?

saulspatz

Bienvenido a MSE. Utilice MathJax para dar formato a sus publicaciones. Para empezar, rodee las expresiones matemáticas (incluidos los números) con $signos y utilícelos _para subíndices. $x_1$ sale como

x_{1}

$x_1$ .

saulspatz

El producto de todos los números es

n!

$n!$ y así es que tenemos

s

$s$ conjuntos, debemos tener

n! \leq k^{s}

$n!\leq k^s$ o

s \geq ⌈ \frac{\log n!}{\log k} ⌉

$s\geq\left\lceil\frac{\log n!}{\log k}\right\rceil$ Entonces, si logramos hacerlo con

⌈ \frac{\log n!}{\log k} ⌉

$\left\lceil\frac{\log n!}{\log k}\right\rceil$ , sabemos que hemos alcanzado el mínimo. No sé si esto siempre es posible, ni conozco un buen algoritmo para construir los conjuntos.

ross milikan

Una manera mucho mejor de plantear el problema sería pedir la partición de

{1, 2, 3, \dots n}

$\{1,2,3,\ldots n\}$ tal que el producto de cada elemento de la partición sea menor que

k

$k$ y se minimiza el número de conjuntos en la partición.

Rob Pratt

@saulspatz

(n, k) = (4, 5)

$(n,k)=(4,5)$ requiere

3

$3$ bins, estrictamente mayor que el límite inferior de

2

$2$ .

Respuestas (1)

¿Cuál es el número mínimo de conjuntos tales que el producto de los elementos en cada uno de ellos sea menor que k?

Bienvenido a MSE. Utilice MathJax para dar formato a sus publicaciones. Para empezar, rodee las expresiones matemáticas (incluidos los números) con $signos y utilícelos _para subíndices. $x_1$ sale como $x_1$ .
El producto de todos los números es $n!$ y así es que tenemos $s$ conjuntos, debemos tener $n!\leq k^s$ o $s\geq\left\lceil\frac{\log n!}{\log k}\right\rceil$ Entonces, si logramos hacerlo con $\left\lceil\frac{\log n!}{\log k}\right\rceil$ , sabemos que hemos alcanzado el mínimo. No sé si esto siempre es posible, ni conozco un buen algoritmo para construir los conjuntos.
Una manera mucho mejor de plantear el problema sería pedir la partición de $\{1,2,3,\ldots n\}$ tal que el producto de cada elemento de la partición sea menor que $k$ y se minimiza el número de conjuntos en la partición.
@saulspatz $(n,k)=(4,5)$ requiere $3$ bins, estrictamente mayor que el límite inferior de $2$ .

Rob Pratt · Answer 1

Puede resolver esto como un problema de embalaje en contenedores donde el $n$ los artículos tienen pesos $\log 1, \dots, \log n$ y cada contenedor tiene capacidad $\log k$ .

¿Cuál es el número mínimo de conjuntos tales que el producto de los elementos en cada uno de ellos sea menor que k?

vacío_117

saulspatz

saulspatz

ross milikan

Rob Pratt

Respuestas (1)

Rob Pratt

¿Cuántas permutaciones casi perfectas hay?

Número mínimo de particiones de un conjunto dada lista de números que no pueden aparecer en la misma partición

Una pregunta sobre un caso especial del principio de inclusión-exclusión

¿La Regla de Collatz 3x+53x+53x+5 tiene un sesgo para ciertos bucles, o mis resultados son defectuosos?

Dado el MCD y el MCM de n enteros positivos, ¿cuántas soluciones hay?

prueba combinatoria de identidad que involucra multiconjuntos

Dos relaciones en serie, cada una implica a la otra - del libro de particiones de Andrews

Seleccionar un elemento de cada uno de muchos conjuntos de modo que no haya dos elementos iguales.

t¿De cuántas maneras podemos dividir un conjunto S en dos subconjuntos bajo las siguientes restricciones?

Existencia de un subconjunto tal que el producto de sus elementos es un cuadrado perfecto