Legalább hány százalék lesz a közös rész?

Ha csak két halmaz adatait adnák meg, a metszetre a becslés a szita formula alapján

történhet. Legyenek a számosságok egészek és |U|=100, |A|=92, |B|=86. (A∪B) komplemensének számosságát t-vel jelölve, ekkor |A\B|+|A∩B|+|B\A|+t=100,

|A\B|+|A∩B|=92, |B\A|+|A∩B|=86 egyenletrendszert megoldva kapjuk, hogy |A\B|=14-t, |A∩B|=t+78, |B\A|=8-t. Tehát min(|A∩B|)=78. Hasonlóan nyerhetők min(|B∩C|)=68 és min(|A∩C|)=74 becslések is.

Három halmaz adataival bonyolultabb a helyzet, mert az egyenletek száma lényegesen alúlmarad az ismeretlenekhez képest. Konkrétan 11 ismeretlennel 8 db. egyenlet írható fel. Egyrészt igaz az, hogy |A∪B∪C|=|B\C|+|C\A|+|A\B|+|A∩B∩C|, másrészt igaz az is, hogy |B\C|+|C\A|+|A\B|=|B\A|+|A\C|+|C\B|. Továbbá |A\B|+|A∩B|=92 és

|A\C|+|A∩C|=92; |B\A|+|A∩B|=86 és |B\C|+|B∩C|=86; |C\A|+|A∩C|=82 és |C\B|+|B∩C|=82.

A folytatáson érdemes még elgondolkozni. Sz. Gy

Folytatom a fenti #1/1 gondolatmenetet.

Az A⋃B⋃C halmaz az U alaphalmazon hét diszjunkt halmaz egyesítéseként fogható fel.

Legyen ezeknek a elemszámai b=|(B\A)\C|, z=|C\(B\A)|, a=|(A\C)\B|, y=|B\(A\C)|, c=|(C\B)\A|, t=|A\(C\B)| és végül x=|A⋂B⋂C|. Ezekre felírható egy kezelhető egyenletrendszer. |A|=a+x+y+t=92, |B|=b+y+x+z=86, |C|=c+x+z+t=82 valamint |U|=a+b+c+x+y+z+t+d=100, ahol d az A⋃B⋃C halmaz komplementerének az elemszáma. Feltehető, hogy az ismeretlenek és paraméterek nemnegatív egészek lesznek. Ez a paraméteres egyenletrendszer megoldható (x,y,z,t)-re, amelynek megoldása a következő:

x=a+b+c+2d+60, y=18-(a+b+d), z=8-(b+d+c) valamint t=14-(a+c+d). Nekünk x minimumát kell megkeresnünk. Feltehető, hogy ebben az esetben a=b=c=d=0 és így a min(x)=60. x=60, y=18. z=8 és t=14 ki fogja elégíteni az egyenletrendszerünket, így a feladat feltételeit is. Így a szóban forgó közös rész legalább 60%-os lesz. Sz. Gy.