Задача про набор элементов группы

[VoloCh]

Может, не в этот раздел, может, это шуточная задача?
Пусть $G\text{ ---}$ конечная группа мощности $n$. Конечное непустое множество $F$, состоящее из элементов группы $G$, назовем фракцией. Фракцию назовем партией, если из фракции можно выбрать представителей $f_1,\ f_2,\ldots$, которые, построившись в ряд, с помощью групповой операции дадут групповую едининцу $f_1\cdot f_2\cdot f_3\cdot\ldots=e.$
Вопрос: Сколько членов должно быть во фракции, чтобы она навярняка считалась партией?
Замечания:
1. Элементы группы {\scriptsize $G$} могут повторяться в множестве {\scriptsize $F$}.
2. Коммутативность не предполагается, но она не существеннa.

[Хорхе]

Как я понял, $F$ -- мультимножество, а "представители" -- мультиподмножество $F$.

В любом случае, ответ $n$. Это почти что классическая задача (по крайней мере, решается в точности так же): доказать, что из $n$ чисел можно выбрать несколько, сумма которых делится на $n$.

(Оффтоп)

Автор прав: это не задача

[VoloCh]

Хорхе, а если можно, если "почти классическая", ну и если можно изложить в несколько строк - просветите, плиз.

[Хорхе]

Пусть $F=\{a_i,\ i=1,\dots,n\}$. Положим $p_k=\prod_{i=1}^k a_i$, $k=1,\dots,n$. Если какое-то из этих $p_i$ равно единице, то доказано. Иначе по принципу Дирихле среди них есть два одинаковых. Поделив одно на другое, получим то, что надобно. Ну а пример с $n$ Вы, думаю, и сами знаете.

[Профессор Снэйп]

Хорхе в сообщении #301230 писал(а):

Как я понял, $F$ -- мультимножество, а "представители" -- мультиподмножество $F$.

А я не так понял. И условие мне, увы, не до конца понятно

Что найти надо? Минимальное $n$, при котором из любого подмножества группы $G$ мощности $n$ можно организовать единичное произведение? Если в произведении члены могут повторятся, то ясно, что минимальное $n$ для любой конечной группы равно $1$. А если не могут, то это уже более сложная задача.

Вот, к примеру, $G = \mathbb{Z}_4$. Для неё, похоже, $n=3$. Так? Или всё-таки $2$. Или $1$?

[Хорхе]

Я так понял условие: найти минимальное $m$, что для любой группы $G$ порядка $n$ из любого набора $(a_1,\dots,a_m)$ элементов $G$ можно выбрать поднабор $(a_{i_1},\dots,a_{i_k})$ ($i_j\neq i_l,j\neq l$), что $a_{i_1}\dots a_{i_k} = e$.

Видимо, слово "множество" в первом посте автора абсолютно лишнее, только чтобы сбить с толку.

[Профессор Снэйп]

Хорхе в сообщении #301439 писал(а):

Я так понял условие: найти минимальное $m$, что для любой группы $G$ порядка $n$ из любого набора $(a_1,\dots,a_m)$ элементов $G$ можно выбрать поднабор $(a_{i_1},\dots,a_{i_k})$ ($i_j\neq i_l,j\neq l$), что $a_{i_1}\dots a_{i_k} = e$.

Да, наверное, именно это и имелось в виду

Тогда для $G = \mathbb{Z}_4$ это минимальное $m$ равно четырём (с набором $(1,1,1)$ ноль никак не получишь). А для общего случая конечной группы я, честно говоря, не вижу простого решения.

Интересно на частные случаи сначала поглядеть. К примеру, для $G = \mathbb{Z}_n$ это $m$ равно $n$. А для $G = S_n$ чему равно это минимальное $m$? Мне почему-то кажется, что не $n!$, а меньше

[VoloCh]

Хорхе в сообщении #301295 писал(а):

Пусть $F=\{a_i,\ i=1,\dots,n\}$. Положим $p_k=\prod_{i=1}^k a_i$, $k=1,\dots,n$. Если какое-то из этих $p_i$ равно единице, то доказано. Иначе по принципу Дирихле среди них есть два одинаковых. Поделив одно на другое, получим то, что надобно.

