Faits:
A. Par jugement du 31 janvier 2011, le Tribunal de police de l'arrondissement de Lausanne a condamné Y._ pour vol, tentative d'escroquerie et infraction à la loi fédérale sur les stupéfiants à une peine privative de liberté de cinq mois, peine partiellement complémentaire à celle prononcée le 12 mai 2010 par le procureur de Winterthur. Il a également reconnu coupable X._ de tentative d'escroquerie et lui a infligé une peine pécuniaire de 60 jours-amende, le montant du jour-amende étant fixé à 50 fr., avec sursis pendant deux ans. Sur le plan civil, il a donné acte de ses réserves civiles à la compagnie d'assurances Z._ SA.
B. Par jugement du 31 mai 2011, la Cour d'appel pénale du Tribunal cantonal vaudois a rejeté l'appel formé par Y._ et X._ et confirmé le jugement de première instance.
En bref, la condamnation pour tentative d'escroquerie repose sur les faits suivants :
B.a En mars 2008, X._ a acheté pour le montant de 26'000 fr. une voiture BMW X 5 dont le kilométrage était de 132'000 km. Elle a reçu deux clés d'origine.
Le 7 avril 2008, elle a souscrit une police d'assurance pour véhicule à moteur, incluant notamment les risques responsabilité civile et casco partielle (vol) auprès de la compagnie d'assurances Z._ SA.
B.b Le 7 octobre 2009, son ami, Y._, s'est rendu à Paris au volant du véhicule en question. Le 9 octobre, il a déposé une plainte pénale auprès d'un agent de police judiciaire à Paris, indiquant s'être fait voler la voiture dans la nuit du 7 au 8 octobre 2009, alors qu'il l'avait garée dans la rue.
Le 16 octobre 2009, X._ a rempli et signé une déclaration de sinistre « vol de véhicule » auprès de la compagnie d'assurances Z._. Elle a indiqué que le vol s'était produit à Paris et que la BMW X 5 affichait alors 140'000 km au compteur. Elle a remis à la compagnie d'assurances une des clés d'origine, expliquant que son ami, Y._, avait perdu la seconde lors d'un déménagement à la fin de l'année 2008 ou au début de l'année 2009.
B.c D'après le dernier enregistrement relevé sur la clé originale (remise par X._ lors de la déclaration de sinistre), le kilométrage de la BMW était de 145'349 km, ce qui correspond à peu près au kilométrage indiqué par X._ dans sa déclaration de sinistre. La compagnie d'assurances Z._ s'est en outre fait remettre par le garage BMW B._ SA les factures d'entretien, dont la dernière, datée du 8 juillet 2009 (à savoir trois mois avant le sinistre), mentionnait que la voiture affichait alors 155'092 km au compteur. Selon la compagnie d'assurances, la différence de kilométrage relevée entre le 16 octobre 2009 au moment de la remise de la clé lors de l'annonce du sinistre et le 8 juillet 2009 ne s'expliquait que si la seconde clé avait continué à être utilisée. Émettant de sérieux doutes sur la réalité du sinistre, la compagnie d'assurances a dénoncé le cas le 17 novembre 2009 et s'est constituée partie civile.
B.d La cour cantonale a considéré qu'il était difficile de savoir si la voiture - qui n'a pas été retrouvée à ce jour - avait été réellement volée ou non. Elle a en revanche acquis l'intime conviction que X._ et Y._ avaient à tout le moins l'intention de profiter de la situation pour demander une indemnisation ne correspondant pas à la valeur du véhicule, en indiquant faussement un kilométrage plus faible. X._ et Y._ ont ainsi été condamnés pour tentative d'escroquerie pour avoir trompé l'assurance sur le kilométrage de la voiture et, partant, sur sa valeur. En effet, les valeurs d'achat et de vente du véhicule en cause sont, selon Argus, de 12'400 fr. à l'achat et de 16'000 fr. à la vente, pour 140'000 km, et, pour 160'000 km, de 11'200 fr. à l'achat et de 14'800 fr. à la vente.
C. Contre ce dernier jugement, X._ et Y._ déposent un recours en matière pénale devant le Tribunal fédéral. Invoquant l'arbitraire dans l'établissement des faits, la mauvaise application de l'<ref-law> (défaut d'astuce) et la violation de l'<ref-law>, ils concluent, en substance, à leur libération du chef d'accusation de tentative d'escroquerie. En outre, ils sollicitent l'assistance judiciaire.
Invité à se déterminer, le Ministère public central conclut au rejet du recours, se référant aux considérants de l'arrêt attaqué. La compagnie d'assurances Z._ et la cour cantonale renoncent à se déterminer.

