Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Nehezebb matematikai problémák

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]  

Szeretnél hozzászólni? Jelentkezz be.
[320] Károly2006-07-14 08:38:04

Köszönöm a bizonyítást!

Nevezzük az idempotens, kommutatív, reguláris és hurokmentes táblákat K-tábláknak, hogy tudjunk róluk beszélni! Az eddigiek szerint

1. Ha G olyan 1-nél több elemű Abel-csoport, hogy a2=b2\impliesa=b és a3=b3\impliesa=b, akkor a G-ből képzett a * b := \sqrt{ab} művelet K-tábla. Az ilyen csoport neve legyen E-csoport!

2. Véges E-csoportok elemszáma nem lehet 2-vel illetve 3-mal osztható, mert ebben az esetben van bennük 2- ill. 3-elemű direkt osztó, amelyben a2=b2 ill. a3=b3 úgy, hogy a\neb. Azaz, ha a K-tábla ilyen csoportból keletkezik, akkor elemszáma nem lehet 2-vel vagy 3-mal osztható.

3. Ha a K-tábla E-csoportból keletkezik, a +n művelettel (a+nb=c\leftarrow\rightarrowa*b=c*n) visszakapjuk az E-csoport egy izomorf képét, a képben az egységelem az n.

4. Vannak nem E-csoportból származó K-táblák. Az ilyen (véges) K-táblák elemszáma továbbra sem lehet páros, 3-mal osztható viszont igen.

5. A (4) pontban említett K-táblák esetében a +n művelet nem asszociatív, és (a*b)*(b*c)=b*(a*c) sem teljesül.

Ezek igazak?

Üdv

Károly

Előzmény: [319] 2501, 2006-07-13 20:13:37
[319] 25012006-07-13 20:13:37

Tétel: nincs páros elemszámú ilyen struktúra.

Biz.: Próbáljuk megadni az a*b = c műveletet az Ma,b = c mátrix kitöltésével (ahogyan az [311]-ben és [314]-ben látható). A művelet idempotens (1), tehát az (a=b) átlót teljesen kitöltjük: M0,0 = 0, M1,1 = 1 stb. A művelet kommutatív (2), és megoldhatók az a*x = b egyenletek (3), tehát a mátrix az átlóra szimmetrikus, és minden sorban illetve oszlopban minden érték pontosan egyszer szerepel. Ezért az első (jobban mondva 0.) sor illetve oszlop elhagyásával kapott részmátrixban el kell még helyeznünk annyi 0-t, amennyi sora (illetve oszlopa) van, tehát páratlan számút. Ahhoz viszont, hogy a mátrix szimmetrikus legyen, páros számú 0-t kellene elhelyeznünk, mivel az átló már teljesen be van töltve. Ez ellentmondás, a mátrixot nem lehet kitölteni, tehát a művelet nem létezik páros elemszámú struktúrán.

Előzmény: [300] Károly, 2006-07-06 16:18:33
[318] Károly2006-07-12 21:13:57

Továbbmenve azt kaptam, hogy léteznek 9-elemű táblák, úgyhogy az előbbi sejtés megbukott.

(A páratlan még tartja magát...)

Károly

Előzmény: [317] Károly, 2006-07-12 21:08:21
[317] Károly2006-07-12 21:08:21

Jó, nem bizonyítás...:-)) Hanem csak egy gondolatmenet, amely arra utal, hogy nincsenek 2-vel és 3-mal osztható elemszámú véges struktúrák.

A gondolatmenet arra épül, hogy ha ez a struktúra egy Abel-csoportból képződik

ac=b\leftarrow\rightarrowac=b2

definícióval, akkor a csoport rendje, amelyből létrejön, nem lehet 2-vel vagy 3-mal osztható. Csakhogy - amint az Általatok bemutatott példák illusztrálják - nem csak csoportból jöhet létre ilyen struktúra. A +n-es "visszacsinálási" módszer sem megy minden ilyen táblára, a +n ugyanis nem lesz feltétlenül asszociatív.

