Preuve de borne inférieure pour l'algorithme d'éléments distinctes déterministes

Question

Il y a une preuve dans ce document (page 8, section 4, lemme 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) Cela reflète une preuve que mon professeur a donné dans ma classe d'algorithmes. Le lemme déclare:

Supposons qu'il existe un algorithme exact déterministe pour compter des éléments distincts qui utilisent des bits de mémoire o (min {| $ sigma $ |, $ n $}) pour traiter un flux de $ n $ d'éléments de $ sigma $.

Ensuite, il existe un algorithme de compression qui mappe les chaînes de $ l $-bits aux chaînes de longueur de longueur o ($ l $).

La conclusion est fausse, donc la prémisse est fausse. La preuve est par contradiction. Ceci est prouvé en construisant un algorithme de compression qui code pour une chaîne de bits $ l $ -legth dans moins de bits $ l $. Une méthode de décodage est ensuite donnée pour reconstruire la chaîne de bits $ L $ -legth.

Ce qui me confond, c'est que le paragraphe ci-dessus est apparemment la contradiction qui prouve que vous ne pouvez pas transmettre une chaîne de bits $ l $ -lenth en utilisant moins de bits $ l $. Et pourtant, cela semble montrer que cela peut être fait.

Je comprends l'argument de comptage qui dit que vous ne pouvez pas cartographier 2 $ ^ L $ Bit-Trings sur une plage de sorties de 2 $ ^ l-1 $. Ce que je dois comprendre pour ma classe, c'est pourquoi la preuve donnée par contradiction est valide. Si quelqu'un peut m'aider avec l'intuition concernant pourquoi la preuve est valide, je l'apprécierais