Простите, опять я не врубилсо! Ежели есть единица, то таки да, все понятно! Если есть одинаковые, то что? Если там все $n$ одинаковых, - тоже понятно вроде. Но вот "поделив одно на другое, получим что надо" - это пока (лично мне) не ясно. И, кажется, я тут не одинок: вражище Снэйп вот подтверждает

Профессор Снэйп в сообщении #301453 писал(а):

А для общего случая конечной группы я, честно говоря, не вижу простого решения.

[Хорхе]

Вообще-то я написал двумя постами решение для общего случая конечной группы.

А поделить просто: если $a_1\dots a_{k_1} = a_1\dots a_{k_2}$, $k_1<k_2$, то $a_{k_1+1}\dots a_{k_2} = e$.

В некоторых случаях это число, конечно, может быть меньше. У меня чувство, что самое маленькое оно для $Z_2^m$, $m+1$.

[VoloCh]

Хорхе в сообщении #301493 писал(а):

Вообще-то я написал двумя постами решение для общего случая конечной группы.

А поделить просто: если $a_1\dots a_{k_1} = a_1\dots a_{k_2}$, $k_1<k_2$, то $a_{k_1+1}\dots a_{k_2} = e$.

В некоторых случаях это число, конечно, может быть меньше. У меня чувство, что самое маленькое оно для $Z_2^m$, $m+1$.

А кто сказал, что $a_{k_1+1}\dots a_{k_2} \in F$? И еще - я (каюсь) ваще-то с алгеброй не знаком и не знаю что такое $Z_2^m$.

[Хорхе]

Никто такого и не говорил. Это, в общем-то, и не требуется.

А на $Z_2^m$ (корректней, наверное, писать $C_2^m$) можно, к примеру, смотреть как на класс подмножеств $m$-элементного множества с операциeй $A\cdot B = (A\setminus B)\cup (B\setminus A)$, симметричной разностью.

[VoloCh]

Ох-Ох! Ну, конечно, же вы все сразу доказали! Я вот это просвистел

Хорхе в сообщении #301295 писал(а):

Положим $p_k=\prod_{i=1}^k a_i$, $k=1,\dots,n$.

А потом у меня в голове перепутались $p_k$ и $a_k$... Все верно.

-- Вт мар 23, 2010 22:35:21 --

Н-да... получилось неудачное обобщение именно "олимпиадной" задачи.
Рассказываю.

На доске в строчку написаны все возможные комбинации из плюс и минус единиц длины $n$. (Другими словами, дана таблица размером $n\times 2^n$, и заполненная $\pm1$). Некто подошел к доске и заменил некоторые $\pm1$ на 0. Доказать, что из "испорченной" таблицы (из $2^n$ строк) можно выбрать несколько строк таким образом, что эти строки в сумме дадут ноль (сложение осуществляется обычным образом, покоординатно).

Хотя теперь и не знаю... олимпиадность заковычил... Щас Хорхе опять все решит в момент.

[Профессор Снэйп]

Хорхе в сообщении #301493 писал(а):

Вообще-то я написал двумя постами решение для общего случая конечной группы.

Простите, я его что-то не могу углядеть Доказательство неравенства $m(G) \leqslant |G|$ увидел, а выражение для $m(G)$ --- нет.

В частности, чему равно $m(S_n)$?

[Хорхе]

Профессор Снэйп, я такого и доказывал, вот как я сформулировал:

Цитата:

найти минимальное $m$, что для любой группы $G$ порядка $n$

Найти $m(G)$ --- безнадежная, мне кажется, задача.

-- Ср мар 24, 2010 09:51:39 --

Ну разве что для абелевой группы можно посчитать.

[mihiv]

Если все элементы набора различны,то m меньше n.Рассмотрим,например,группу с нечетным $n>3$,и составим набор из $\frac {n+3}2$ элементов группы,в этом наборе обязательно найдется пара элементов произведение которых равно e,в противном случае среди оставшихся $\frac {n-3}2$ элементов группы не нашлось бы обратных для всех элементов набора.