Ettől függetlenül lehetséges, hogy a 2-vel vagy 3-mal oszthatóság tilalma öröklődik ezekre a táblákra, de ezt még nem tudom.

Károly

Előzmény: [316] Károly, 2006-07-11 21:38:19
[316] Károly2006-07-11 21:38:19

Nincs páros elemszámú és nincs olyan sem, amelynek elemszáma 3-mal osztható. A bizonyítás megvan, ha kéritek, majd fölteszem.

Károly

Előzmény: [315] lgdt, 2006-07-11 21:26:05
[315] lgdt2006-07-11 21:26:05

Köszi. Úgy néz ki, hibás volt a kódom. Elvileg az enyém is megtalálta volna az összes lehetőséget. :) Most bizonyítsuk be vagy cáfoljuk meg, h nincs páros elemszámú!

[314] 25012006-07-11 21:20:06

Írtam egyet én is: forrás

Ez 5-ösből (és valószínűleg 7-esből is, azt nem számoltam meg :D) többet talál: lista

Előzmény: [311] lgdt, 2006-07-11 16:45:41
[313] Károly2006-07-11 17:42:40

Bocs, közben rájöttem, hogy hogy kell nézni... A fejléc mindenütt 0, 1, ... n - 1. Látom a táblákról, hogy idempotensek, kommutatívak, regulárisak. A hurokmentességet kapásból nem látom, de biztos úgy van. Akkor ezek ellenpéldák, és köszönöm.

Károly

Előzmény: [311] lgdt, 2006-07-11 16:45:41
[312] Károly2006-07-11 17:19:44

Milyen szabályokkal hoztad létre ezeket a struktúrákat? Ha jól olvasom őket (nem biztos, hogy jól olvasom, mert fej- és oldalléceket nem látok), ezek a struktúrák nem idempotensek.

Károly

P.S.: Használsz valamilyen matematikai programot, vagy ez egy SQL-eredmény?

Előzmény: [311] lgdt, 2006-07-11 16:45:41
[311] lgdt2006-07-11 16:45:41

Nekem most úgy tűnik, hogy nem igaz (az asszociativitás hiányából nem következik, hogy ez van helyette).

Itt van 8-ig az összes véges struktúra, hételemű a legelső, amire nem teljesül az állítás. Kérlek, ellenőrizz le egy ellenpéldát, hogy biztosan nem értettem-e félre valamit.

De vajon az igaz, hogy csak páratlan elemszámú ilyen struktúra létezik a végesek között?

Előzmény: [310] Károly, 2006-07-10 21:05:50
[310] Károly2006-07-10 21:05:50

Bocs mindenkitől: (ab)(bc)=b(ac). Ez a kérdés.

Károly

Előzmény: [309] lgdt, 2006-07-10 15:06:54
[309] lgdt2006-07-10 15:06:54

már csak az átlagolóssal is a=c=1, b=3 nekem ellenpéldának tűnik. javíts ki, ha tévedek!

Előzmény: [308] Károly, 2006-07-09 17:17:55
[308] Károly2006-07-09 17:17:55

Kösz! Persze! "Elszámoltam" magam. Rossz szelektet írtam (ezeket a táblákat SQL-ben nézegetem).

Vagyis a +n visszaadja az 5-elemű ciklikus csoportot, melynek egységeleme n.

Ez már olyan, mintha lenne egy tételünk...:-))

Szerinted az axiómákból le lehet-e vezetni, hogy (ab)(ac)=b(ac) vagy esetleg van ellenpélda?

(Vagy, ami ezzel szorosan összefügg: be lehet-e bizonyítani, hogy az ab létezik definícióval adott reláció ekvivalenciareláció?)

Még egyszer nagyon köszönöm, hogy kijavítottál.

Üdv

Károly

Előzmény: [307] 2501, 2006-07-09 16:01:49
[307] 25012006-07-09 16:01:49

Szervusz!