Considérant en droit:
1. Invoquant le principe in dubio pro reo, l'art. 6 § 2 CEDH et l'art. 32 al. 1 Cst., les recourants soutiennent que la cour cantonale a retenu, de manière arbitraire, que la voiture n'avait pas été volée.
1.1 Dans la mesure où, comme en l'espèce, le principe in dubio pro reo est invoqué en relation avec l'appréciation des preuves, il n'a pas de portée plus large que l'interdiction de l'arbitraire, prohibant une appréciation reposant sur des preuves inadéquates ou sans pertinence (<ref-ruling> consid. 2a p. 41). On peut renvoyer, sur la notion d'arbitraire, aux principes maintes fois exposés par le Tribunal fédéral (voir par ex: <ref-ruling> consid. 2.4 p. 5; <ref-ruling> consid. 4.2 p. 560 ; <ref-ruling> consid. 1.3 p. 4/5; <ref-ruling> consid. 5.4 p. 148; <ref-ruling> consid. 3.1 p. 153 et les arrêts cités). En bref, pour qu'il y ait arbitraire, il ne suffit pas que la décision attaquée apparaisse discutable ou même critiquable; il faut qu'elle soit manifestement insoutenable et cela non seulement dans sa motivation, mais aussi dans son résultat.
1.2 En l'espèce, la cour cantonale a condamné les recourants pour avoir trompé la compagnie d'assurances sur le kilométrage du véhicule et, partant, sur sa valeur, et non pour avoir faussement annoncé le vol du véhicule. Elle a en effet admis qu'il y avait doute sur l'existence du vol. C'est donc à tort que les recourants lui reprochent d'avoir retenu arbitrairement que la voiture n'avait pas été volée. Non pertinent, leur grief doit être rejeté.
2. Les recourants contestent s'être rendu coupables de tentative d'escroquerie, en faisant valoir l'absence d'astuce.
2.1 Aux termes de l'<ref-law>, se rend coupable d'escroquerie celui qui, dans le dessein de se procurer ou de procurer à un tiers un enrichissement illégitime, a astucieusement induit en erreur une personne par des affirmations fallacieuses ou par la dissimulation de faits vrais, ou l'a astucieusement confortée dans son erreur et a de la sorte déterminé la victime à des actes préjudiciables à ses intérêts pécuniaires ou à ceux d'un tiers.
2.1.1 L'escroquerie consiste à tromper la dupe. Pour qu'il y ait escroquerie, une simple tromperie ne suffit cependant pas ; il faut qu'elle soit astucieuse. Selon la jurisprudence, la tromperie est astucieuse lorsque l'auteur recourt à un édifice de mensonges, à des manoeuvres frauduleuses ou à une mise en scène, mais aussi lorsqu'il donne simplement de fausses informations, si leur vérification n'est pas possible, ne l'est que difficilement ou ne peut raisonnablement être exigée, de même que si l'auteur dissuade la dupe de vérifier ou prévoit, en fonction des circonstances, qu'elle renoncera à le faire en raison d'un rapport de confiance particulier (<ref-ruling> consid. 4.4.3 p. 264 ; <ref-ruling> consid. 3a p. 20). L'astuce n'est toutefois pas réalisée si la dupe pouvait se protéger avec un minimum d'attention ou éviter l'erreur avec le minimum de prudence que l'on pouvait attendre d'elle. Il n'est cependant pas nécessaire qu'elle ait fait preuve de la plus grande diligence ou qu'elle ait recouru à toutes les mesures possibles pour éviter d'être trompée. L'astuce n'est exclue que si elle n'a pas procédé aux vérifications élémentaires que l'on pouvait attendre d'elle au vu des circonstances. Une coresponsabilité de la dupe n'exclut toutefois l'astuce que dans des cas exceptionnels (<ref-ruling> consid. 5.2 p. 81).
2.1.2 Il y a tentative d'escroquerie si l'auteur, agissant intentionnellement et dans un dessein d'enrichissement, a commencé l'exécution de cette infraction sans poursuivre son exécution jusqu'à son terme ou que le résultat dommageable ne se produit pas (cf. <ref-law>). Toute tromperie qui ne réussit pas n'est pas nécessairement dénuée de caractère astucieux. Abstraction faite de l'échec de la tromperie, il importe d'examiner si la tromperie prévue paraissait ou non facilement décelable compte tenu des possibilités de protection dont disposait la victime et dont l'auteur avait connaissance. Autrement dit, c'est dans le cadre d'un examen hypothétique qu'il faut déterminer si le plan élaboré par l'auteur était objectivement astucieux ou non. S'il l'était et que la tromperie échoue parce que la victime était plus attentive ou plus avisée que l'auteur ne se l'était figuré ou en raison du hasard ou d'une autre circonstance non prévisible, il y a alors lieu de retenir une tentative de tromperie astucieuse (ATF <ref-ruling> consid. 3b p. 21 et références citées).
2.2 La cour cantonale a constaté que les recourants avaient mis en scène un « édifice de mensonges », que seuls des contrôles plus poussés effectués par l'assurance auprès du garage BMW avaient permis de mettre à jour. Elle n'a toutefois pas expliqué en quoi consistait cet édifice de mensonge difficile à déceler. Selon les faits constatés, les recourants se sont bornés à indiquer un faux kilométrage dans la déclaration de sinistre et à prétendre avoir perdu la seconde clé. Il s'agit-là de simples mensonges, qui ne peuvent être qualifiés d'astucieux que si leur vérification n'est pas possible ou ne l'est que difficilement ou ne peut être raisonnablement exigée (cf. consid. 2.1.1 ci-dessus). Or, en l'espèce, il a suffi à la compagnie d'assurances de s'adresser à l'Agence BMW, auprès de laquelle les recourants étaient clients, et de lui demander les anciennes factures pour connaître le kilométrage du véhicule volé. De telles vérifications sont faciles et usuelles. Elles ne peuvent être qualifiées - comme le fait la cour cantonale - de contrôles « poussés ». En effet, les compagnies d'assurances sont conscientes des risques de fraudes ou d'allégations mensongères de leurs assurés et font preuve de vigilance. C'est ainsi qu'elles ont l'habitude de contrôler le kilométrage d'un véhicule en cas de sinistre et plus particulièrement en cas de vol, puisque le kilométrage est un des éléments pour établir la valeur du véhicule et, ainsi, chiffrer le montant de l'indemnisation. Dans ces circonstances, le mensonge des recourants, consistant à indiquer un faux kilométrage, était aisément décelable par la compagnie d'assurances et ne peut être qualifié d'astucieux. La cour cantonale a donc violé le droit fédéral en condamnant les recourants pour tentative d'escroquerie. Le recours doit être admis sur ce point.
3. Le recourant, qui a été condamné à une peine privative de liberté de cinq mois ferme, dénonce la violation de l'<ref-law>. Il convient d'entrer en matière sur ce grief, dans la mesure où une nouvelle peine doit être infligée au recourant pour les vols et l'infraction à la LStup.
3.1 Selon l'<ref-law>, le juge peut prononcer une peine privative de liberté ferme de moins de six mois uniquement si les conditions du sursis à l'exécution de la peine (<ref-law>) ne sont pas réunies et s'il y a lieu d'admettre que ni une peine pécuniaire ni un travail d'intérêt général ne peuvent être exécutés.
L'<ref-law> prévoit deux conditions cumulatives :
3.1.1 Il faut d'abord que les conditions du sursis à l'exécution de la peine ne soient pas réunies. Il en va ainsi, conformément à l'<ref-law>, lorsqu'une peine ferme paraît nécessaire pour détourner l'auteur d'autres crimes ou délits. Lorsque l'auteur a fait l'objet de condamnations durant les cinq ans qui précèdent l'infraction, il faut en outre qu'il n'existe aucune circonstance particulièrement favorable au sursis (<ref-law>).
3.1.2 La seconde condition reflète la subsidiarité de la peine privative de liberté. Le juge ne peut prononcer une peine privative de liberté de moins de six mois que s'il y a lieu d'admettre que ni une peine pécuniaire ni un travail d'intérêt général ne peuvent être exécutés (<ref-law>).
Pour pouvoir émettre un pronostic, le juge doit fixer dans les grandes lignes la peine pécuniaire susceptible d'être prononcée. Le nombre de jours-amende et leur montant unitaire doivent être déterminés selon les critères prévus par l'<ref-law>. C'est seulement sur la base de la peine pécuniaire ainsi déterminée que le juge pourra poser son pronostic (<ref-ruling> consid. 8.2 p. 78 s. ; arrêt 6B_541/2007 du 13 mai 2008, consid. 7.1). Dans son appréciation, le juge doit se pencher par avance sur les questions d'exécution et tenir compte des possibilités offertes par les art. 35 et 36 CP. Il doit aussi prendre en considération la situation du condamné sur le plan de la police des étrangers (<ref-ruling> consid. 8.3 p. 79 ; arrêt 6B_541/2007 du 13 mai 2008, consid. 7.2).
Le juge doit apprécier si l'intéressé est disposé à effectuer un travail d'intérêt général, mais aussi s'il y est apte et en est capable. L'impossibilité doit être liée à la personne du condamné, et non pas à des facteurs extérieurs tels que l'absence de place de travail d'intérêt général. Par exemple, le condamné peut être incapable d'accomplir un travail d'intérêt général compte tenu notamment de son emploi du temps, ou lorsqu'il le refuse (DUPUIS ET AL., CP, Code pénal, 2012, n. 4 ad art. 41). En outre, le prononcé d'un travail d'intérêt général n'est justifié qu'autant que l'on puisse au moins prévoir que l'intéressé pourra, le cas échéant, après l'exécution, poursuivre son évolution en Suisse (arrêt 6B_541/2007 du 13 mai 2008, consid. 4.2.4).
3.1.3 Le juge doit motiver le choix de la courte peine privative de liberté ferme de manière circonstanciée (<ref-law>). Il ne lui suffit pas d'expliquer pourquoi une peine privative de liberté ferme semble adéquate, mais il devra également mentionner clairement en quoi les conditions du sursis ne sont pas réunies, en quoi il y a lieu d'admettre que la peine pécuniaire ne paraît pas exécutable et en quoi un travail d'intérêt général ne semble pas non plus exécutable (<ref-ruling> consid. 8.4 p. 80).
3.2 En l'espèce, le juge de première instance a expliqué que les conditions du sursis n'étaient pas réalisées. Il a ajouté que le recourant devait donc être condamné à une peine privative de liberté ferme de cinq mois, en application de l'<ref-law>, « dont les conditions sont remplies dès lors que ni les condamnations antérieures à des peines d'emprisonnement, avec ou sans sursis, ni celle à du travail d'intérêt général, ni celle à une peine pécuniaire ne paraissent l'avoir dissuadé de poursuivre son activité délictueuse » (jugement de première instance p. 20). De la sorte, il ne s'est prononcé que sur la première condition de l'<ref-law> (conditions du sursis), mais ne dit mot sur la seconde condition (inexécution de la peine pécuniaire et du travail d'intérêt général). Pour sa part, la cour cantonale confirme la peine privative de liberté de cinq mois, qu'elle considère comme adéquate, sans examiner les conditions de l'<ref-law>. Les exigences de motivation posées à l'<ref-law> ne sont dès lors pas remplies. Il appartiendra à la cour cantonale de développer son raisonnement si elle devait prononcer une peine privative ferme de moins de six mois.
4. Au vu de ce qui précède, le recours doit être admis, l'arrêt attaqué est annulé et la cause renvoyée à la cour cantonale pour nouveau jugement. Il appartiendra à cette dernière d'acquitter X._ et d'infliger une nouvelle peine à Y._, en tenant compte de sa libération de la tentative d'escroquerie et des remarques figurant au considérant précédent.
Les recourants ont requis l'assistance judiciaire. Leur requête est sans objet dans la mesure où ils obtiennent gain de cause et peuvent, à ce titre, obtenir des dépens à la charge du canton de Vaud (art. 64 al. 2 et 68 al. 1 LTF).
Il n'y a pas lieu d'imposer des frais à l'intimée, qui a renoncé à se déterminer.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à la cour cantonale pour nouveau jugement dans le sens des considérants.
2. Il n'est pas perçu de frais.
3. Le canton de Vaud versera au conseil des recourants une indemnité de 3'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Cour d'appel pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 16 mars 2012
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Kistler Vianin