9 монет арасынан жалғанды анықтау үшін қажетті ең аз салмақтау санын қалай анықтауға болады?

9 монета және олардың ішінде жалғаны бар классикалық жұмбақ. Жалған монетаны (жеңіл немесе ауыр) анықтау үшін салмақтарда ең аз қанша өлшеу керек.

9 монета үшін ең аз өлшеу саны — 2.

Негіздеме:

• Әр өлшеу үш нәтиже бере алады: сол жақ табақ ауыр, оң жақ ауыр немесе тең.
• k өлшеуде 3^k түрлі нұсқаны ажыратуға болады.
• 2n нұсқаны ажырату керек (әр монета жеңіл немесе ауыр болуы мүмкін), яғни 2*9=18 нұсқа.
• 3^2=9 < 18, жеткіліксіз.
• 3^3=27 >= 18, демек 3 өлшеу жеткілікті.

Алайда, егер 9 монетаның жалғаны жеңіл немесе ауыр екені белгісіз болса, ең аз өлшеу саны — 3.

Егер жалған монета жеңіл немесе ауыр екені белгілі болса, 2 өлшеу жеткілікті.

3 өлшеу стратегиясының мысалы:

• 9 монетаны 3 топқа бөлу, әрқайсысы 3-ден.
• Екі топты салмақтау.
• Нәтижесіне қарай күдікті топты таңдап, процедураны қайталау.

Осылайша, белгісіз жалған монетаның типі бар 9 монета үшін ең аз өлшеу саны — 3.