Szerintem elszámoltál (illetve "-betűztél" :)) valamit. Az a+nb=c \equiv a*b=c*n definícióból következik, hogy a+nzn=a \equiv a*zn=a*n (ahol zn az egység). Ebből már következik, hogy zn=n, feltéve, hogy az fa(b)=a*b függvény injektív.

Előzmény: [306] Károly, 2006-07-07 19:28:39
[306] Károly2006-07-07 19:28:39

Neeem!

Nagyon örülök, hogy rögtön vágtad.

Mutatok egy nemtriviális véges példát:

a b c d e
a a d b e c
b d b e c a
c b e c a d
d e c a d b
e c a d b e

(Húú - régen TeX-eltem...!! :-)

Ez a tábla természetesen a mod 5 additív csoportból készült - úgy, ahogy mondtad - átlagokkal.

Namost. Vissza lehet-e kapni ebből az algebrai struktúrából az 5-elemű ciklikus csoportot?

A gondolatmenet a következő: Vezessük be erre a szorzótáblára építve az a+nb műveletet, melynek eredménye c, ha ab=cn (a szorzatokat itt az én táblámban kell leolvasni). Az n természetesen a struktúra egyik rögzített eleme.

Az eljárás szépen vissza is adja az 5-elemű ciklikus csoportot. Eddig csupa derű. Csakhogy: melyik elem lesz az így visszakapott ciklikus csoport egységeleme?

Ha erre a kérdésre az átlaggal kívánsz választ adni, a következőt mondod: Most

ab = \frac{a+b}2,

tehát

a +_n b = c \leftarrow\rightarrow \frac{a+b}2 = \frac{c + n}2 \leftarrow\rightarrow c = a + b - n.

Az így kapott művelet

asszociatív, mert (a+nb)+nc=a+b+c-2n

egységelemes, egységelem az n, mert a+nn=a+n-n=a

invertálható, a inverze 2n-a

és kommutatív (ami triviális), tehát tényleg Ábel-csoport.

És - figyelem - egységeleme az n.

Na ezzel szemben ennek a táblának a származtatott +n-je így viselkedik:

Ha n = a b c d e
akkor az egységelem a e d c b

Vagyis az egységelem nem n, hanem az nx=a egyenlet megoldása (úgy is írhatnám ez esetben, hogy an-1.

Honnan van a-nak ez a kitüntetett szerepe? Úgy érzem, a táblázat teljesen szimmetrikus az öt betűre nézve. Vagy elszámoltam valamit?

Köszönöm

Károly

Előzmény: [305] 2501, 2006-07-07 10:24:38
[305] 25012006-07-07 10:24:38

> Nem úgy értettem, hogy mondjatok példát.

Sejtettem, hogy mégis rosszul értem; túl egyszerű volt. :)

Előzmény: [302] Károly, 2006-07-07 09:02:34
[304] Károly2006-07-07 09:21:00

Más: Ti hogy tanultátok a definíciót?

f felbonthatatlan, ha f = ab-ból az következik, hogy vagy f és a vagy f és b asszociáltak.

Avagy

f felbonthatatlan, ha f = ab-ből az következik, hogy vagy a vagy b egység.

Köszönöm

Károly

[303] Károly2006-07-07 09:19:22

Abbahagyva a hülyéskedést, én eddig a következőket látom:

(1) Ha a struktúra véges, akkor (1.a) A 2. axióma sima kommutativitásba megy át. (1.b) A 4. axióma tétel.

(2) Az 5. axióma független, mert van nemtriviális példa 1-4-re, úgy, hogy 5. nem teljesül.

Kösz

Károly

Előzmény: [300] Károly, 2006-07-06 16:18:33
[302] Károly2006-07-07 09:02:34

Nem úgy értettem, hogy mondjatok példát. (A példa egyébként jó.:-) Hanem úgy, hogy valaki azt mondja, hogy igen, van ilyen algebrai struktúra, korbácsnak hívják, és Vittorio d'Assistenza olasz matematikus publikált tételeket a Zeitschrift der angewandten Nabelschau-ban.

Károly

Előzmény: [301] 2501, 2006-07-06 23:26:24
[301] 25012006-07-06 23:26:24

