One thing I would like to add: let them set long passwords [0], different ones for each service and write them down in a dedicated notebook.
As a result, paper is sort of natural for them, and the only way I found to impeach them from writing down their passwords is to make them use passphrases instead of passwords.
They do remember the passphrases they typed in, however the issue is that some websites still refuse passphrases because they are too long :(.