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'art. 146 CP (défaut d'astuce) et la violation de l'art. 41 CP, 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.