proof of arrow's impossibility for n = 2, m = 3

arrow.cpp

#include <cstdio>

using namespace std;

bool gt[7][4][4];
bool unanimity[37][7];

char* profile_str[7];


void profiles(int inp, int &p1, int &p2) {
    inp--;
    p1 = inp % 6 + 1;
    p2 = inp / 6 + 1;
}

void gen_gt() {
    int cnt = 0;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            for (int k = 1; k <= 3; k++) {
                if (i == j || j == k || i == k) continue;
                cnt++;
                gt[cnt][1][2] = i > j;
                gt[cnt][1][3] = i > k;
                gt[cnt][2][1] = j > i;
                gt[cnt][2][3] = j > k;
                gt[cnt][3][1] = k > i;
                gt[cnt][3][2] = k > j;

                profile_str[cnt] = new char(4);
                profile_str[cnt][i-1] = '1';
                profile_str[cnt][j-1] = '2';
                profile_str[cnt][k-1] = '3';
                profile_str[cnt][3] = 0;
            }
        }
    }
}

void gen_unanimity() {
    for (int inp = 1; inp <= 36; inp++) {
        for (int out = 1; out <= 6; out++) {
            int p1, p2;
            profiles(inp, p1, p2);

            bool ok = true;
            for (int i = 1; i <= 3; i++) {
                for (int j = i+1; j <= 3; j++) {
                    if (gt[p1][i][j] == gt[p2][i][j] && gt[p1][i][j] != gt[out][i][j]) {
                        ok = false;
                    }
                }
            }

            unanimity[inp][out] = ok;
        }
    }
}

int f[37];

bool IIA(int inp, int out) {
    int p1, p2;
    profiles(inp, p1, p2);

    for (int oinp = 1; oinp < inp; oinp++) {
        int op1, op2;
        profiles(oinp, op1, op2);

        for (int i = 1; i <= 3; i++) {
            for (int j = i + 1; j <= 3; j++) {
                if (gt[op1][i][j] == gt[p1][i][j] && gt[op2][i][j] == gt[p2][i][j]) {
                    if (gt[out][i][j] != gt[f[oinp]][i][j]) {
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

int dictator() {
    bool is_p1 = true, is_p2 = true;
    for (int inp = 1; inp <= 36; inp++) {
        int p1, p2;
        profiles(inp, p1, p2);
        
        if (p1 != f[inp]) is_p1 = false;
        if (p2 != f[inp]) is_p2 = false;
    }
    if (is_p1) return 1;
    else if (is_p2) return 2;
    else return 0;
}

void print_f() {
    for (int inp = 1; inp <= 36; inp++) {
        int p1, p2;
        profiles(inp, p1, p2);
        printf("(%s,%s)->%s\t", profile_str[p1], profile_str[p2], profile_str[f[inp]]);
    }
    printf("\n");
}


void dfs(int inp) {
    if (inp == 37) {
        int d = dictator();
        if (d > 0) {
            printf("------------------\n");
            printf("%d is dictator!\n", d);
            print_f();
            printf("------------------\n");
        } else {
            printf("------------------\n");
            printf("A possible solution!");
            print_f();
            printf("------------------\n");
        }
        return;
    }

    for (int out = 1; out <= 6; out++) {
        if (!unanimity[inp][out]) continue;
        if (!IIA(inp, out)) continue;
        f[inp] = out;
        dfs(inp+1);
    }
}


int main() {
    gen_gt();
    gen_unanimity();
    dfs(1);
    return 0;
}