Wie groß ist die Mindestanzahl von Mengen, bei denen das Produkt der Elemente in jeder kleiner als k ist?

Question

Wie groß ist die Mindestanzahl von Mengen, bei denen das Produkt der Elemente in jeder kleiner als k ist?

Mathematik
Kombinatorik
Zahlentheorie
Set-Partition
elementare Mengenlehre
Extremal-Kombinatorik

void_117

Gegeben sei eine positive Zahl n und eine positive Zahl k. So finden Sie die Mindestanzahl von Mengen, sodass für jede Menge s das Produkt aller Elemente in s kleiner oder gleich k ist.

Außerdem sollten alle Mengen nur Elemente von 1 bis n (beide einschließlich) enthalten. Und jede Zahl von 1 bis n sollte in genau einer Menge enthalten sein.

Mein Ansatz bestand darin, zuerst die Quadratwurzel von k zu finden (es sei t). Und dann teilen Sie die Zahlen von 1 bis n in 2 Teile. Der erste Teil hat Zahlen kleiner oder gleich t, der zweite Teil hat Zahlen größer als t und kleiner als gleich n. Dann können wir sagen, dass keine zwei Zahlen im zweiten Teil in derselben Menge sein können, weil ihr Produkt mehr das k sein wird. Aber das beantwortet die Frage nicht vollständig. Wie es geht?

Saulspatz

Willkommen bei MSE. Bitte verwenden Sie MathJax, um Ihre Beiträge zu formatieren. Umgeben Sie zunächst mathematische Ausdrücke (einschließlich Zahlen) mit $Vorzeichen und verwenden Sie sie _für Indizes. $x_1$ kommt heraus als

x_{1}

$x_1$ .

Saulspatz

Das Produkt aller Zahlen ist

n!

$n!$ und so sind wir haben

s

$s$ Sets, müssen wir haben

n! \leq k^{s}

$n!\leq k^s$ oder

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

$s\geq\left\lceil\frac{\log n!}{\log k}\right\rceil$ Also, wenn wir es schaffen, damit umzugehen

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

$\left\lceil\frac{\log n!}{\log k}\right\rceil$ , wissen wir, dass wir das Minimum erreicht haben. Ich weiß nicht, ob das immer möglich ist, und ich kenne auch keinen guten Algorithmus, um die Mengen zu konstruieren.

Ross Millikan

Ein viel besserer Weg, das Problem anzugeben, wäre, nach der Partition von zu fragen

{1, 2, 3, \dots n}

$\{1,2,3,\ldots n\}$ so dass das Produkt jedes Elements der Partition kleiner als ist

k

$k$ und die Anzahl der Sätze in der Partition wird minimiert.

RobPratt

@Saulspatz

(n, k) = (4, 5)

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

3

$3$ bins, strikt größer als die untere Grenze von

2

$2$ .

Antworten (1)

Wie groß ist die Mindestanzahl von Mengen, bei denen das Produkt der Elemente in jeder kleiner als k ist?

Willkommen bei MSE. Bitte verwenden Sie MathJax, um Ihre Beiträge zu formatieren. Umgeben Sie zunächst mathematische Ausdrücke (einschließlich Zahlen) mit $Vorzeichen und verwenden Sie sie _für Indizes. $x_1$ kommt heraus als $x_1$ .
Das Produkt aller Zahlen ist $n!$ und so sind wir haben $s$ Sets, müssen wir haben $n!\leq k^s$ oder $s\geq\left\lceil\frac{\log n!}{\log k}\right\rceil$ Also, wenn wir es schaffen, damit umzugehen $\left\lceil\frac{\log n!}{\log k}\right\rceil$ , wissen wir, dass wir das Minimum erreicht haben. Ich weiß nicht, ob das immer möglich ist, und ich kenne auch keinen guten Algorithmus, um die Mengen zu konstruieren.
Ein viel besserer Weg, das Problem anzugeben, wäre, nach der Partition von zu fragen $\{1,2,3,\ldots n\}$ so dass das Produkt jedes Elements der Partition kleiner als ist $k$ und die Anzahl der Sätze in der Partition wird minimiert.
@Saulspatz $(n,k)=(4,5)$ erfordert $3$ bins, strikt größer als die untere Grenze von $2$ .

RobPratt · Answer 1

Sie können dies als Bin-Packing-Problem lösen , wo die $n$ Gegenstände haben Gewichte $\log 1, \dots, \log n$ und jeder Behälter hat Kapazität $\log k$ .

Wie groß ist die Mindestanzahl von Mengen, bei denen das Produkt der Elemente in jeder kleiner als k ist?

void_117

Saulspatz

Saulspatz

Ross Millikan

RobPratt

Antworten (1)

RobPratt

Wie viele nahezu perfekte Permutationen gibt es?

Minimale Anzahl von Partitionen einer gegebenen Liste von Zahlen, die nicht in derselben Partition erscheinen können

Eine Frage zu einem Sonderfall des Inklusions-Exklusions-Prinzips

Hat die Collatz-Regel 3x+53x+53x+5 eine Verzerrung für bestimmte Schleifen oder sind meine Ergebnisse fehlerhaft?

Wie viele Lösungen gibt es bei ggT und LCM von n positiven ganzen Zahlen?

kombinatorischer Identitätsnachweis mit Multisets

Zwei Reihenbeziehungen, jede impliziert die andere - aus Andrews' Partitionsbuch

Auswahl eines Elements aus jeder Menge von Mengen, sodass keine zwei Elemente gleich sind.

tWie viele Möglichkeiten gibt es, eine Menge S unter den folgenden Einschränkungen in zwei Teilmengen aufzuteilen?

Existenz einer Teilmenge, so dass das Produkt seiner Elemente ein perfektes Quadrat ist