Udregning af kombinationsmuligheder, hjælp søges

Med ≥255 menes der: antal kombinationer der giver et antal af stemmer lig med eller over 255 stemmer.
Den kan åbenbart ikke finde ud af tegnet.

Hvad er det I gerene vil have?

Antallet?
Eller et program til at udregne det?

Jeg kan ikke lave det i TI interactie (da jeg ikke kender det) man I kan få en version i C# hvis det har interesse.

Jeg kan ikke gennemskue hvad det tal skal bruges til, men ok:

Der er 27 lande, og de kan enten stemme "oui" eller "non". Dvs. der er 2^27 (to opløftet til syvogtyve) mulige stemmeafgivninger. Hvis min lommeregner ellers regner rigtigt er det omkring 134 millioner muligheder.

Hvis alle landende havde lige mange stemmer, ville ca. halvdelen give alm. flertal. Men selv om de har forskellige stemmeantal, så udligner det hinanden, så resultatet igen bliver rundt regnet halvdelen.

Altså: der er omkring 60-70 millioner kombinationer af stemmeafgivninger, der giver et alm. flertal.

Kvalificeret flertal vil tilsvarende give ca 1/4-del af alle muligheder, omkring 30-35 millioner muligheder.

Man kan selvfølgelig på nogle sekunder (minutter...) regne de præcise tal ud, når først man lige har tallene hakket ind i et program - men til hvad nytte ??

Uden at kunne løse det, tror jeg, at der efterspørges noget, der automatisk kan opliste noget i denne stil:

1 Tyskland, Frankrig ... Ungarn har flertal (257)
2 Samme, men hvor Sverige erstatter Ungarn har flertal (255)
3 osv. osv.

Givetvis hvad der efterspørges - men måske ikke alligevel, når den bliver på 30 millioner linier.

Nu vover jeg mig ud på dybt vand - Erik:

Hvis vi forudsætter, at stemmerne fra et land er ens. Altså f.eks. DK 7 ja eller 7 nej, bliver det langt værre kombinationer.

Men måske stadig et betragteligt antal?

Det var nu også sådan at jeg læste problemet: For et givet land antages det at alle stemmerne stemmer ens.

I alt 2718774 kombinationer.

Du har brugt tiden siden i går på at tælle efter - ok, 27 millioner er tæt nok på de 30 millioner jeg sjussede mig til ;)

Skal vi ikke bare sige at programmet tog betydelig længere tid at skrive end det tager at køre ;^)

Men så: det er jo rimeligt uanvendeligt, selv med det præcise tal - og hvis det er en samfundsfagslærer, der skal bedømme opgaven, vil han nok slet ikke tro på tallet.

Mere interessant er vel 2 ting:

1) Hvor få af de store lande skal der til for at nedtromle de små (læg sammen fra toppen). Tænk på Helmuth Kohl, der sætter sig på en spidsmus, og maser den flad
2) Hvor mange af de små lande skal der til for at sætte de store lande på plads (læg sammen nedefra)
3) Kan man finde 3-4-5 lande hvoraf mindst 1-2 skal være med i ethvert kvalificeret flertal (regn den selv ud).

Emnet er interessant og snakken hyggelig.

Og jeg fremturer: Er I ikke lidt i overkanten med de 27 mio.?

Svaret på eriks 1 er vel 13. 13 kan vælges i 20.058.300 kombinationer ud af 27.

Svaret på eriks 2 er vel 24. 24 kan vælges i 2.925 kombinationer ud af 27.

De to antal kombinationer må være absolut højeste og nederste grænse for det rigtige svar.

Hvis man regner med permutationer bliver tallene meget større. Men det må da være kombinationer, det drejer sig om her. Rækkefølgen af et givet landeudpluk er jo ligegyldig?

Jeg tror du har talt rigtigt med de 13 og 24.

Men det betyder også at det ikke kan lade sig gøre at få et kvalificeret flertal uden at enten Tyskland, Frankrig, Storbritannien eller Italien er med.

Se det er noget man kan skrive mange sider om, som vil få hjertet til at smelte på enhver samfundsfagslærer.

Man kan nemt bjæffe løs om "kvalificeret flertal", og prøve at se ud som om man mener det er en god ting. Men find lige en politker, der både vil sætte sig ned med lommeregneren og (korrekt) regne ovenstående ud, og bagefter vil sige at disse 4 store lande reelt tilsammen har vetoret mod beslutninger truffet ved kvalificeret flertal, se ... det bliver svært at finde ... hehe

"Er I ikke lidt i overkanten med de 27 mio.?" - underviser du i samfundsfag? Det er det korrekte tal, men man skal nok være specielt intellektuelt udfordret (matematiker) for at forstå det. Og iøvrigt er tallet i sig selv inderligt interessant.

Og iøvrigt er tallet i sig selv inderligt uinteressant.  <-- mente jeg nok

Min matematiklærer i gymnasiet sagde: Hvis I får en valgfri eksamensopgave i sandsynlighedsregning, så vælg den ikke. I kan kun lave den helt rigtig eller helt forkert. Dengang 11 eller 0.