Szervusz!

Pl.: az elemek (mondjuk) számok, a művelet pedig az átlag.

(Remélem nem néztem el semmit. :))

Előzmény: [300] Károly, 2006-07-06 16:18:33
[300] Károly2006-07-06 16:18:33

Sziasztok!

Új vagyok, ha nem jó helyen járok, irányítsatok át!

Szükségem lenne egy algebrai struktúrára, a következő axiómákkal:

1. Idempotencia: aa = a 2. "Kommutativitás": ab =?= ba (Ezt a jelölést én találtam ki; olvasd: ab, ha létezik, egyenlő ba-val. Ez amolyan "kváziművelet", nem minden ab létezik, de ha létezik, akkor ba is létezik, és egyenlő ab-vel.) 3. Megoldhatók x-re az ax = b egyenletek. 4. Az ax = a egyenlet egyetlen megoldása: x = a. 5. Hurokmentesség: (ab = c és ac = b) => b = c (És ekkor már a = b = c.)

(Asszociativitás nincs!)

Ráismertek-e valami hasonlóra? Van-e neve? Vannak-e tételek?

Köszönöm

Károly

[299] joe2006-06-02 19:48:53

138. feladat: (Ha nem tévedek.)

Azt mondjuk, hogy a k számot öröklődő n alapú számrendszerben írjuk föl, ha a k számot a következőképpen fejezzük ki: Írjuk föl a k számot (a hagyományos módon) n alapú számrendszerben, majd az együtthatókat "fejtsük ki", tehát a_i n^\alpha_i helyett írjunk ai darab összeadandót: n^\alpha_i + n^\alpha_i + ... + n^\alpha_i. Az így kapott kifejezésben minden kitevőt írjunk öröklődő n alapú számrendszerbe (tehát ismételjük meg az n alap minden kitevőjére az imént leírt eljárást; majd a kitevőkben szereplő számok kitevőire, és így tovább). Ezt az eljárást addig folytatjuk, amíg a kifejezésben csak a + jel, az n szám és a 0 szerepel (tehát az 1-et n0 -nak írhatjuk). Ez a rekurzív eljárás véges sok lépésben véget ér, és a k szám egyértelmű öröklődő n alapú számrendszerbeli alakját adja.

Definiáljuk a következő sorozatot: a0:=k, ahol k természetes szám;

Minden i természetes számra:

Ha ai-1 nem pozitív egész, a sorozatnak nincs több tagja.

Ha ai-1 pozitív egész, akkor írjuk föl azt öröklődő i+1 alapú számrendszerben; az így kapott kifejezésben MINDEN (i+1) számot cseréljünk ki (i+2)-re, számítsuk ki az így keletkezett kifejezés értékét, és az ennél eggyel kisebb számérték legyen ai.

Melyek azok a k természetes számok, melyekre a0=k esetén az ai sorozat véges?

[298] stephen2006-05-26 11:10:34

Köszönöm a választ, megnézem.

Előzmény: [297] Lóczi Lajos, 2006-05-25 15:07:12
[297] Lóczi Lajos2006-05-25 15:07:12

A

http://mathworld.wolfram.com/CoinTossing.html

http://mathworld.wolfram.com/Run.html

http://mathworld.wolfram.com/Fibonaccin-StepNumber.html

oldalakon mindenféle szép rekurziókat meg generátorfüggvényeket fogsz találni olyan kérdésekről, hogy pl. "mennyi az esélye, hogy n dobásban nincs k egymásutáni írás", vagy hogy "mennyi az esélye, hogy egy n hosszú dobássorozatban előfordul egy legalább k hosszúságú fejsorozat".

Előzmény: [296] stephen, 2006-05-25 10:04:42
[296] stephen2006-05-25 10:04:42

Nagyon érdekelne az alábbi feladat megoldása:

Feldobunk n pénzérmét. Mennyi a valószínűsége, hogy lesz legalább k egyforma (fej vagy írás) egymás mellett?

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]