Faits: A. Le 22 septembre 2008, à la demande de son compagnon, A._, B._ s'est fait remettre à Madrid 2'606 grammes de cocaïne contenus dans deux porte-documents. Le 23 septembre, elle a emprunté un bus à destination de Zurich pour y livrer la cocaïne. Au passage de la frontière franco-suisse à Genève, elle a été interpellée en possession de la drogue. La police a alors mis sur pied une opération pour faire venir à Genève les récipiendaires de la drogue, avec la collaboration de B._ et le concours de A._, qui avait été informé de la situation de son amie. Sous le contrôle de la police, B._ a eu plusieurs contacts téléphoniques avec A._ et d'autres personnes qui étaient avec lui en Espagne. Elle a reçu pour instruction de se rendre dans un hôtel et d'y attendre un homme qui devait venir en début de soirée. Il lui a été indiqué qu'elle devait l'aborder et recourir à un code verbal qui consistait à l'interpeller en allemand pour lui demander s'il parlait cette langue et où se trouvait la gare. X._ qui se trouvait à Zurich, a reçu un coup de téléphone d'un dénommé "C._" qui lui a demandé de se rendre à Genève pour y rencontrer une femme. Il est parti en compagnie d'un ami et s'est rendu alors au contact de B._ qui l'a abordé selon la procédure codée préétablie avec A._ et dont il avait connaissance. Il a indiqué alors d'un geste à B._ qu'il était la bonne personne. X._ a alors été immédiatement interpellé par la police. Il a nié toute implication dans le trafic de stupéfiants. Le 13 mai 2009, B._, en détention depuis le 23 septembre 2008, a reçu une lettre de A._ clamant l'innocence de l'intimé. B. Par jugement du 3 juin 2009, la Cour correctionnelle sans jury du canton de Genève a condamné X._, pour infraction grave à la loi fédérale sur les stupéfiants, à une peine privative de liberté de 3 ans et 6 mois, sous déduction de la détention préventive subie. Par arrêt du 16 octobre 2009, la Cour de cassation du canton de Genève a annulé le jugement de la Cour correctionnelle et a prononcé l'acquittement de X._. C. Contre ce dernier arrêt, le Procureur général du canton de Genève dépose un recours en matière pénale devant le Tribunal fédéral. Invoquant l'arbitraire, il conclut au renvoi de la cause à la Cour de cassation pour nouvelle décision et, subsidiairement, à la confirmation de l'arrêt rendu par la Cour correctionnelle. Invité à se déterminer, l'intimé conclut à l'irrecevabilité du recours pour cause de tardiveté, respectivement à son rejet. Il requiert l'assistance judiciaire ainsi que la désignation de son conseil comme avocat d'office. La Cour de cassation a renoncé à déposer des observations. 