Jeg er sikkert havnet i det sidste tilfælde.

Enig I, at tallet i sig selv er uinteressant. Men jeg gad godt se beregningen.

Som sagt - hyggeligt at pigerne ("to studiner") oprettede dette emne.

erik>

Det er kun 2.7 millioner ikke 27 millioner - problemet ligner en normal fordeling
ikke en uniform fordeling.

Vil I så straks holde op med at snakke om at gå til eksaminer i sandsynlighedsregning eller normalfordelinger – dette her er en opgave i kombinatorik. Et helt andet dyr.

Man kan kigge på spørgsmålet ud fra forskellige vinkler:


Matematikeren (guilty as charged): Opgaven er yderst interessant. Den har dog ikke nogen pæn og simpel løsning (hvilket selvfølgelig ikke er et kriterium i sig selv for matematikeren). Som svar på opgaven er tallet 2718774 ikke specielt intessant.

Som et tal i egen ret er 2718774 dog hverken mere eller mindre interessant end tal som 2 eller 1729 ( http://www.durangobill.com/Ramanujan.html ).


Programmøren : Givet et problem som dette er det da bestemt interessant at finde en algoritme som kan udregne tallet på en nogenlunde effektiv måde. Dvs. uden at skulle vente mere end 1-2 sekunder på svaret.

At man så kan få hæftet titlen ”computer-troldmand med kompetence!” på sig gør jo ikke sagen værre. Ak ja, forfængelighed kan være en rigtig grim ting. ;^)


Samfundsvidenskabeligt / Valgforskeren : Tja, i den sammenhæng er problemet (og dermed også svaret) nok rimeligt uinteressant. Som det allerede er påpeget er der masser af mere relevante problemer at kaste sig over.


Endeligt er det intet som dikterer at f.eks. alle Danmarks 7 stemmer skal stemme ens. Faktisk er også EU inddelt i ”partier” på samme måde som Folketinget er det.

Eh, ja, jeg regnede (gættede) og læste en faktor 10 galt - måske er det derfor de aldrig sætter mig til at lave budgetter ... ;)

Men stadig, hvis nogle vil have listen med de 2.7 millioner muligheder, så er jeg sikker på vi kan skaffe den! Man skal nok bare lige forklare, hvad man vil bruge det til.

<joke>
Hvis man nu sklal aflevere mindts N sider, saa kan et appendix med 2.7 millioner muligheder
listet hjaelpe ....
</joke>

Et lands stemmer vil aldrig blive delt.

Dette her er ikke EU parlamentet men ministerraadet.

Der deltager 1 minister fra hvert land og vedkommende har det antal stemmer
der er angivet.

Ok så fik jeg lavet et lille perlscript, der tager et par minutter om at køre. Der er kommentarer foran de linier, der vil kunne skabe overblikket over fordelingerne ved kvalificeret flertal. Et rigtig godt overblik på 2.7 mio linier ;)

#!/usr/bin/perl

$land[ 0]='Tyskland';      $antal[ 0]=29;$used[ 0]=0;
$land[ 1]='Frankrig';      $antal[ 1]=29;$used[ 1]=0;
$land[ 2]='Storbritannien';$antal[ 2]=29;$used[ 2]=0;
$land[ 3]='Italien';      $antal[ 3]=29;$used[ 3]=0;
$land[ 4]='Spanien';      $antal[ 4]=27;$used[ 4]=0;
$land[ 5]='Polen';        $antal[ 5]=27;$used[ 5]=0;
$land[ 6]='Rumænien';      $antal[ 6]=14;$used[ 6]=0;
$land[ 7]='Nederlandene';  $antal[ 7]=13;$used[ 7]=0;
$land[ 8]='Grækenland';    $antal[ 8]=12;$used[ 8]=0;
$land[ 9]='Portugal';      $antal[ 9]=12;$used[ 9]=0;
$land[10]='Belgien';      $antal[10]=12;$used[10]=0;
$land[11]='Tjekkiet';      $antal[11]=12;$used[11]=0;
$land[12]='Ungarn';        $antal[12]=12;$used[12]=0;
$land[13]='Sverige';      $antal[13]=10;$used[13]=0;
$land[14]='Østrig';        $antal[14]=10;$used[14]=0;
$land[15]='Bulgarien';    $antal[15]=10;$used[15]=0;
$land[16]='Danmark';      $antal[16]=7; $used[16]=0;
$land[17]='Slovakiet';    $antal[17]=7; $used[17]=0;
$land[18]='Finland';      $antal[18]=7; $used[18]=0;
$land[19]='Irland';        $antal[19]=7; $used[19]=0;
$land[20]='Litauen';      $antal[20]=7; $used[20]=0;
$land[21]='Letland';      $antal[21]=4; $used[21]=0;
$land[22]='Slovenien';    $antal[22]=4; $used[22]=0;
$land[23]='Estland';      $antal[23]=4; $used[23]=0;
$land[24]='Cypern';        $antal[24]=4; $used[24]=0;
$land[25]='Luxembourg';    $antal[25]=4; $used[25]=0;
$land[26]='Malta';        $antal[26]=3; $used[26]=0;

