Je peux d'ores et déjà affirmer qu'il n'existe pas de tels nombres inférieurs à 100.

En effet, prenons deux entiers [latex]n \in [0;4][/latex] et [latex]p \in [0;9][/latex]
Le nombre [latex]20n[/latex] est formé de chiffres pairs.
Le nombre [latex]2p+1[/latex] est formé de chiffres impairs, et varie entre 0 et 19
Et [latex]20n+2p+1[/latex] est un nombre impair.
Chaque nombre impair compris entre 1 et 99 peut s'écrire ainsi.
Donc chaque nombre impair entre 1 et 99 est somme de deux nombres dont l'un n'a que des chiffres pairs et l'autre que des chiffres pairs.

EDIT
Dans les trois cents premiers entiers, seuls 109, 129, 149, 169, et 189 vérifient les conditions. Preuve a suivre, pas encore de généralisation :-(

En additionnant un chiffre pair et un chiffre impair, on obtient au mieux 17, 18 avec une retenue. Si on a besoin de faire 19, c'est cuit.
Autrement dit, si un des chiffres est 9, que le précédent est pair et qu'il y en a encore un autre devant, c'est impossible.
Le plus petit de ces nombres serait donc 109, et on pourrait les caractériser de la manière suivante : les nombres contenant un 9 immédiatement précédé d'un chiffre pair, précédé (pas forcément juste avant) d'un chiffre impair

A premiere vue, je dirais que les nombres de la forme XXX09 ne peuvent pas être écrits comme somme de deux nombres dont l'un a tous ses chiffres pairs et l'autre a tous ses chiffres impairs, si XXX est impair (et pas forcement 3 chiffres).
Par exemple: 109 repond au probleme.

A moins que je ne me sois trompé, je pense avoir entièrement fait le tour de ta question, non ?

Tu as mis le doigt sur le cas limite, dans ma preuve j'ai juste oublié le cas où le chiffre pair est en tête, en ce cas le chiffre impair correspondant est un ... 0 ! Mais comme il est en tête, il est invisible.

Je viens de m'apercevoir que j'ai la même réponse que scarta
@gasole: il faut un chiffre impair devant le pair devant le 9, sinon, ça ne suffit pas.
Il reste à montrer que l'on peut "scinder" tous les autres...

@rivas : le chiffre devant le pair n'a pas besoin d'être pair lui-même, ça ne sera pas possible de toute façon.

Je dis (maintenant) la même chose que scarta pour une condition suffisante d'impossibilité, mon algorithme montre qu'elle est aussi nécessaire.

En résumé, mon algorithme prend 0 pour pair (ou 8 s'il faut une retenue au rang suivant) et le chiffre courant pour impair (éventuellement -1 si pair, la retenue du rang précédent bouchant le trou, et éventuellement plus 2 si besoin de retenue au rang suivant)

En effet, les cas dégénérés comme 22229 ont une solution qui est, par exemple : 22220+9, je dis dégénérée car le 9 est précédé de 0 invisibles... qui sont pairs lol

Si l'on parlait d'un codage sur n chiffres (n fixés) ces zéros seraient visibles et la décomposition serait impossible avec un 9 précédé d'un chiffre pair, c'est mon oubli puisque l'on parle de l'écriture standard des nombres (avec 0 invisibles).


BREF :
On teste d'abord si le nombre est acceptable, s'il l'est on lui applique l'algorithme suivant (en image) pour le décomposer.
---------------------------------------------------------
Est acceptable (décomposable), tout nombre (vu de gauche à droite) dans lequel tout 9 est soit précédé d'un chiffre impair, soit précédé uniquement de chiffres pairs (les autres chiffres ne posent pas de pb) :

Acceptables :
- 42091 (le 9 est précédé uniquement de chiffres pair)
- 42191 (le 9 est précédé d'un impair)
- 42096395 (l'un des 9 est précédé d'un impair, l'autre uniquement de pairs)

Non acceptables:
- 32091 (le 9 n'est pas précédé uniquement de chiffres pair, ni d'un chiffre impair)
- 3221229 (le cas délicat de Rivas, même raison)

Acceptables : reconnus (de droite à gauche) par l'expression régulière :
        i . (1 + p + i' + (9.(1 + i))* . p*   

où p est {0,2...8} et i' est i : {1,3...9} privé de 9; x* : un nombre quelconque de  fois x; et 1 est le mot vide.

---------------------------------------------------------
Algorithme :

On parcourt le nombre de droite à gauche, en jetant un oeil sur le chiffre suivant : les i désignent des chiffres impairs, et les p des chiffres pairs, r est la retenue engendrée, et les "+1" indiquent les retenues précédentes propagées.



Il reste à prouver que si le nombre à décomposer contient un 9 précédé d'une séquence de nombres pairs, elle-même précédée d'au moins un chiffre impair alors le nombre n'est pas décomposable, puisque tous les autres cas sont décomposables par l'algorithme.

Soit N un nombre de la forme (de gauche à droite) :
        ...n(k+1) n(k) n(k-1)...n(1)9...
où les n(i<k+1) sont pairs, n(k+1) est impair, les pointillés étant des séquences quelconques.

Il est impossible d'obtenir n(1) comme somme d'un pair et d'un impair (remarque 1 ci-dessous), même avec une retenue au rang précédent. La seule option est de le décomposer en n(1)+0 (ce 0 quoique pair serait invisible donc ça va). Mais alors, devant ce 0, il ne faut que des 0 (sinon ils seront visibles), et ça va coincer pour n(k+1).

C'est complet maintenant, et plus clair j'espère.

(1) : Ce chiffre pair on ne pourrait l'obtenir comme somme d'un pair et d'un impair qu'avec une retenue au rang précédent, il faudrait donc qu'au rang précédent la somme des chiffres (avec l'aide d'une retenue éventuellement) fassent 19 ce qui n'est pas possible avec un impair et un pair (max = 17, 18 avec retenue).