Útgáfa síðunnar 9. nóvember 2005 kl. 16:17 breyta Friðrik Bragi Dýrfjörð (spjall \| framlög) 5.905 breytingar m interwiki, af hverju er talað um kassa og skúffur sitt á hvað? ← Eldri breyting		Útgáfa síðunnar 9. nóvember 2005 kl. 17:48 breyta taka aftur þessa breytingu Friðrik Bragi Dýrfjörð (spjall \| framlög) 5.905 breytingar m Einföldun að ég held. Nýrri breyting →
Lína 1: '''Skúffuregla Dirichlets''' er regla sem segir að; ef ''k'' hlutir eru settir í ''N'' skúffur, þar sem ''k > N'' (hlutirnir eru fleiri en skúffurnar), þarf minnst að kosti ein skúffan að innihalda fleiri en einn hlut. Viðfang reglunar er mikilvægt í [[talnafræði]]. '''Skúffuregla Dirichlets''' er regla í [[talningafræði]] sem snýr að því að svara þeirri spurningu hvort að hægt sé að setja ''k'' hluti í ''N'' skúffur án þess að þörf sé að setja tvo hluti í eina og sömu skúffuna. Höfundur þessarrar reglu, [[G. Lejeune Dirichlet]], notaði samlíkingu við dúfur (''k'') og dúfnaholur (''N'') og því er reglan kölluð ''The pidgeonhole principle'' á ensku. Á íslensku hefur myndast sú hefð að kalla þetta skúffureglu, og þá væri hægt að orða dæmi þannig að „''Ef að ''k'' hlutir eru látnir í ''n'' skúffur og <math>k > m</math> þá lenda að minnsta kosti tveir hlutir í sömu skúffunni.''“. Höfundur þessarrar reglu, [[G. Lejeune Dirichlet]], notaði samlíkingu við dúfur (''k'') og dúfnaholur (''N'') og því er reglan kölluð „the pidgeonhole principle“ á ensku (einnig þekkt sem „Dirichlet's Box Principle“). Á íslensku hefur myndast sú hefð að kalla þetta skúffureglu. Almenna skúffureglan er þannig: Ef að ''k'' hlutir eru settir í ''N'' kassa, þá er að lágmarki til einn kassi sem inniheldur <math>\left\lceil \frac{k}{N} \right\rceil</math> hluti.▼ ▲Almenna skúffureglan er þannig: Ef að ''k'' hlutir eru settir í ''N'' ~~kassa~~skúffur, þá er að lágmarki til ~~einn~~ein ~~kassi~~skúffa sem inniheldur <math>\left\lceil \frac{k}{N} \right\rceil</math> hluti. == Sönnun == Gerum ráð fyrir því að ~~enginn~~engin ~~kassi~~skúffa inniheldur meira en <math>\left\lceil \frac{k}{N} \right\rceil - 1</math> hluti. Þá er heildarfjöldi hluta að hámarki :<math>k \left( \left\lceil \frac{k}{N} \right\rceil \right) < k \left( \left( \frac{k}{N} + 1 \right) - 1 \right) = k</math>, Lína 12 ⟶ 14: == Dæmi == Í 100 manna hópi eru að lágmarki <math>\left\lceil \frac{100}{12} \right\rceil = 9</math> manns sem eiga afmæli í sama mánuði. ==Tenglar== * [http://www.cut-the-knot.org/do_you_know/pigeon.shtml Pigeonhole Principle] * [http://mathworld.wolfram.com/DirichletsBoxPrinciple.html Einföld útskýring á MathWorld] {{stubbur}} [[Flokkur:Stærðfræði]] [[Flokkur:Fléttufræði]]

„Skúffuregla Dirichlets“: Munur á milli breytinga