پاسخ برای ۷ رقم برابر با ۹ و برای ۱۳ رقم برابر با ۵۸۵ و برای 6n+1 رقم برابر است با:

$$ \frac{2^{6n}-1}{7} $$

ابتدا سعی می‌کنیم مساله را برای ۷ رقم به طور خاص حل کنیم. برای اینکه عدد بر ۵ بخش‌پذیر باشد، رقم یکان باید ۵ باشد. پس عدد را می‌توان به صورت abcdef5 نوشت. برای اینکه کل عدد بر ۷ بخش پذیر باشد، باید باقیمانده‌ی abcdef0 بر ۷ برابر ۲ باشد.

که باقیمانده‌ی این عدد بر ۷ را می‌توان به صورت زیر نوشت:

$$ \begin{aligned} abcdef0 \overset{7}{\equiv} &f \cdot 10 + e \cdot 10^2 + d \cdot 10^3 + \\ &c \cdot 10^4 + b \cdot 10^5 + a \cdot 10^6 \end{aligned} $$

با کمی دقت متوجه می‌شویم که اینکه رقمی را ۷ بگذاریم معادل این است که آن رقم را صفر بگذاریم و در باقیمانده تاثیری ندارد. پس حالت‌هایی که قرار است بشماریم معادل این است که زیرمجموعه‌ای از ارقام a، b، c، d، e، f را برابر ۵ قرار دهیم بطوری که حاصل باقیمانده‌ی بالا برابر با ۲ باشد.

همچنین باقیمانده‌ی $(5 \times 10^i)$ بر ۷ به ازای ۱ تا ۷ به ترتیب برابر است با ۱، ۳، ۲، ۶، ۴، ۵.

بنابراین مساله معادل این است که زیرمجموعه‌هایی از ۱،۲،۳،۴،۵،۶ را بشماریم که باقیمانده‌ی مجموع اعدادشان بر ۷ برابر با ۲ باشد.

یک راه ساده این است سعی کنیم دستی زیرمجموعه‌های به هر طول را که باقیمانده‌ی ۲ می‌دهند را دربیاوریم:

• طول ۱: {2}
• طول ۲: {3,6}، {4,5}
• طول ۳: {1,2,6}، {1,3,5}، {2,3,4}
• طول ۴: {1,4,5,6}، {2,3,5,6}
• طول ۵: {1,2,3,4,6}

پس پاسخ برابر با ۹ است.

اگر باقیمانده‌ی $(5 \times 10^i)$ بر ۷ را به ازای ۸ تا ۱۳ ادامه دهیم (یا به ازای هر i برابر $7n+1$ تا $7n+6$) ، باز بدست می‌آوریم ۱، ۳، ۲، ۶، ۴، ۵.

یعنی برای شمردن پاسخ برای ۱۳، باید باقیمانده‌ی ۲ را با استفاده از داشتن انتخاب دو تا از هر کدام از ۱ تا ۶ بدست بیاوریم.

می‌توان اثبات کرد که (قضیه ۲ در انتها) اگر همه‌ی زیرمجموعه‌های $\{1_1,2_1,3_1,4_1,5_1,6_1, ..., 1_n,2_n,3_n,4_n,5_n,6_n\}$ که در آن هر کدام از ۱ تا ۶، n بار تکرار شده باشد را در نظر بگیریم، تعداد آن‌هایی که باقیمانده‌شان بر ۷ برابر با ۱ یا ۲ یا ... یا ۶ است مساوی است، و تعداد آن‌هایی که باقیمانده‌شان صفر است یکی بیشتر است.

(چگونه به این رسیدم؟ با راه‌حل ترکیبیاتی مساله را برای ۱۳ حل کردم و شباهت پاسخ آن با حالت ۷ را دیدم و حدس زدم برای حالت کلی نیز درست باشد. سپس اثبات کردم. احتمالا با کمی تلاش راه‌حل ترکیبیاتی حالت ۱۳ رقم را بتوانید پیدا کنید، ولی اگر مایل به دیدن راه‌حل ترکیبیاتی ما نیز هستید، کامنت بگذارید.)

پس جواب برای n به طور کلی برابر است با:

$$ \frac{2^{6n}-1}{7} $$