$count=0;

sub try {
  my ($n,$sum) = @_;

  if ($n>=$#antal && $sum>=255) {
    $count++;
#  my $i;
#    print "#$count: ";
#    for ($i=0;$i<=$#antal;$i++) {
#          print "$land[$i]($antal[$i]) " if ($used[$i]);
#  } 
#    print " = $sum\n";
  }

  if ($n<$#antal) {
    $used[$n+1]=1;
    try($n+1,$sum+$antal[$n+1]);
    $used[$n+1]=0;
    try($n+1,$sum);
  }
}

try(-1,0);

print "$count\n";

Min C-sjap løsning:

namespace e818025
{
    class Program
    {
        static void Main(string[] args)
        {
            int MaxL3 = 1;  // Malta
            int MaxL4 = 5;  // Letland, Slovenien, Estland, Cypern, Luxembourg
            int MaxL7 = 5;  // Danmark, Slovakiet, Finland, Irland, Litauen
            int MaxL10 = 3; // Sverige, Østrig, Bulgarien
            int MaxL12 = 5; // Grækenland, Portugal, Belgien, Tjekkiet, Ungarn
            int MaxL13 = 1; // Nederlandene
            int MaxL14 = 1; // Rumænien
            int MaxL27 = 2; // Spanien, Polen
            int MaxL29 = 4; // Tyskland, Frankrig, Storbritannien, Italien

            int CombinationsXX = 0;

            for (int L3 = 0; L3 <= MaxL3; L3++)
            {
                int Combinations3 = Combinations(MaxL3, MaxL3);

                for (int L4 = 0; L4 <= MaxL4; L4++)
                {
                    int Combinations4 = Combinations(MaxL4, L4);

                    for (int L7 = 0; L7 <= MaxL7; L7++)
                    {
                        int Combinations7 = Combinations(MaxL7, L7);

                        for (int L10 = 0; L10 <= MaxL10; L10++)
                        {
                            int Combinations10 = Combinations(MaxL10, L10);

                            for (int L12 = 0; L12 <= MaxL12; L12++)
                            {
                                int Combinations12 = Combinations(MaxL12, L12);

                                for (int L13 = 0; L13 <= MaxL13; L13++)
                                {
                                    int Combinations13 = Combinations(MaxL13, L13);

                                    for (int L14 = 0; L14 <= MaxL14; L14++)
                                    {
                                        int Combinations14 = Combinations(MaxL14, L14);

                                        for (int L27 = 0; L27 <= MaxL27; L27++)
                                        {
                                            int Combinations27 = Combinations(MaxL27, L27);

                                            for (int L29 = 0; L29 <= MaxL29; L29++)
                                            {
                                                int Combinations29 = Combinations(MaxL29, L29);

                                                int stemmerX = L3 * 3 + L4 * 4 + L7 * 7 + L10 * 10 + L12 * 12 + L13 * 13 + L14 * 14 + L27 * 27 + L29 * 29;

                                                if (stemmerX >= 255)
                                                {
                                                    int CombinationsX = Combinations3 * Combinations4 * Combinations7 * Combinations10 * Combinations12 * Combinations13 * Combinations14 * Combinations27 * Combinations29;
                                                    CombinationsXX += CombinationsX;

                                                    Console.WriteLine("{0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11}",
                                                        L3, L4, L7, L10, L12, L13, L14, L27, L29, stemmerX, CombinationsX, CombinationsXX);
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

        }

        // http://en.wikipedia.org/wiki/Combination
        private static int Combinations(int n, int k)
        {
            double comb = 1;

            while (k > 0)
            {
                comb *= n;
                comb /= k;

                n--; k--;
            }

            return (int)Math.Round(comb);
        }
    }
}

Laura & Mie, er I der stadigvæk?

Java (rekursivt som Perl løsningen men med udnyttelse af combinations udregningen som
C# løsningen):

public class Combi2 {
    private static int[] FAC = new int[10];
    static
    {
        FAC[0] = 1;
        for(int i = 1; i < 10; i++) FAC[i] = i * FAC[i -1];
    }
    private static int Comb(int n, int p) {
        return FAC[p]/(FAC[n]*FAC[p-n]);
    }
    private static int calc(int[] count, int[] votes, int target, int[] n, int ix) {
        int res = 0;
        if(ix < votes.length) {
            for(int i = 0; i <= count[ix]; i++) {
                n[ix] = i;
                res += Comb(i, count[ix]) * calc(count, votes, target, n, ix + 1);
            }
        } else {
            int tmp = 0;
            for(int i = 0; i < votes.length; i++) {
              tmp += (n[i] * votes[i]);
            }
            res = (tmp >= target) ? 1 : 0;
        }
        return res;
    }
    private static int calc(int[] count, int[] votes, int target)
    {
        return calc(count, votes, target, new int[votes.length], 0);
    }
    public static void main(String[] args) {
        int[] count = {  4,  2,  1,  1,  5,  3, 5, 5, 1 };
        int[] votes = { 29, 27, 14, 13, 12, 10, 7, 4, 3 };
        System.out.println(calc(count, votes, 255));
    }
}