Faits:
A.
C._ bénéfice d'un premier délai-cadre d'indemnisation de l'assurance-chômage depuis le 1 er août 2012.
Par décision du 25 septembre 2012, confirmée sur opposition le 10 octobre 2012, l'Office cantonal de l'emploi (ci-après: OCE) a sanctionné l'assuré pour recherches d'emploi «nulles» durant le mois d'août 2012 et prononcé une suspension du droit à l'indemnité de cinq jours. Cette décision était motivée par le fait que l'intéressé n'avait pas remis en temps voulu la preuve de ses recherches d'emploi.
B.
C._ a recouru contre cette décision devant la Cour de justice de la République et canton de Genève, Chambre des assurances sociales.
Après avoir entendu les parties le 21 novembre 2012, la juridiction cantonale a partiellement admis le recours en ce sens qu'elle a réduit la suspension du droit à l'indemnité de chômage à trois jours (jugement du 5 décembre 2012).
C.
L'OCE interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation.
L'intimé conclut au rejet du recours. Il demande en outre au tribunal la suppression de toute sanction. Quant au Secrétariat d'Etat à l'économie (SECO), il a renoncé à se déterminer.

Considérant en droit:
1.
La LTF ne connaît pas l'institution du recours joint, de sorte que la partie qui entend contester une décision doit le faire elle-même dans le délai de recours de l'<ref-law>. A défaut, elle ne peut, dans sa détermination sur le recours formé par l'autre partie, que proposer de rejeter celui-ci; elle n'est pas admise à reprendre les conclusions formulées devant l'autorité précédente (cf. <ref-ruling> consid. 2.1 p. 110; arrêt 2C_77/2012 du 31 août 2012 consid. 1.3). Il s'ensuit dans le cas particulier que les conclusions de l'intimé sont irrecevables dans la mesure où elles tendent à autre chose qu'au rejet du recours.
2.
Le jugement entrepris expose les dispositions légales relatives à la suspension du droit aux indemnités de chômage (art. 30 al. 1 let. d LACI) et à l'obligation des assurés d'apporter la preuve de leurs efforts en vue de retrouver un emploi (<ref-law>). On peut y renvoyer sur ces points.
On rappellera qu'aux termes de l'<ref-law>, dans sa teneur en vigueur dès le 1 er avril 2011 (RO 2011 1179), l'assuré doit remettre la preuve de ses recherches d'emploi pour chaque période de contrôle au plus tard le cinq du mois suivant ou le premier jour ouvrable qui suit cette date. A l'expiration de ce délai, et en l'absence d'excuse valable, les recherches d'emploi ne sont plus prises en considération.
3.
Dans un arrêt récent publié aux <ref-ruling>, le Tribunal fédéral a admis la conformité à la loi du nouvel article 26 al. 2 OACI (qui ne prévoit plus l'octroi d'un délai de grâce comme dans son ancienne version). Il a jugé que la loi n'impose pas de délai supplémentaire et que, sauf excuse valable, une suspension du droit à l'indemnité peut être prononcée si les preuves ne sont pas fournies dans le délai de l'<ref-law>; peu importe qu'elles soient produites ultérieurement, par exemple dans une procédure d'opposition.
4.
La juridiction cantonale a considéré que l'intimé n'avait pas été en mesure de prouver qu'il avait bien déposé sa feuille de recherches d'emploi pour le mois d'août 2012 dans le délai prescrit par l'<ref-law>. Par conséquent, l'administration était fondée à prononcer une sanction. S'écartant du barème du SECO (cinq jours de suspension en pareil cas), les premiers juges en ont réduit la durée à trois jours.
Le recourant se plaint d'une violation des <ref-law> et 26 al 2 OACI ainsi que de l'<ref-law>.
5.
5.1. La durée de la suspension du droit à l'indemnité de chômage est fixée compte tenu non seulement de la faute, mais également du principe de proportionnalité ( THOMAS NUSSBAUMER,, Arbeitslosenversicherung, in Soziale Sichereit, SBVR, Vol. XIV, 2 ème éd., n. 855 p. 2435). En tant qu'autorité de surveillance, le SECO a adopté un barème (indicatif) à l'intention des organes d'exécution. Un tel barème constitue un instrument précieux pour ces organes d'exécution lors de la fixation de la sanction et contribue à une application plus égalitaire dans les différents cantons. Cela ne dispense cependant pas les autorités décisionnelles d'apprécier le comportement de l'assuré compte tenu de toutes les circonstances - tant objectives que subjectives - du cas concret, notamment des circonstances personnelles, en particulier celles qui ont trait au comportement de l'intéressé au regard de ses devoirs généraux d'assuré qui fait valoir son droit à des prestations (cf. p. ex. DTA 2006 no 20 p. 229 consid. 2 [C 285/05]; arrêt 8C_33/2012 du 26 juin 2012 consid. 3.2).
5.2. La quotité de la suspension du droit à l'indemnité de chômage dans un cas concret constitue une question relevant du pouvoir d'appréciation, qui est soumise à l'examen du juge de dernière instance uniquement si la juridiction cantonale a exercé son pouvoir d'appréciation de manière contraire au droit, soit si elle a commis un excès positif («Ermessensüberschreitung») ou négatif («Ermessensunterschreitung») de son pouvoir d'appréciation ou a abusé («Ermessensmissbrauch») de celui-ci (arrêt 8C_33/2012 du 26 juin 2012 consid. 2.2; arrêt 8C_31/2007 du 25 septembre 2007 consid. 3.1, non publié in <ref-ruling> mais dans SVR 2008 ALV n° 12 p. 35). Il y a abus du pouvoir d'appréciation lorsque l'autorité, tout en restant dans les limites du pouvoir d'appréciation qui est le sien, se fonde sur des considérations qui manquent de pertinence et sont étrangères au but visé par les dispositions légales applicables, ou viole des principes généraux du droit tels que l'interdiction de l'arbitraire et de l'inégalité de traitement, le principe de la bonne foi et le principe de la proportionnalité (<ref-ruling> consid. 2 p. 152 et les références).
5.3. En l'espèce, la juridiction cantonale a motivé la réduction de la quotité du droit à l'indemnité par le fait qu'il s'agissait d'une première inscription au chômage et d'une première période contrôlée. En outre, l'assuré avait fait des recherches d'emploi importantes et de qualité. Ces motifs ne constituaient cependant pas des critères d'évaluation pertinents de la gravité de la faute pour fixer la durée de la suspension du droit à l'indemnité (pour un cas comparable cf. arrêt 8C_601/2012 ). Le présent cas se distingue de l'arrêt 8C_64/2012 du 26 juin 2012, dans lequel le Tribunal fédéral a confirmé une réduction de la suspension au minimum prévu par l'<ref-law>, au motif que l'intéressé avait remis la preuve de ses recherches d'emploi avec un jour de retard seulement et pour la première fois (cf. aussi arrêt 8C_33/2012 du 26 juin 2012). Or, dans le cas particulier, on doit admettre, sur la base des constatations du jugement attaqué, que l'intimé n'a pas remis spontanément les pièces requises. Il l'a fait seulement après avoir pris connaissance de la décision de suspension et de surcroît bien au-delà du délai dont il disposait à cet effet. Dans ces conditions on doit admettre qu'il y a abus du pouvoir d'appréciation de la part de la juridiction cantonale.
Le recours est ainsi bien fondé.
6.
L'intimé, qui succombe, supportera les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est admis. La décision de la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, du 5 décembre 2012 est annulée et la décision sur opposition de l'Office cantonal de l'emploi du 10 octobre 2012 confirmée.
2.
Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de l'intimé.
3.
Le présent arrêt est communiqué aux parties, à la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, et au Secrétariat d'Etat à l'économie (SECO).
Lucerne, le 29 août 2013
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Présidente: Leuzinger
La Greffière: Berset