Μέγεθος συνόλου

#1

Έστω

το σύνολο όλων των τετραγώνων του $\mathbb{F}_{2011}$ και έστω $x \in \mathbb{F}_{2011}$ . Να βρεθεί το $|S \cap (S+x)|$ , όπου $S+x = \{s+x:s \in S\}$ .

#2

Επαναφορά.

Το μέγεθος του $|S \cap (S+x)|$ μπορεί να εξαρτάται από το

.

#3

Επαναφορά.

Μέχρι Κυριακή 15 Ιανουαρίου. Μετά θα δώσω την λύση μου.

Ilias_Zad · #4

Δημήτρη:

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#5

Ναι σωστό είναι.

Ilias_Zad · #6

Οκ για να το δούμε.
Έστω $p\equiv -1 (mod4)$ . Για x=0

τα τετράγωνα είναι $\frac{p+1}{2}$ , (είχα ξεχάσει το μηδέν παραπάνω).

Αλλιώς ουσιαστικά ζητάμε το πλήθος των λύσεων της a^2-b^2=x

ως προς

.

Aφού τα τετράγωνα αποτελούν υποομάδα της κυκλικής $F_{p}*$ δείκτου

παίρνουμε άμεσα ότι το πλήθος της τομής για

τετράγωνο είναι το ίδιο για κάθε

τέτοιο , έστω ίσο με

, και για

μη τετράγωνο πάλι ίσο πάντα με ένα

.

Τότε όμως λόγω του ότι

όχι τετραγωνικό υπόλοιπο στο Z_p

, καθώς και λόγω της ισοδυναμίας $a^2-b^2=1 \rightarrow b^2-a^2=-1$ έχουμε ότι t=m

.

Οπότε έχουμε ότι για $x \not =0$ η εξίσωση μας έχει ακριβώς το ίδιο πλήθος λύσεων. Τα (a^2,b^2)

όμως με $a^2 \not = b^2$ είναι $\frac{p^2-1}{4}$ και λόγω της ομοιόμορφης κατανομής για x=1,.,p-1

οι λύσεις για σταθερό

είναι $\frac{p^2-1}{4(p-1)}=\frac{p+1}{4}$ .

#7

Βάζω την κάπως διαφορετική λύση μου:

Συνεχίζοντας από την εξίσωση x = a^2 - b^2

, αν θέσω

, όπου $k \neq 0$ τότε έχουμε a+b = x/k

(τα

είναι στοιχεία του σώματος $\mathbb{F}_p$ ) και άρα a = (k + x/k)/2

. Επομένως παίρνουμε ότι κάθε στοιχείο του

είναι της μορφής a_k = ((k + x/k)/2)^2

. Το αντίστροφο είναι επίσης εύκολο να ελεγχθεί. Αν τώρα $a_k = a_{\ell}$ μετά από λίγες πράξεις βρίσκουμε ότι $\ell \in \{k,-k,x/k,-x/k\} = A_k$ . Επειδή η σχέση $k \sim \ell \Leftrightarrow a_k = a_{\ell}$ είναι προφανώς σχέση ισοδυναμίας τα σύνολα A_k

διαμερίζουν το $\mathbb{F}_p^{\ast}$ . Όλα αυτά τα σύνολα έχουν μέγεθος 4 εκτός εάν x = k^2

ή

. Επειδή $p \equiv -1 \bmod 4$ ακριβώς μία από τις δύο σχέσεις μπορεί να ισχύει και επιπλέον αυτή η σχέση έχει ακριβώς δύο λύσεις, τις

και

για κάποιο $a \in \mathbb{F}_p$ . Επειδή $A_a = A_{-a}$ ακριβώς ένα από τα σύνολα έχει μέγεθος 2 και άρα έχουμε ακριβώς 1 + (p-1-2)/4 = (p+1)/4

τέτοια σύνολα.

----------------
Ενδιαφέρον παρουσιάζει και η περίπτωση $p \equiv 1 \bmod 4$ . Εδώ, αν το

είναι τετραγωνικό υπόλοιπο $\bmod p$ και οι δύο εξισώσεις x = k^2,x=-k^2

θα έχουν λύση και θα βρούμε ακριβώς δύο σύνολα μεγέθους 2 οπότε θα έχουμε (2 + (p-1-4)/4 = (p+3)/4

τέτοια σύνολα. Στην περίπτωση που το

δεν είναι τετραγωνικό υπόλοιπο $\bmod p$ καμία από τις εξισώσεις δεν έχει λύση και άρα υπάρχουν (p-1)/4

τέτοια σύνολα.

-----------------
Δυστυχώς δεν θυμάμαι από που πήρα την άσκηση. Ίσως από κάποιο Putnam.

Μέγεθος συνόλου

Μέγεθος συνόλου

Re: Μέγεθος συνόλου

Re: Μέγεθος συνόλου

Re: Μέγεθος συνόλου

Re: Μέγεθος συνόλου

Re: Μέγεθος συνόλου

Re: Μέγεθος συνόλου

Μέλη σε σύνδεση