NDLI: A generalized algorithm for solving n coins problem

Content Provider	IEEE Xplore Digital Library
Author	Ghosh, J. Senmajumdar, P. Maitra, S. Dhal, D. Pal, R.K.
Copyright Year	2011
Description	Author affiliation: Dum Dum Subhasnagar High School (HS), 43 S B Road, Rabindranagar, 24 Parganas (North), Kolkata - 700 065, West Bengal, India (Dhal, D.) \|\| Department of Information Technology, School of Technology, Assam University, Silchar, Cachar - 788 011, India (Pal, R.K.) \|\| Department of Computer Science and Engineering, University of Calcutta, 92 A P C Road, Kolkata - 700 009, West Bengal, India (Senmajumdar, P.; Maitra, S.) \|\| Department of Mathematics, Surendra Institute of Engineering and Management, New Chamta, Siliguri, Darjeeling - 734 009, West Bengal, India (Ghosh, J.)
Abstract	Eight coins problem is a well-known problem in mathematics as well as in computer science. In this problem eight coins are given, say A, B, C, D, E, F, G, and H, and we are told that only one is counterfeit (or false), as it has a different weight than each of the others. We want to determine which coin it is, making use of an equal arm balance. At the same time we want to identify the counterfeit coin using a minimum number of comparisons and determine whether the false coin is heavier or lighter than each of the remaining. In this paper, we develop algorithms for solving the counterfeit coin problem for any given number n of coins. The first algorithm is in essence based on the existing classical solution for the eight coins problem (with slight modification) for larger values of n, where n is a power of two beyond eight, as two and four being base cases. Then we develop an algorithm for solving n coins problem, where n is even but not power of two, i.e., the numbers are six, ten, 12, 14, 18, 20, etc. At the end, we have extended the same to solve the counterfeit coin problem for odd number of coins as well.
Starting Page	411
Ending Page	415
File Size	1095964
Page Count	5
File Format	PDF
ISBN	9781424487271
e-ISBN	9781424487288
DOI	10.1109/CSAE.2011.5952498
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-06-10
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Eight coins problem Coin counterfeiting Odd coin problem Comparison Equal arm balance Algorithm Decision tree Even coin problem
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The first algorithm for solving two coins counterfeiting with ω(ΔH) = ω(ΔL)

On a New Universal Algorithm for Coins Problem and Its Realization

An endeavour to find two unequal false coins

Two-pan balance and generalized counterfeit coin problem.

Algorithm for Solving Games

Defective coin problem: an algorithmic analysis

Wiener odd and even indices on BC-Trees

Dynamics and constraints in insight problem-solving.

Lower bounds on two coin-weighing problems, with applications to threshold circuits (2007).

A generalized algorithm for solving n coins problem

Similar Documents

The first algorithm for solving two coins counterfeiting with ω(ΔH) = ω(ΔL)

On a New Universal Algorithm for Coins Problem and Its Realization

An endeavour to find two unequal false coins

Two-pan balance and generalized counterfeit coin problem.

Algorithm for Solving Games

Defective coin problem: an algorithmic analysis

Wiener odd and even indices on BC-Trees

Dynamics and constraints in insight problem-solving.

Lower bounds on two coin-weighing problems, with applications to threshold circuits (2007).

A generalized algorithm for solving n coins problem