که به دست می‌آید برای ۱۳ رقم پاسخ برابر است با ۵۸۵.

توضیح. در اینجا $1_1$ و $1_2$ مجزا هستند (به خاطر اینکه هرکدام نماینده‌ی یک رقم مجزا در عدد 6n+1 رقمی هستند) و ۴ حالت انتخاب برای این دو داریم، ولی هر دو نقش ۱ در حساب کردن باقیمانده‌ی مجموع دارند.

اثبات ادعای بالا:‌

قضیه. در بین زیرمجموعه‌هایی از مجموعه‌ای که در آن هر کدام از ۱ تا ۶، n بار تکرار شده باشد،

• تعداد زیرمجموعه‌هایی که باقیمانده‌ی مجموع اعضای آن بر ۷ برابر با $1 \leq i \leq 6$ باشد، برابر است با $\frac{2^{6n}-1}{7}$
• تعداد زیرمجموعه‌هایی که باقیمانده‌ی مجموع اعضای آن بر ۷ برابر با صفر باشد برابر است با $\frac{2^{6n}+6}{7}$

اثبات. چون ۷ عدد اول است، هر کدام از ۱ تا ۶ در پیمانه‌ی ۷ یک وارون ضربی یکتا دارند. اگر یک زیرمجموعه داشته باشیم که باقیمانده‌اش بر ۷ برابر با $p$ باشد، با ضرب (در پیمانه ۷) هر کدام از اعضای این زیرمجموعه در $p^{-1}q$، یک زیرمجموعه‌ی دیگر بدست می‌آید که باقیمانده‌ی مجموع آن بر ۷ برابر با $q$ است. چون ۷ اول است، این عمل هر کدام از زیرمجموعه‌ها با باقیمانده‌ی $p$ را به یک زیرمجموعه با باقیمانده‌ی $q$ مجزا نگاشت می‌کند. همچنین ضرب هر کدام اعضای هر کدام از اعضای این زیرمجموعه‌ی جدید در $q^{-1}p$ زیرمجموعه‌ی اصلی را می‌دهد.

عمل بالا یک تناظر یک‌به‌یک بین زیرمجموعه‌های با باقیمانده‌ی ۱ تا ۶ می‌دهد. پس تعداد زیرمجموعه‌هایی که باقیمانده‌ی آن بر ۷ برابر با ۱ یا ۲ یا ... یا ۶ است مساوی است.

بقیه‌ی اثبات را با استقرای ریاضی انجام می‌دهیم:

حالت پایه (n=1). قبلا دیدیم که برای حالتی که از هر کدام از ۱ تا ۶ یک عدد داشته باشیم، تعداد زیرمجموعه‌ها با باقیمانده‌ی $1 \leq i \leq 6$ برابر است با ۹. پس تعداد زیرمجموعه‌هایی در این حالت که باقیمانده‌ مجموعشان برابر با صفر شود، برابر است با $2^6-6\times9 = 10$.

گام استقرا. برای اینکه یک زیرمجموعه با باقیمانده صفر در حالت تکرار n+1 بسازیم، ۷ انتخاب داریم:

• از حالت n تکرار یک زیرمجموعه با باقیمانده $1 \leq i \leq 6$ انتخاب کنیم و از حالت ۱ تکرار یک زیرمجموعه با باقیمانده $7 - i$ انتخاب کنیم و این دو رو بچسبونیم به هم.
• از حالت n تکرار یک زیرمجموعه با باقیمانده صفر انتخاب کنیم و از حالت ۱ تکرار یک زیرمجموعه با باقیمانده صفر انتخاب کنیم و این رو بچسبونیم به هم.

پس تعداد کل زیرمجموعه‌های حالت n+1 تکرار که باقیمانده مجموع آن صفر باشد، برابر است با:

$$ 6 \times 9 \times \frac{2^{6n} - 1}{7} + 10 \times \frac{2^{6n}+6}{7} = \frac{54 \times 2^{6n} - 54 + 10 \times 2^{6n} + 60}{7} = \frac{2^{6(n+1)} + 6}{7} $$

و به طرز مشابه برای حالت باقیمانده‌ی غیر صفر به دست می‌آید $\frac{2^{6(n+1)} - 1}{7}$.