Προβλήματα Μαθηματικών

Ιουνίου 7, 2010

Πώς να βρείτε αν μια ομάδα δεν είναι αβελιανή (αντιμεταθετική)

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 9:55 πμ

Μια ομάδα G με N στοιχεία σας δίνεται μέσω του πίνακα πολλαπλασιασμού της M. Αν τα στοιχεία της ομάδας είναι τα g_1, g_2, \ldots, g_N τότε το (i,j) στοιχείο του N\times N πίνακα M είναι το k αν και μόνο αν g_i g_j = g_k.

Αν για κάποια i,j έχουμε M_{i,j} \neq M_{j,i} τότε προκύπτει φυσικά ότι η ομάδα δεν είναι αντιμεταθετική.

Αν σας δώσουν μια ομάδα με τεράστιο N και αν για κάθε φορά που ζητάτε να μάθετε το στοιχείο M_{i,j} πληρώνετε ένα ευρώ βρείτε ένα τρόπο να ελέγχετε αν η ομάδα είναι αντιμεταθετική χωρίς να κάνετε πολλούς ελέγχους.

Είναι αποδεκτό να κάνετε λάθος, το να συμπεράνετε δηλ. ότι η ομάδα είναι αβελιανή ενώ δεν είναι, αλλά αυτό πρέπει να συμβαίνει με πολύ μικρή πιθανότητα, ας πούμε 10^{-6}.

Η μέθοδός σας μπορεί να χρησιμοποιεί τυχαίους αριθμούς.

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: